Foros aprenderaprogramar.com

Aprender a programar => C, C++, C#, Java, Visual Basic, HTML, PHP, CSS, Javascript, Ajax, Joomla, MySql y más => Mensaje iniciado por: chemitta azul en 03 de Marzo 2015, 18:27

Título: Problema del cambio de monedas (programación dinámica) resuelto en Java
Publicado por: chemitta azul en 03 de Marzo 2015, 18:27
me pueden ayudar con este ejercicio necesito hacerlo en pseudocodigo y en c++ por favor

Escriba un algoritmo que calcule el número mínimo de billetes 20, 10, 5, 1 dólares, que se necesita para cambiar un cheque. Considere que el valor del cheque es un número entero.
Título: Re:pseudocodigo
Publicado por: javi in the sky en 03 de Marzo 2015, 23:48
Hola este problema se llama típicamente "problema del cambio de monedas" y no es un problema sencillo de resolver... puedes encontrar mucha información sobre este problema en internet.

Este es el código en java (que es muy similar a c++):

Código: [Seleccionar]
public class Cambio
{
    private int[][] matrizCambio;
    private int[] vectorMonedas;
    private int cantidad;
    private int[] vectorSeleccion;

    Cambio(int cantidad, int[]  monedas){
        this.cantidad = cantidad;
        this.vectorMonedas = monedas;
        matrizCambio = calcularMonedas(cantidad, monedas);
        vectorSeleccion = seleccionarMonedas(cantidad, monedas, matrizCambio);
    }

    public int[] getVectorSeleccion(){
        return this.vectorSeleccion;
    }

    private int[][] calcularMonedas(int cantidad, int[]  monedas){

        int[][] matrizCambio = new int[monedas.length + 1][cantidad + 1];

        for (int i = 0; i < monedas.length; i++)
            matrizCambio[i][0] = 0;

        for (int j = 1; j <= cantidad; j++)
            matrizCambio[0][j] = 99;

        for (int i = 1; i <= monedas.length; i++)
            for (int j = 1; j <= cantidad; j++) {
                if (j < monedas[i - 1]) {

                    matrizCambio[i][j] = matrizCambio[i - 1][j];
                } else {

                    int minimo = 0;

                    minimo = min(matrizCambio[i - 1][j] , matrizCambio[i][j- monedas[i - 1]] + 1);
                    matrizCambio[i][j] = minimo;

                }
        }

        return matrizCambio;
    }

    private int[] seleccionarMonedas(int c, int[] monedas, int[][]tabla ){
        int i,j;
        int[] seleccion = new int[monedas.length];
        for(i = 0; i< monedas.length; i++){             seleccion[i]=0;         }         i= monedas.length;         j= c;         while(j>0){
            if(i>1 && tabla[i][j]==tabla[i-1][j]){
                i--;
            }
            else{
                seleccion[i-1]++;
                j = j - monedas[i-1];
            }
        }

        return seleccion;
    }

    private int min(int a, int b){
        if(a<b)
            return a;

        else
            return b;
    }

}

Obtención de resultados:

Código: [Seleccionar]
public class TestCambio {

    public static void main(String[] args) {
        System.out.println ("¿Cuántos billetes hacen falta para cambiar un cheque de 32?" );
        Cambio c = new Cambio(32, new int[]{20,10,5,1});

        System.out.println("Billetes de 20: "+c.getVectorSeleccion()[0]);
        System.out.println("Billetes de 10: "+c.getVectorSeleccion()[1]);
        System.out.println("Billetes de 5: "+c.getVectorSeleccion()[2]);
        System.out.println("Billetes de 1: "+c.getVectorSeleccion()[3]);
    }
}

En este ejemplo el resultado es:

¿Cuántos billetes hacen falta para cambiar un cheque de 32?

Billetes de 20: 1
Billetes de 10: 1
Billetes de 5: 0
Billetes de 1: 2

Saludos