Corso di Laboratorio di Informatica A

Soluzione (con controlli sull'input)

#include <stdio.h>

int div(int x, int y){
     if (x>=y) return 1+div(x-y,y);
     else return 0;
}
 

main() {
     int x,y,ris;

     do{
          printf("Inserire dividendo: ");
          scanf("%d",&x);
     }while (x<0);

     do{
          printf("Inserire divisore: ");
          scanf("%d",&y);
     }while (y<1);

     ris = div(x,y);
     printf("%d/%d = %d",x,y,ris);
}
 

Versione tail ricorsiva:

int div_tail(int x, int y, int v, int k)
{
 if (k<=x){
  v = v + 1;
  k = k + y;
  return div_tail(x,y,v,k);
 }
 else return v;
}

int div(int x, int y){
     return div_tail(x,y,0,y);
}
 
 

Soluzione ricorsiva

int pot(int m, int n){
     if (n>0) return m*pot(m,n-1);
     else return 1;
}
 

Soluzione tail ricorsiva

int pot_tail(int m, int n, int v, int k)
{
     if (k<=n){
      v = v * m;
      k++;
      return pot_tail(m,n,v,k);
     }
     else return v;
}
 

int pot(int m, int n){
    return pot_tail(m,n,1,1);
}
 
 

Soluzione

float potenza(float M, int N)
{   float P;
    if (N==0)
        { return 1; }
    else
        if (N%2 == 0) /* Se N è pari */
            { P = potenza(M,N/2);
              return P*P; }
        else
            { return potenza(M,N-1)*M; }
}

La funzione è ricorsiva, ma non tail ricorsiva, infatti dopo la chiamata ricorsiva devono ancora essere effettuati dei prodotti (sia nel caso di N pari sia in quello di N dispari). È possibile scriverla in maniera tail ricorsiva, osservando che, nella funzione precedente, vengono calcolate tutte le potenze del tipo M^(2i), per tutti gli i tali che  2i<N ovvero M1, M2, M4, M8, ... Aggiungeremo quindi due parametri. P rappresenta la potenza calcolata fino a questo momento; P2 rappresenta la potenza M^(2i) accumulata fino a questo momento. Se N è pari, allora dovremo moltiplicare P per P2.

float potenza_tail(float M, int N, float P, float P2)
{
    if (N==0)
        { return P; }
    else
        if (N%2 == 0)
            { P2=P2*P2;
              return potenza_tail(M,N/2,P,P2);
            }
        else
            { P = P*P2;
              return potenza_tail(M,N-1,P,P2);
            }
}

float potenza_2(float M, int N)
{
    return potenza_tail(M,N,1,M);
}

Visto che è stato possibile scriverla in maniera tail ricorsiva, è evidentemente possibile scriverla anche in maniera iterativa. Infatti un compilatore che esegue l'ottimizzazione tail effettuera` il calcolo in maniera iterativa. In questo caso, dovremo essere noi a scrivere il ciclo corrispondente. Prendiamo una variabile i che ci servira` come indice e che fara` le veci del parametro N nella versione tail ricorsiva.

float potenza_non_ric(float M, int N)
{ float P, P2;
  int i;

  i = N;
  while (i>0)
   { if (i%2 == 0)
          { P2=P2*P2;
            i = i/2;
          }
      else
          { P = P*P2;
            i = i-1;
          }
   }
}
 
 
 
 
 

Soluzione

#include <stdio.h>
#include <math.h>
#define PI 3.14159

int fatt(int n){
     if (n>1) return n*fatt(n-1);
     else return 1;
}
 

double sin_taylor(double x, int n){
     if (n>=0)
        return ( pow(-1,n)*pow(x,2*n+1)/fatt(2*n+1) + sin_taylor(x,n-1) );
     else return 0;
}
 

main()
{
     double x,ris;
     int n;

     do{
          printf("Inserire angolo in radianti: ");
          scanf("%lf",&x);
     }while (x<0 || x>=2*PI);

     printf("Inserire grado del polinomio: ");
     scanf("%d",&n);

     ris = sin_taylor(x,n);

     printf("sin_taylor(%lf,%d) = %lf\n",x,n,ris);
     printf("sin(%lf) = %lf",x,sin(x));
}