Cursos Empresas Blog Live Conf Eventos Precios

0:009:54

Recursos

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

Implementación de Algoritmo Greedy para Cambio de Monedas

Curso Práctico de Estructuras de Datos y Algoritmos

Clase 37 de 42

Clase 37 / 42

Comentarios (63)63 comentarios

DAVID STEVEN BOCAREJO IBAÑEZ

Hace 6 años

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

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

Me sucedió lo mismo

Gabriel Vargas Monroy

Hace 8 años

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

Profesor

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

Hace 7 años

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

luis martinez

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

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

Fernando Famanía

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

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

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

Azael Ortega

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

En Venezuela 🇻🇪 se le dice vuelto!

Hiram Rodriguez Gomez

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

Moisés Manuel Morín Hevia

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

Never Andrés Aparicio Hernandéz

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

Hanier Morales

En Nicaragua le decimos "vuelto" :P

David Lara

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 M

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

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

Ariel Sharpe

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

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

Christian Gómez

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

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

William Andres Dussan Gonzalez

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?

Sí, el el resultado se pasa del cambio.

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

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

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

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

Karen Paola Diaz Duarte

Wilson Erik Ramírez Franco

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

Recursos

Resumen

Implementación de Algoritmo Greedy para Cambio de Monedas

Progreso del curso

Bienvenido al Curso

Introducción a los algoritmos

Algoritmos de ordenamiento

Recursividad

Divide and conquer y programación dinámica

Algoritmos 'Greedy'

Grafos y árboles

¿Cómo comparar Algoritmos?

¿Qué sigue?