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
-
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.
-
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++):
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:
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