SoluzioneHomework5aa0203 < Programmazione1/AA0506/PZ

Tags: view all tags

---++ Soluzione dell' HomeWork5aa0203
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.

----
<verbatim>
/*
    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);
}
</verbatim>
----

-- Users.AndreaSterbini - 26 Nov 2002
<!--
   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group
-->