Principal › Foros › PC: Scene, Homebrew, OpenSource y Software › Programacion › Tecnicas de programación y otros lenguajes

Ayuda con algoritmo php

Sáb, 2012-01-21 20:06 — doseuros

Muy buenas a todos! Me ha surgido un problema con un código y esperaba que alguien me pudiera ayudar con esto.

A ver, el objetivo es programar un cajero automático, como el de los bancos. A partir de una cantidad introducida por el usuario, éste la devuelve con el menor número de billetes posible. El problema surge al cambiar la disponibilidad de ciertas cantidades (por ejemplo, que de todo tipo de billetes salvo de 200€).

No encuentro una forma de expresar ésto de forma matemática. Por el momento, esto es lo que tengo:

<?

$x=0;

$n=$_POST['cantidad'];

if($_POST['500']==true){$x=$x+1;$moneda[$x]='B500';$valor[$x]=500;}

if($_POST['200']==true){$x=$x+1;$moneda[$x]='B200';$valor[$x]=200;}

if($_POST['100']==true){$x=$x+1;$moneda[$x]='B100';$valor[$x]=100;}

if($_POST['50']==true){$x=$x+1;$moneda[$x]='B50';$valor[$x]=50;}

if($_POST['20']==true){$x=$x+1;$moneda[$x]='B20';$valor[$x]=20;}

if($_POST['10']==true){$x=$x+1;$moneda[$x]='B10';$valor[$x]=10;}

for ($p=1;$p<=$x;$p=$p+1)

 {while ($valor[$p]<=$n)

     {$cambio[$p]=$cambio[$p]+1;

       $n=$n-$valor[$p];

     }

 }

for ($p=1;$p<=$x;$p=$p+1) {print $moneda[$p] ; print ":"; print $cambio[$p];print "---";}

?>

dónde $n es la cantidad a entregar y $cambio, la cantidad de cada billete.

 

Muchas gracias por vuestro tiempo y si alguien cuenta con una solución, aunque sea pseudocódigo, me será de mucha ayuda.

‹ error en llamada de funciones(java) [AYUDA POR FAVOR]Pacman NetBeans ›

Anuncios Google

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Sáb, 2012-01-21 21:23 — joserc87
Coder
Imagen de joserc87

Pseudo código

No se PHP, solo C++, Java y algo de Python, así que no te puedo ayudar diréctamente en PHP. Sin embargo el algoritmo es muy sencillo:

# En billetes vamos a poner, por orden decreciente, qué tipo de billetes tenemos
billetes={500, 100, 50, 20, 10, 5}
i=0;
j=0;# J va a iterar sobre el cambio
while (n>5){
  if (n>billetes [i]){
    n-=billetes[i];
    cambio[j]=billetes[i];
  }else{
    i=i+1;
  }
}

Al final, te podrían sobrar, por ejemplo, 4 euros, que no se pueden pagar con billetes. Por eso es lo del while(n>5) y no while(n!=0).

No se si te he ayudado. Espero que sí.

Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

Lun, 2012-01-23 17:26 — doseuros
Imagen de doseuros

Gracias, pero de hecho, el

Gracias, pero de hecho, el algoritmo que me presentas es muy similar al que escribi en el post. El fallo en ambos viene en casos como el siguiente:

billetes={200, 50, 20}

n=210

 

Como podras comprobar, en un caso como el anterior, cuya respuesta seria 3x50 + 3x20, el programa responde 1x200, y los 10 de resto desaparecen.

Gracias por tu atención y tiempo de todos modos ;)

Mar, 2012-01-24 18:16 — joserc87
Coder
Imagen de joserc87

No había caido.

Pues no lo había pensado, pero tienes razón. Para sacarlo hay que complicarse un poco más la vida con recursividad y tal. Te lo pongo en python porque es como lo he escrito. Esta vez no lo he hecho de cabeza, así que me he asegurado que funciona:

def calcularSuma (cambio):
    suma=0
    for c in cambio:
        suma += c
    return suma
 
# Devuelve el mejor de 2 cambios
def mejor (cambio0, cambio1, suma0, suma1):
    if suma0>suma1 or (suma0==suma1 and len(cambio0)<=len(cambio1)):
        return (cambio0, suma0)
    else:
        return (cambio1, suma1)
 
# Devuelve el mejor de 3 cambios
def mejorCambio (cambio0, cambio1, cambio2):
    sum0=calcularSuma (cambio0)
    sum1=calcularSuma (cambio1)
    sum2=calcularSuma (cambio2)
 
    (c,s)=mejor (cambio0, cambio1, sum0, sum1)
    (c2,s2)=mejor (c, cambio2, s, sum2)
    return c2
 
# Calcula el cambio optimo con los billetes disponibles
def calcularCambio (billetes, n):
    cambio=[]
    if n<0:
        cambio=[]
    elif len(billetes)==1:
        billete = billetes[0]
        while n>=billete:
            cambio.append(billete)
            n-=billete
    else:
        cambio0=[]
        cambio1=[]
        if (billetes [0]<=n):
            cambio0=calcularCambio (billetes [0:], n-billetes[0])+[billetes [0]]
            cambio1=calcularCambio (billetes [1:], n-billetes[0])+[billetes[0]]
        cambio2=calcularCambio (billetes [1:], n)
        cambio = mejorCambio (cambio0, cambio1, cambio2)
    return cambio
 
billetes=[200, 50, 20]
cambio = calcularCambio(billetes, 210)
print cambio

Para 210 me devolvería [50, 50, 50, 20, 20, 20]

No creo que tengas mucho problema en entender el código, aunque no sepas python. Es bastante simple (de hecho yo hace unas semanas no sabía nada).

Saludos

Be pointer my friend...

Dennis Ritchie. Padre de C y cocreador de UNIX.

R.I.P.

 

Jue, 2012-01-26 18:00 — doseuros
Imagen de doseuros

Me voy a tomar mi tiempo para

Me voy a tomar mi tiempo para analizar el código y traducir-lo a PHP. Gracias por tu respuesta y perdón por la demora, estos dias estoy un poco ocupado con los exámenes. 

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.