Bienvenido al Curso

1

Introducci贸n al curso b谩sico de algoritmos y estructuras de datos

Introducci贸n a los algoritmos

2

驴Qu茅 entiende una computadora?

3

Lenguajes de programaci贸n

4

Estructuras de datos

5

驴Qu茅 es un algoritmo?

6

Metodolog铆a para la construcci贸n de un algoritmo

7

Variables y tipos de datos

8

User defined data types

9

Instalando Ubuntu Bash en Windows

10

Creando nuestro user defined data type

11

Abstract Data Types b谩sicos: Lists, Stacks, Queues

12

Explicaci贸n gr谩fica Data Types b谩sicos

13

Glosario de funciones para Abstract Data Types

14

Clases y objetos

15

Creando tu primera Queue: Arrays

16

Creando tu primera Queue: implementaci贸n.

17

Creando tu primera Queue: implementar la funci贸n enQueue

18

Creando tu primera Queue: implementar la funci贸n deQueue

19

Creando tu primera Queue: main code

Algoritmos de ordenamiento

20

Algoritmos de ordenamiento

21

Bubble sort

22

Bubble sort: implementaci贸n

23

Bubble sort: main code

24

Insertion sort

25

Desaf铆o: implementa un algoritmo de ordenamiento

Recursividad

26

Recursividad

27

La funci贸n Factorial, calculando el factorial recursivamente

28

Manejo de cadenas de caracteres

29

Arte: Generando arte recursivo

Divide and conquer y programaci贸n din谩mica

30

Divide and Conquer (divide y vencer谩s)

31

Qu茅 es la programaci贸n din谩mica (divide y vencer谩s v2.0)

32

MergeSort

33

Desaf铆o: Buscar el algortimo m谩s r谩pido de sort

34

Implementando QuickSort con Python

35

Implementando QuickSort con Python: main code

Algoritmos 'Greedy'

36

Qu茅 son los Greedy Algorithm

37

Ejercicio de programaci贸n greedy

38

Ejercio de programaci贸n greedy: main code

Grafos y 谩rboles

39

Grafos y sus aplicaciones

40

脕rboles

驴C贸mo comparar Algoritmos?

41

C贸mo comparar algoritmos y ritmo de crecimiento

驴Qu茅 sigue?

42

Cierre del curso y siguientes pasos

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Ejercicio de programaci贸n greedy

37/42
Recursos

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.

  1. Buscaremos el m铆nimo de monedas posible para obtener el cambio total tomando monedas del set de monedas 鈥coinset
  2. Necesitamos un auxiliar 鈥res鈥 para que cada moneda funcione como stack recursivo
  3. Crear una funci贸n recursiva para encontrar el valor, haciendo iteraciones hasta que encuentre cu谩l es el billete que va a utilizar
  4. Retornar las monedas necesarias para el cambio

Aportes 53

Preguntas 7

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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 鈥渆spera, 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.

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

ser铆a bueno hacer los ejemplos con buenas pr谩cticas de nomenclatura de variables y no poner nombres como: 鈥渞es鈥 o 鈥渘鈥 y 鈥淣鈥

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)```

En Bogot谩 se dice las vueltas, estas las guardaba para ahorralas y comprar libros de programaci贸n, no exist铆a Internet 馃槂

Como bien dices Celis, en M茅xico se le dice 鈥渃ambio鈥, en tiempos pasados era casi como 鈥渙ro鈥, cuando era el resultado de ir por las tortillas y pasabas por un lugar de maquinitas (Arcades, videojuegos) 馃槃

En Venezuela 馃嚮馃嚜 se le dice vuelto!

En M茅xico, en algunas zonas es com煤n decirle 鈥渇eria鈥

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

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

El Chile al cambio le llamamos vuelto, ser铆a interesante en el ejercicio poder aplicar una ley nueva en mi pais llamada 鈥渓ey 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.

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

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?

En Mexico se dice, 鈥渃ambio鈥, o 鈥渇eria鈥 xd

En El Salvador se dice 鈥渆l vuelto鈥 o " el cambio"

Vaya, estoy listo, por cierto, el c贸digo es arte.馃ぉ

Aqu铆 en M茅xico le solemos decir feria o morralla al cambio jaja

Mi intenci贸n con C es para aprender a programar videojuegos y adem谩s para programar Arduinos y Raspberry PI.

En Rep煤blica Dominicana se dice: Devuelta.

Si no fuera por GPT ya hubiera desertado馃ぃ

Aportarian sin duda en el caso de la creaci贸n de un curso de C y C++, (deep functions) porque creo que son lenguajes que aportan mucho en la forma de programar actualmente. Ahorrarian el tiempo de leer un libro (lo cual me parece excesivamente positivo) para entender el lenguaje, y ser铆a m谩s visual en el aprendizaje.

A los que se sientan perdidos, sobre todo desde los algoritmos de ordenamiento, entiendo su dolor xp

Y bueno, no entend铆:
*Por qu茅 usa la funci贸n min
*Por qu茅 usa la librer铆a <climits>
*Qu茅 es lo que retorna coins
*C贸mo funciona el algoritmo (ahora en C++, ser铆a el 4to lenguaje luego de c, java, python que han visto en un solo curso).

A los que se sientan perdidos, no se den por vencidos, es solo un reto mas para entender la computaci贸n y nadie dijo que seria super f谩cil. Aqu铆 les dejo informaci贸n relacionada a los algoritmos de ordenamiento para que lo chequen https://kesquivel.files.wordpress.com/2012/09/tema_1_algoritmosordenacionbusqueda1.pdf

cuando la maquina no tenga cambio te da chicles

aqui hya una explicacion de las librerias limits

https://www.tutorialspoint.com/c_standard_library/limits_h

en 馃嚚馃嚧 se dice 鈥渧ueltas鈥

En espa帽a tanto el cambio, como la vuelta se utiliza.

en python el int_max se puede hacer con float(鈥榠nf鈥)

Me gustar铆a ver algoritmos como el de Dijkstra programado, o algo parecido apra encontrar el camino m谩s corto. :9

En mi pa铆s es Vuelto, aqu铆 en Colombia donde vivo actualmente es vueltas.

La verdad es que yo estoy en esta ruta de aprendizaje para aprender a programar desde cero, esto quiere decir que no cuento con muchas bases de programaci贸n, cuando se hacen los cambios a otro lenguaje se me dificulta y algunas funciones las desconozco, sobre todo el hecho de que extension usar o como compilar, he estado siguiendo la ruta de fundamentos de programaci贸n y solo he visto C y C++, a excepci贸n del curso de programaci贸n b谩sica donde vi JavaScript. El profesor si explica los conceptos muy bien, no tengo problema para que sirve cada algoritmo, pero donde empiezan mis problemas son en los c贸digos, literal, me llego a perder鈥

Me salta errores en el editos, pero esperemos que en la sguiente clase se solucionen

#include <iostream>
#include <climits>

using namespace std;

int greedyChange( int coinSet, int n, int N ) {
    if ( N == 0 ) 
        return 0;
    
    if ( N < 0 )
        return INT_MAX;
    
    int coins = INT_MAX;


    // Recorremos el set de monedas
    for ( int i = 0; i < n; i++ ) {
        int res = greedyChange( coinSet, n, N - coinSet[i] );
        if( res != INT_MAX ) {
            coins = min(coins, res + 1);
        }
    }

    return coins;
    
}```

La morralla

Un quinto le decimos en mi pueblo.

haaa con que asi era XD

En Bogot谩 se le dice devueltas.

Una forma de aplicar este algoritmo en C


En python:
![](

De_veinte = [20,20,20,20,20]
De_diez = [10,10,10,10,10]
De_cinco = [5,5,5,5,5]
De_uno = [1,1,1,1,1]

def respalda(arreglo) :
    vector = []
    for i in arreglo:
        vector.append(i)
    return vector

def Dame_moneda(cantidad) :
    cambio = []
    sincambio = False

    global De_veinte
    global De_diez
    global De_cinco
    global De_uno
    V = respalda(De_veinte)
    D = respalda(De_diez)
    C = respalda(De_cinco)
    U = respalda(De_uno)

    while cantidad:
        if cantidad >= 20 :
            if De_veinte != [] :
                cambio.append(20)
                De_veinte.pop()
                cantidad -= 20
                sincambio = False
                continue
            else :
                sincambio = True

        if cantidad >= 10 :
            if De_diez != [] :
                cambio.append(10)
                De_diez.pop()
                cantidad -= 10
                sincambio = False
                continue
            else :
                sincambio = True

        if cantidad >= 5 :
            if De_cinco != [] :
                cambio.append(5)
                De_cinco.pop()
                cantidad -= 5
                sincambio = False
                continue
            else :
                sincambio = True
        if cantidad >= 1 :
            if De_uno != [] :
                cambio.append(1)
                De_uno.pop()
                cantidad -= 1
                sincambio = False
                continue
            else :
                sincambio = True
        if sincambio :
            break
    if sincambio :
        De_veinte = V
        De_diez = D
        De_cinco = C
        De_uno = U
        return []
    else:
        return cambio


if __name__ == "__main__" :
    while (True) :
        try:
            cantidad = input("ingresa la cantidad que quieras retirar [salir]\n")
            if str(cantidad) == "salir" :
                break
            int (cantidad)
        except ValueError :
            print("el valor es incorrecto intenta de nuevo\n")
            continue
        else:
            cambio = Dame_moneda(int(cantidad))
            if cambio:
                print("tu cambio es : {} \n".format(cambio))
            else:
                print("lo sineto no hay suficiente cambio")

En C++ ok aqui se me complico por que por error al hacer remplase borre parte de la librer铆a vector as铆 que tuve que reconstruir la parte borrada pero al fina pude hacerla funcionar d谩ndole mi propio toque XD
![](

#include <iostream>
#include <deque>
#include <vector>

using namespace std;

template <typename T> deque<T> &operator<<(deque <T> &s,const T &valor){
    s.push_back(valor);
    return s;}

ostream &operator<<(ostream &o,const vector<int>&v){
    vector<int>::const_iterator i;
    o <<"[ ";
    for(i = v.begin(); i != v.end();++i)
        o<<*i<<" ";
    return o<<"]";}

deque<int> De_Veinte;
deque<int> De_Diez;
deque<int> De_Cinco;
deque<int> De_Uno;

vector<int> Dame_Cambio(const int &CANTIDAD){
    vector<int>Cambio;
    int cantidad = CANTIDAD;
    bool sinCambio = false;
    deque<int> V = De_Veinte;
    deque<int> D = De_Diez;
    deque<int> C = De_Cinco;
    deque<int> U = De_Uno;
    while(cantidad){
        if(cantidad >= 20){
            if(!De_Veinte.empty()){
                cantidad -= 20;
                Cambio.push_back(20);
                De_Veinte.pop_back();
                sinCambio = false;
                continue;}
           else
                sinCambio = true;}

        if(cantidad >= 10){
            if(!De_Diez.empty()){
                cantidad -= 10;
                Cambio.push_back(10);
                De_Diez.pop_back();
                sinCambio = false;
                continue;}
           else
                sinCambio = true;}

        if(cantidad >= 5){
            if(!De_Cinco.empty()){
                cantidad -= 5;
                Cambio.push_back(5);
                De_Cinco.pop_back();
                sinCambio = false;
                continue;}
           else
                sinCambio = true;}

        if(cantidad >= 1){
            if(!De_Uno.empty()){
                cantidad -= 1;
                Cambio.push_back(1);
                De_Uno.pop_back();
                sinCambio = false;
                continue;}
           else
                sinCambio = true;}

        if(sinCambio)
            break;}

    if(sinCambio){
        De_Veinte = V;
        De_Diez = D;
        De_Cinco = C;
        De_Uno = U;
        vector<int>vacio;
        return vacio;}
    else
        return Cambio;}

int main()
{
    De_Veinte<<20<<20<<20<<20<<20;
    De_Diez  <<10<<10<<10<<10<<10;
    De_Cinco <<5<<5<<5<<5<<5;
    De_Uno   <<1<<1<<1<<1<<1;
    while(true){
        int cantidad;
        cout<<"ingresa la cantidad que deseas retirar [-1 = salir]"<<endl;
        cin>> cantidad;
        vector<int>cambio;
        if(cantidad == -1)
            break;

        cambio = Dame_Cambio(cantidad);

        if(!cambio.empty())
            cout <<"tu cambio es : "<<cambio<<endl;
        else
            cout <<"lo sentimos no hay cambio suficiente"<<endl;}
    return 0;
}

Antes de ver el v铆deo me avent茅 mi versi贸n del greedy en mis tres lenguajes aqu铆 el de C:
![](

#include <stdio.h>
#include <stdlib.h>

void push_back(int **arreglo, int contenido);
void pop(int **arreglo);
void copiar(const int *Original,int **copia);
void imprimir(const int *vector);

typedef struct Dinero{
    int * veinte;
    int * diez;
    int * cinco;
    int * uno;       }Dinero;

Dinero *Billetes(int cantidad);
void Quemar_Dinero(Dinero *billetes);
Dinero * Respaldar(const Dinero* existente);

#define SI '\0'
#define NO '\1'

int *Dame_cambio(const int cantidad,Dinero **Cajero){
    char HayCambio = SI;
    int *Cambio = NULL;
    Dinero *Bolsa = Respaldar(Cajero[0]);
    int Restante = cantidad;
    while(Restante){
        if(Restante >= 20){
            if(Cajero[0]->veinte){
                pop(&Cajero[0]->veinte);
                push_back(&Cambio,20);
                Restante -= 20;
                HayCambio = SI;
                continue;}
            else
                HayCambio = NO;}

        if(Restante >= 10){
            if(Cajero[0]->diez){
                pop(&Cajero[0]->diez);
                push_back(&Cambio,10);
                Restante -= 10;
                HayCambio = SI;
                continue;}
            else
                HayCambio = NO;}

        if(Restante >= 5){
            if(Cajero[0]->cinco){
                pop(&Cajero[0]->cinco);
                push_back(&Cambio,5);
                Restante -= 5;
                HayCambio = SI;
                continue;}
            else
                HayCambio = NO;}

        if(Restante >= 1){
            if(Cajero[0]->uno){
                pop(&Cajero[0]->uno);
                push_back(&Cambio,1);
                Restante -= 1;
                HayCambio = SI;
                continue;}
            else
                HayCambio = NO;}
        if(HayCambio)
            break;}

    if(HayCambio){
        Quemar_Dinero(Cajero[0]);
        Cajero[0] = Bolsa;
        if(Cambio)
            free(Cambio);
        return NULL;}
    else{
        Quemar_Dinero(Bolsa);
        return Cambio;}}

int main()
{
    Dinero *cajero = Billetes(5);
    int * Cambio = NULL;
    while(1){
        int cantidad;
        printf("Cuanto deseas retirar [-1 = salir]\n");
        scanf("%d",&cantidad);

        if(cantidad == -1) break;

        Cambio = Dame_cambio(cantidad,&cajero);
        imprimir(Cambio);
        free(Cambio);
        Cambio = NULL;}

    Quemar_Dinero(cajero);
    return 0;
}

void push_back(int **arreglo, int contenido){
    if(arreglo == NULL)return;
    if(arreglo[0]== NULL){
        arreglo[0] = (int *)calloc(2,sizeof(int));
        arreglo[0][0] = 2;
        arreglo[0][1] = contenido;
        return;}
    int dimencion = arreglo[0][0];
    int *Nuevo_arreglo = (int*)calloc(dimencion + 1,sizeof(int));
    Nuevo_arreglo[0] = dimencion + 1;

    int i;
    for(i = 1; i < dimencion;++i)
        Nuevo_arreglo[i] = arreglo[0][i];

    Nuevo_arreglo[dimencion] =contenido;
    free(arreglo[0]);
    arreglo[0]= Nuevo_arreglo;}

void pop(int **arreglo){
    if(arreglo == NULL||arreglo[0]==NULL)return;
    int dimencion = arreglo[0][0] - 1;

    if(dimencion == 1){
        free(arreglo[0]);
        arreglo[0] = NULL;
        return;}

    int *Nuevo_arreglo = (int*)calloc(dimencion,sizeof(int));
    Nuevo_arreglo[0] = dimencion;
    int i;
    for(i = 1; i < dimencion;++i)
        Nuevo_arreglo[i] = arreglo[0][i];
    free(arreglo[0]);
    arreglo[0] = Nuevo_arreglo;}

void copiar(const int *Original,int **copia){
    if(Original == NULL){
        copia[0] = NULL;
        return;}
    if(copia||copia[0]) free(copia[0]);
    copia[0] = (int *)calloc(Original[0],sizeof(int));
    int i;
    for(i = 0; i < Original[0];++i)
        copia[0][i] = Original[i];}

void imprimir(const int *vector){
    if(vector == NULL){
        printf("Lo sentimos no hay suficiente cambio\n");
        return;}
    int i;
    printf("Su cambio : [ ");
    for(i = 1; i < vector[0]; ++i)
        printf("%d ",vector[i]);
    printf("]\n");}

Dinero *Billetes(int cantidad){
    Dinero *Bolsa = (Dinero*)malloc(sizeof(Dinero));
    Bolsa->veinte = (int*)calloc(cantidad + 1,sizeof(int));
    Bolsa->diez = (int*)calloc(cantidad + 1,sizeof(int));
    Bolsa->cinco = (int*)calloc(cantidad + 1,sizeof(int));
    Bolsa->uno = (int*)calloc(cantidad + 1,sizeof(int));

    Bolsa->veinte[0] = cantidad + 1;
    Bolsa->diez[0] = cantidad + 1;
    Bolsa->cinco[0] = cantidad + 1;
    Bolsa->uno[0] = cantidad + 1;

    int i;
    for(i = 1; i <= cantidad;++i){
        Bolsa->veinte[i] = 20;
        Bolsa->diez[i] = 10;
        Bolsa->cinco[i] = 5;
        Bolsa->uno[i] = 1;}
    return Bolsa;}

void Quemar_Dinero(Dinero *billetes){
    if(billetes == NULL)return;
    if(billetes->veinte)free(billetes->veinte);
    if(billetes->diez)free(billetes->diez);
    if(billetes->cinco)free(billetes->cinco);
    if(billetes->uno)free(billetes->uno);
    free(billetes);}

Dinero *Respaldar(const Dinero* existente){
    if(existente == NULL)return NULL;
    Dinero *respaldo = (Dinero*)malloc(sizeof(Dinero));
    copiar(existente->veinte,&respaldo->veinte);
    copiar(existente->diez,&respaldo->diez);
    copiar(existente->cinco,&respaldo->cinco);
    copiar(existente->uno,&respaldo->uno);
    return respaldo;}```

Es muy lenta la complementaci贸n recursiva hecha.

Mi c贸digo adaptado a C#

using System;

namespace GreedyCoinChange
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] coinSet={1,5,10,15,20};
            int n = coinSet.Length;
            int N = 30;
            Console.WriteLine("El m铆nimo de monedas para dar cambion es: ");
            Console.Write(greedyChange(coinSet, n, N));
        }

        private static int greedyChange(int[] coinSet, int n, int N )
        {
            if (N==0)
                return 0;
            if (N<0)
                return Int16.MaxValue;
            int coins = Int16.MaxValue;
            for (int i = 0; i < n; i++)
            {
                 int res = greedyChange(coinSet, n, N - coinSet[i]);
                 if(res != Int16.MaxValue)
                    coins = Math.Min(coins, res+1);
            }
             return coins;
        }
    }
    
}

Me emociona mucho hacer codigo en las clases:

#include <iostream>
#include <climits>
using namespace std;

int greedyChange(int coinSet, int n, int N)
{
  if (n==0)
  {
    return 0;
  }
  if(N<0)
  {
    return INT_MAX;
  }
  int coins = INT_MAX;
  //RECORREMOS TODO EL SET DE MONEDAS  PARA DAR CAMBIO
  for(int i = 0; i<n; i++)
  {
    int res = greedyChange(coinSet, n, N-coinSet[i]);
    if(res != INT_MAX)
    {
      coins = min(coin, res+1);
    }
  }
  return coins;
}

C贸mo soporte y profundizaci贸n para este curso recomiendo:
Introduction to Algorithms. Thomas H. Cormen et Al.
No se imaginan cuanta informaci贸n tiene, ejercisios y de todo. Ojal谩 les sea de ayuda.

Hola Amigos,

No entiendo aun para que se usa la N y la n, creo que la n es la longitud del arreglo coinSet, pero la N no la entiendo

Me pueden ayudar por favor?

Mil gracias

Feria jajajaja

Para usarlo en Rob贸tica

En JavaScript!

function greedy(coinsSet, change, coins){
    for(let item of coinsSet){
        if(change === 0){
            return coins 
        } else if(item <= change){
            coins.push(item)
            return greedy(coinsSet, change - item, coins)
        }
    }
}

const coinsSet = new Set([100000,50000,20000,10000,5000,2000,1000,500,200,100])
const change = (Math.floor(Math.random() * (5000 - 10)) + 10) * 100
const coins = []

greedy(coinsSet, change, coins)

驴Hay que tener un Arduino para tomar el curso de Fundamentos de Desarrollo de Hardware con Arduino?