Autor Tema: Problema del cambio de monedas (programación dinámica) resuelto en Java  (Leído 17436 veces)

chemitta azul

  • Sin experiencia
  • *
  • APR2.COM
  • Mensajes: 1
    • Ver Perfil
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.
« Última modificación: 04 de Marzo 2015, 08:24 por Alex Rodríguez »

javi in the sky

  • Avanzado
  • ****
  • Mensajes: 380
    • Ver Perfil
Re:pseudocodigo
« Respuesta #1 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

 

Sobre la educación, sólo puedo decir que es el tema más importante en el que nosotros, como pueblo, debemos involucrarnos.

Abraham Lincoln (1808-1865) Presidente estadounidense.

aprenderaprogramar.com: Desde 2006 comprometidos con la didáctica y divulgación de la programación

Preguntas y respuestas

¿Cómo establecer o cambiar la imagen asociada (avatar) de usuario?
  1. Inicia sesión con tu nombre de usuario y contraseña.
  2. Pulsa en perfil --> perfil del foro
  3. Elige la imagen personalizada que quieras usar. Puedes escogerla de una galería de imágenes o subirla desde tu ordenador.
  4. En la parte final de la página pulsa el botón "cambiar perfil".