Vedi anche:
HomeWork5aa0203,
DomandeHomework5aa0203,
RisultatiHomework5aa0203.
Questa è la mia implementazione, con cui ho confrontato le vostre.
La profondità parte da 1 invece che da zero ma viene incrementata dopo, quindi fa lo stesso.
/*
HomeWork5: funzioni ricorsive
*/
#include <stdio.h>
/* struct usata da fibonacci_efficiente (versione che torna una coppia) */
typedef struct {
int last;
int prev;
} coppia;
/* array che 'ricorda' i valori calcolati (solo fino a 50) */
int memo[50] = { 0 };
int memo1[50] = { 0 };
/* prototipi delle funzioni usate */
void traccia(int x, int p);
void traccia2(int x, int y, int p);
int fattoriale(int x,int p);
int fibonacci(int x, int p);
coppia fibonacci_efficiente(int x, int p);
int fibonacci_memo(int x, int p);
int quarantadue(int x, int p);
int emme(int x, int p);
int emme_memo(int x, int p); /* ricorda la sola m */
int emme_memo_memo(int x, int p); /* ricorda sia m che g */
int GCD(int x, int y, int p);
/************************************************************************/
int main(int argc, char * argv[]) {
/* dichiarazioni */
int x = 0,
y = 0;
int prof = 1; /* profondita` */
/* controllo l'input */
if (argc>4 || argc<2)
return 1;
if (argv[1][0] != '-')
return 1;
/* leggo 2' (e 3') argomento */
if (argc>2)
x = atoi(argv[2]);
if (argc>3)
y = atoi(argv[3]);
/* seleziono la funzione a seconda del secondo carattere dell'opzione */
switch (argv[1][1]) {
case 'f':
y = fattoriale(x,prof);
printf("%d\n",y);
break;
case 'F':
y = fibonacci(x,prof);
printf("%d\n",y);
break;
case 'E':
y = fibonacci_efficiente(x,prof).last;
printf("%d\n",y);
break;
case 'A':
y = fibonacci_memo(x,prof);
printf("%d\n",y);
break;
case 'G':
if (x>y)
y = GCD(y,x,prof);
else
y = GCD(x,y,prof);
printf("%d\n",y);
break;
case 'h':
y = quarantadue(x,prof);
printf("%d\n",y);
break;
case 'v':
/* dati personali */
printf("Andrea\nSterbini\n02\n02\n1961\nsterbini@dsi.uniroma1.it\n");
break;
case 'm':
y = emme(x,prof);
printf("%d\n",y);
break;
case 'M':
y = emme_memo(x,prof);
printf("%d\n",y);
break;
case 'D':
y = emme_memo_memo(x,prof);
printf("%d\n",y);
break;
default:
return 1;
}
return 0;
}
/*************************************************************************/
void traccia(int x, int p)
{
int i;
for (i=0;i<p;i---++)
printf("*");
printf(" %d\n",x);
}
void traccia2(int x, int y, int p)
{
int i;
for (i=0;i<p;i---++)
printf("*");
printf(" %d %d\n",x,y);
}
/*************************************************************************/
int fattoriale(int x,int p)
{
traccia(x,p);
if (0==x)
return 1;
else
return x * fattoriale(x-1,p---+1);
}
/*************************************************************************/
/*
* fibonacci-ricorsiva-di-Sterbini-che-non-si-ricorda-il-caso-base
*/
int fibonacci(int x, int p)
{
traccia(x,p);
if (0==x || 1==x)
return 1;
else
return fibonacci(x-1,p---+1) + fibonacci(x-2,p+1);
}
/* questa implementazione torna i due valori F(n) e F(n-1) da cui calcola
* F(n---+1) e F(n)
* usiamo una struct 'coppia' per tornare i due valori
*/
coppia fibonacci_efficiente(int x, int p)
{
int y;
coppia c={1,1};
traccia(x,p);
if (x>1) {
c = fibonacci_efficiente(x-1,p---+1);
y = c.prev---+ c.last;
c.prev = c.last;
c.last = y;
};
return c;
}
/* questa funzione 'ricorda' i valori calcolati in modo da non doverli
* ricalcolare
*/
int fibonacci_memo(int x, int p)
{
int result = 0;
traccia(x,p);
/* se gia' l'ho calcolato lo prendo dal vettore */
if (memo[x] != 0)
return memo[x];
/* altrimenti lo calcolo nel modo standard */
if (x == 0 || x == 1)
result = 1;
else
result = fibonacci_memo(x-1, p---+1) + fibonacci_memo(x-2, p+1);
/* e mi ricordo il risultato */
memo[x] = result;
return result;
}
/*************************************************************************/
int quarantadue(int x, int p)
{
traccia(x,p);
if (0==x)
return 42;
else
return 2*x---+ quarantadue(x-1,p+1);
}
/*************************************************************************/
/*
# m(0) = 0
# m(x) = m(x-1)---+ 2*g(x)
# g(0) = 1
# g(x) = g(x-1) - 2*m(x-1)
*/
int gi(int x, int p); /* prototipo necessario per la chiamata doppiamente ricorsiva*/
int emme(int x, int p)
{
traccia(x,p);
if (0==x)
return 0;
else
return emme(x-1,p---+1) + 2 * gi(x,p+1);
}
int gi(int x, int p)
{
traccia(x,p);
if (0==x)
return 1;
else
return gi(x-1,p---+1) - 2 * emme(x-1,p+1);
}
/* versione che memorizza i risultati della sola 'm' */
int gi_memo(int x, int p)
{
traccia(x,p);
if (0==x)
return 1;
else
return gi_memo(x-1,p---+1) - 2 * emme_memo(x-1,p+1);
}
int emme_memo(int x, int p)
{
int result = 0;
traccia(x,p);
/* se gia' l'ho calcolato lo prendo dal vettore */
if (memo[x] != 0)
return memo[x];
if (0==x)
result = 0;
else
result = emme_memo(x-1,p---+1) + 2 * gi_memo(x,p+1);
memo[x] = result;
return result;
}
/* versione che memorizza i risultati sia di 'm' che di 'g' */
int gi_memo_memo(int x, int p)
{
int result = 0;
traccia(x,p);
/* se gia' l'ho calcolato lo prendo dal vettore */
if (memo1[x] != 0)
return memo1[x];
if (0==x)
result = 1;
else
result = gi_memo_memo(x-1,p---+1) - 2 * emme_memo_memo(x-1,p+1);
memo1[x] = result;
return result;
}
int emme_memo_memo(int x, int p)
{
int result = 0;
traccia(x,p);
/* se gia' l'ho calcolato lo prendo dal vettore */
if (memo[x] != 0)
return memo[x];
if (0==x)
result = 0;
else
result = emme_memo_memo(x-1,p---+1) + 2 * gi_memo_memo(x,p+1);
memo[x] = result;
return result;
}
/*************************************************************************/
/*
* Minimo Comune Multiplo calcolato ricorsivamente
* usando l'algoritmo di Eulero
*/
int GCD(int x, int y, int p) {
traccia2(x, y, p);
if (x == 0)
return y;
else
return GCD(y%x,x,p---+1);
}
--
AndreaSterbini - 26 Nov 2002