04 Abril, 2020, 11:58 *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Función recursiva en C  (Leído 1503 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Springer
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 127


Ver Perfil
« : 29 Junio, 2009, 09:43 »

¡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:
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.
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #1 : 29 Junio, 2009, 11:59 »

Hola

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

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

 donde por [texx]arreglo+1[/texx] 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.
En línea
Springer
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 127


Ver Perfil
« Respuesta #2 : 30 Junio, 2009, 13:38 »

¡Gracias!

Sí, es como vos decís.

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

Código:
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:
void cambio_p(int importe, int *monedas, int dim, int *ret)

Hasta ahora, llevo hecho lo siguiente, pero no funciona:

Código:
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!
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 46.144


Ver Perfil
« Respuesta #3 : 03 Julio, 2009, 07:37 »

Hola

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

Código:
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.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!