Implementación de Algoritmo Greedy para Cambio de Monedas

Clase 37 de 42 • Curso Práctico de Estructuras de Datos y Algoritmos

Resumen

Ahora es momento de implementar el greedy algorithm que diseñamos en la clase anterior, en esta clase vamos a definir el código para encontrar la moneda correcta utilizando recursividad.

Buscaremos el mínimo de monedas posible para obtener el cambio total tomando monedas del set de monedas “coinset”
Necesitamos un auxiliar “res” para que cada moneda funcione como stack recursivo
Crear una función recursiva para encontrar el valor, haciendo iteraciones hasta que encuentre cuál es el billete que va a utilizar
Retornar las monedas necesarias para el cambio

DAVID STEVEN BOCAREJO IBAÑEZ

student•

A lo largo del curso Me he sentido perdido en el COMO se desarrolla algoritmo de una forma lógica. Osea el por que y la secuencia de cada linea de código. Y siento que esto me pasa debido a en muchas ocasiones, llegado un punto el profe dice "espera, no te preocupes, mas adelante veras por que" Y eso hace (desde mi punto de vista) que a lo largo del desarrollo del código quede huecos que después con un repaso muy general no se cierran. y esto sin contar que el cambio de sintaxis de cada lenguaje si no es conocido ayuda en la confusión. Y digo que pasa en el Código, por que cuando explica los conceptos, son muy claros y entendibles teóricamente el problema siento yo es al pasar al código.

Lorena Mosquera González

student•

Literal. Yo inicie con este curso y me empece a ver demasiado perdida por mas que revisara una y otra vez los videos, prosegui a ver otros cursos mientras este lo deje en pausa, volvi y ya entiendo un poco mejor varias de las expresiones a las que se refiere. Respecto a lo de los programas, opino igual.

David Barreto

student•

Me sucedió lo mismo

Gabriel Vargas Monroy

student•

No se si platzi tenga actualmente un curso de ciencias de la computación, en ciencias para la computación se hablan en mas detalle de:

Cada uno de los métodos de ordenamiento para listas(Por lo menos con mas detalle).
Temas de Matemáticas Discretas para optimización de algoritmos
- En el caso de Conjuntos potencia y Teorema de Cantor
- Complejidad algorítmica
- Consumo en Memoria
Grafos y Arboles
- Cada uno de los tipos de arboles y su forma de uso
- Teoria de Grafos
- Arboles B
- Arboles B+
- Arboles Binarios Simples
- Arboles AVL
- Arboles Roji-negros
Operaciones pre-orden y pos-orden para compiladores

Ricardo Celis

teacher•

Todavía no lo tenemos pero la idea es llegar al punto de tener todo ese contenido explicado con la metodología de platzi!

Luis Eduardo Quiroga Esparza

student•

De casualidad ya salió algún curso con todo esto?

luis martinez

student•

sería bueno hacer los ejemplos con buenas prácticas de nomenclatura de variables y no poner nombres como: "res" o "n" y "N"

Elisa Zamarron Muñoz

student•

Totalmente de acuerdo, tener variables así hace que uno se pueda perder en el código

Fernando Famanía

student•

Hola Luis, creo que esas buenas practicas, las deberias usar tu, en el momento que realmente lo necesites, ya sea que estes haciendo un programa complejo, que necesites leer mas adelante, o que trabajes en equipo y el resto lo tenga que leer, pero para un curso, no lo veo necesario, son programas sencillos, y nadie mas que tu en el momento lo necesita leer, saludos.

Andres Felipe Leal Mora

student•

Lo desarrollé de la siguiente manera en Python:

import random

def greedychange(coins_set, change, coins):

    for i in range(len(coins_set)-1,-1,-1):
        if change == 0:
            return coins
        elif change >= coins_set[i]:
            coins.append(coins_set[i])
            return greedychange(coins_set, change - coins_set[i], coins)

if __name__ == '__main__':

    Cambio = random.randint(7, 30)

    print(f'Se requiere devolver {Cambio} pesos de cambio\n')
    monedas_denominaciones = [1 ,5, 10, 15]
    vueltos_en_monedas = []

    greedychange(monedas_denominaciones, Cambio, vueltos_en_monedas)
    print('Se entregaran las siguientes denominaciones: ', vueltos_en_monedas)```

LUIS ALEJANDRO BERNAL ROMERO

student•

En Bogotá se dice las vueltas, estas las guardaba para ahorralas y comprar libros de programación, no existía Internet :-)

Azael Ortega

student•

Como bien dices Celis, en México se le dice "cambio", en tiempos pasados era casi como "oro", cuando era el resultado de ir por las tortillas y pasabas por un lugar de maquinitas (Arcades, videojuegos) 😄

Gabriel De Andrade

student•

En Venezuela 🇻🇪 se le dice vuelto!

Hiram Rodriguez Gomez

student•

En México, en algunas zonas es común decirle "feria"

Moisés Manuel Morín Hevia

student•

Ay ! el lenguaje C no me cae tan bien, mejor Python que es un amor.

Never Andrés Aparicio Hernandéz

student•

el cambio en colombia se dice Cambio vueltas de todo la verdad.

Hanier Morales

student•

En Nicaragua le decimos "vuelto" :P

David Lara

student•

El Chile al cambio le llamamos vuelto, sería interesante en el ejercicio poder aplicar una ley nueva en mi pais llamada "ley del vuelto", que sirve para redondear los vueltos ya que las monedas de 1 y 5 casi están fuera de circulación, por su nulo valor.

Hector Esau

student•

Me gustaría mucho que hicieran una escuela o una ruta de aprendizaje dedicada a entender el codigo del un SO para poder hacer aportes

Hugo perez garcia

student•

Eso sería increíble, por supuesto yo lo haría. Incluso para hacer mini SO embedidos para automatismos enanos o para IoT.

Luis Castro

student•

buenas intento hacerlo en javascript pero me tira too much recursividad, quiero pasarle los parametros y probarlo pero no logro entender bien el intMAX me esta tirando el mayor numero de 1 (supongo que lo toma predeterminado de coins ya que nunca le asigno un valor).

function greedyChange(Monedas, DebeDinero,MisMonedas)
{
	if(DebeDinero==0)
	{
		return 0;
	}
	if (DebeDinero<0)
	{
		return Number.MAX_VALUE; //regresa el mayor numero
	}
	var coins=Number.MAX_VALUE ; //variable para tener el numero mayor

	for(var i=0 ; i<DebeDinero;i++)  
	{
		var AuxMonedas=greedyChange(Monedas,DebeDinero,MisMonedas-Monedas[i]);  
		if(AuxMonedas!=Number.MAX_VALUE)
		{
			coins=Math.min(coins,AuxMonedas+1);
		}
		console.log(AuxMonedas);
	}


}

var Monedillas=[3,4,5,6,7,8];
var deuda=30;
var cantMonedas=Monedillas.length;
greedyChange(Monedillas,deuda,cantMonedas);```

Ariel Sharpe

student•

Eso puede ser porque la recursividad es infinita o se aplica muchas veces, revisa que haya un punto de fin a la recursividad de tu algoritmo.

Carlos Lefin Henriquez

student•

la unica forma de que el programa haga menos recursividades es pasandole menos monedas a comparar.

Christian Gómez

student•

No entiendo como en el código, la variable coinSet empieza por el mayor valor osea el 20 para irle restando a N.

Este for no lo entiendo: va de mi moneda de menor valor a la mas alta ?

  for(int i = 0; i<n;i++)
    {
        //printf("%i, ", coinSet[i]);
        int res = greedyChange(coinSet, n, N-coinSet[i]);
        if(res != INT_MAX)
            coins = min(coins, res+1);
            
    }```

Luis Gerardo Colmenares

student•

Creo que iría de la moneda de mayor valor a la de menor. coinSet[] = {20, 15, 10, 5, 1}

William Andres Dussan Gonzalez

student•

Aquí entonces el segundo if del greedyChange, es cuando el resultado se pasa del cambio completo que el usuario revise, si estoy en lo correcto?

Moisés Manuel Morín Hevia

student•

Sí, el el resultado se pasa del cambio.

David Barreto

student•

Alguien que me ayude en este pregunta, si aun no conoces el lenguaje de programación en el que intentan explicarte un algoritmo, eso dificulta tu aprendizaje si o no? que piensan amigos?

Miqueas Gamero

student•

Bueno David. Yo desconozco de Python, y para hacer los algoritmos no me he podido basar en la clase de Ricardo más que en la lógica (y hasta por ahí nomas). Pero si existen alternativas para poder implementarlo en el lenguaje que vos sepas. Aquí te dejo una fuente super confiable y que a mi me ha ayudado mucho: https://www.geeksforgeeks.org Allí están todos los algoritmos en todos los lenguajes explicados al detalle

GERARDO EMMANUEL ALONSO CELIS

student•

Que interesante pregunta, en lo personal pienso que no ha afectado mi aprendizaje, por que al menos en éste curso el profesor ha utilizado tres lenguajes (C, Java, Phyton) en los cuales la escritura es un poco diferente pero la lógica e incluso los nombres de las funciones es el mismo. Lo que me causa cierta "incomodidad" por así decirlo es que cambie de lenguaje de un momento a otro. En lo personal hubiera preferido que se siguiera con C todo el curso, ya que fue el lenguaje con el que comenzó, pero nada que afecte mucho. Es mi opinión.

Manuel Valenzuela

student•

En Mexico se dice, "cambio", o "feria" xd

Karen Paola Diaz Duarte

student•

Wilson Erik Ramírez Franco

student•

En El Salvador se dice "el vuelto" o " el cambio"