Autor Tema: Función recursiva en C

0 Usuarios y 1 Visitante están viendo este tema.

29 Junio, 2009, 02:43 pm
Leído 1898 veces

Springer

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 127
  • Karma: +0/-0
  • Sexo: Masculino
¡Hola!

Este mensaje es para pedir ayuda con la implementación de una función recursiva en lenguaje C que, sin utilizar funciones ni variables auxiliares, haga lo siguiente:

- Reciba un entero que representa un importe, un arreglo de enteros que representa distintos tipos de monedas y un entero con la dimensión del arreglo.

- Retorne la cantidad de maneras en que se puede pagar el importe utilizando las monedas del arreglo.

Algunos ejemplos:

- Si recibe como importe 4, como arreglo {1, 2} y como dimensión 2, debería retornar 3, pues:
  4 = 1+1+1+1
  4 = 2+1+1
  4 = 2+2

- Si recibe como importe 2, como arreglo {1,2,3} y como dimensión 3, debería retornar 2, pues:
  2 = 1+1
  2 = 2

El prototipo sería el siguiente:

Código: [Seleccionar]
int cambio(int importe, int *monedas, int dim);
Pensé en cómo hacerla durante un largo rato, pero no puedo hallar dónde se aplica la recursión. Hice varias funciones que fueron fallidas, pues funcionaban solamente con algunos casos.

Espero que alguien pueda ayudarme.

29 Junio, 2009, 04:59 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 51,228
  • País: es
  • Karma: +0/-0
Hola

 mmmm... no me acuerdo bien de la sintaxis del C pero la fórmula recursiva podría ser esta:

\(  cambio(importe, arreglo, dimension)=cambio (importe-arreglo[1],arreglo,dimension)+cambio(importe,arreglo+1,dimension-1) \)

 donde por \( arreglo+1 \) denoto al arreglo al que hemos quitado el primer elemento.

 La idea es que dividimos el problema en los cambios que al menos llevan una moneda del primer tipo y las que no llevan ninguna de ese tipo.

 Además habrá que incluir unos condicionales para los casos límite.

Saludos.

30 Junio, 2009, 06:38 pm
Respuesta #2

Springer

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 127
  • Karma: +0/-0
  • Sexo: Masculino
¡Gracias!

Sí, es como vos decís.

Acá pongo el código, por si a alguien le interesa:

Código: [Seleccionar]
int cambio(int importe, int *monedas, int dim)
{
if(importe == 0)
return 1;

if(importe < 0 || dim == 0)
return 0;

return cambio(importe - monedas[0], monedas, dim) +
cambio(importe, monedas+1, dim-1);
}

Ahora estoy tratando de hacerla de modo que la respuesta sea almacenada en una variable. Para ello, se le pasa un puntero a la variable y la función es void (no retorna nada). Al llamar a la función, la respuesta (que antes era devuelta en su nombre) ahora es almacenada en dicha variable.

La verdad, se me está complicando de nuevo.

El prototipo sería algo así:

Código: [Seleccionar]
void cambio_p(int importe, int *monedas, int dim, int *ret)
Hasta ahora, llevo hecho lo siguiente, pero no funciona:

Código: [Seleccionar]
void cambio_p(int importe, int *monedas, int dim, int *ret)
{
if(importe == 0)
*ret = 0;
else if(importe > 0 && dim != 0)
{
int i, flag = FALSE;

for(i = 0; i < dim && !flag; i++)
if(importe == monedas[i])
flag = TRUE;

cambio_p(importe-monedas[0], monedas, i, ret);

if(importe != 0)
cambio_p(importe, monedas+1, i-1, ret);

if(flag == 1)
(*ret)++;
}
}

Si alguien tiene ganas de ayudarme, ¡gracias!

03 Julio, 2009, 12:37 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 51,228
  • País: es
  • Karma: +0/-0
Hola

 mmmm... no debiera de ser muy diferente...prueba algo así:

Código: [Seleccionar]
void cambio_p(int importe, int *monedas, int dim, int *ret)
{
if(importe == 0)
ret=ret+1;

else if(importe > 0 && dim > 0)

  {
       
                        cambio_p(importe - monedas[0], monedas, dim,ret);
                        cambio_p(importe, monedas+1, dim-1,ret);
                }
}

Revisa la sintaxis. La vairable ret debe de estar inicializada a cero al comenzar.

Saludos.