Programmi C/C++ - prof.Claudio Maccherani

Programmi C / C++ - prof. Claudio Maccherani - Perugia - 2008
Esempi di Funzioni RICORSIVE (Fattoriale, Ricerca Binaria)

  /* "prg_c_ricorsione.cpp" - Fattoriale e Ricerca Binaria (con Ricorsione e Iterazione)
    prof.Claudio Maccherani - Perugia - 2009  */

 #include <iostream>
 #include <stdlib.h>
 #include <time.h> 
 #include <windows.h> 
 
 using namespace std;

 int N,v[21],acc;

 void gotoRC(short r, short c) { COORD pos = {c, r};
      SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos); }
 
 long int FattRic(int n) { // Fattoriale con Ricorsione
   if (n <= 1) return 1;
   else        return n * FattRic(n-1); }
	
 long int FattIte(int n) { // Fattoriale con Iterazione (For/While/Do-While)
   int x = 1;
   for(int i=1;i<=n;i++) x = x*i;
   return x; }

 void Riempi_vettore() { // riempimento e ordinamento vettore
   int x;
   for(int i=1;i<N;i++) v[i] = rand() %1000 +1;
   for(int i=1;i<N-1;i++)
      for(int j=i+1;j<N;j++)
         if (v[i]>v[j]) { x=v[i]; v[i]=v[j];v[j]=x; }		
      for(int i=1;i<N;i++)
         { gotoRC(i+1,1); cout<<i; gotoRC(i+1,4); cout<<" - "<<v[i];}
   }

 int Ric_Bin_Ric(int x,int i1,int i2) { // Ricerca Binaria con Ricorsione
   int j; if (i1 > i2) return 0;       // posizione di ‘x’ se esiste oppure 0
   j = (i1+i2)/2; gotoRC(j+1,15); cout << j;
   if (v[j] == x)	return j;
   if (x < v[j]) Ric_Bin_Ric(x,i1,j-1);
   else          Ric_Bin_Ric(x,j+1,i2); }	
	
 int Ric_Bin_Ite(int x,int i1,int i2) { // Ricerca Binaria con Iterazione
   int i,n=0; acc=0;                   // posizione di ‘x’ se esiste oppure 0
   if (x<v[i1] || x>v[i2]) return 0;   // 'x' non è presente in 'v[]'
   while(i1 <= i2) {
      i = (i1+i2)/2; n++; gotoRC(i+1,10+n*10); cout << "<-"<<i; acc++;
      if (v[i] == x) return i;
      if (v[i] > x)  i2 = i-1;
      else           i1 = i+1;
      }
   return 0; }
 
 int main() { // programma principale
   int i,n,scelta; N = 21;
   srand(time(0)); 
   do { system("cls");
      cout << "\n esempi di RICORSIONE  (prof. Claudio Maccherani)\n\n\n";
      cout << " 1 - fattoriale\n\n 2 - Ricerca Binaria\n\n 0 - fine\n\n";
      cout << "     scegli ... "; cin >> scelta;
      if (scelta == 1) { 
         system("cls"); cout << "\n FATTORIALE\n\n";
         cout<<"    Fattoriale di "; cin>>n;
         cout<<" il Fattoriale di "<<n<<" e' "<<FattRic(n)<<" (RICORS)\n";
         cout<<" il Fattoriale di "<<n<<" e' "<<FattIte(n)<<" (ITERAZ)\n\n";
         system("pause");		
      }
      if (scelta == 2) { 
         system("cls"); cout << " RICERCA BINARIA\n";
         Riempi_vettore();
         gotoRC(0,20); cout<<"Dato da cercare: "; cin >> n;
         i = Ric_Bin_Ric(n,1,N-1);
         gotoRC(0,45); 
         if (i>0) cout<<"Dato trovato in posizione "<<i<<"\n";
         else     cout<<"Dato NON trovato\n";
         gotoRC(23,1); cout<<"Fatta con RICORSIONE - ";system("pause");		
         i = Ric_Bin_Ite(n,1,N-1);
         gotoRC(0,45);
         if (i>0) cout<<"Dato trovato in posizione "<<i<<"\n"; 
         else     cout<<"Dato NON trovato\n";
         gotoRC(23,1); cout<<"Fatta con ITERAZIONE - "<<acc<< " ACCESSI ! - ";
         system("pause");		
      }
   }
 while(scelta != 0);	
 return 0; }