NGI.Home > Forum
  EOLO HOME  OFFERTE INTERNET WIRELESS EOLO  FORMULA ADSL
   
   
WEBMAIL
   
 
  > Register  
  > FAQ  
  > Members List  
 
  > Calendar  
  > Today's Posts  
   
 

Go Back   NGI Forum > Tech & Tech > Developer's Zone

Reply
 
Thread Tools Rate Thread
Old 20th December 2010, 13:57   #1
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
[Impariamo il C] Lezione 11

Buongiorno.

Nelle puntate precedenti del corso collaborativo di programmazione:
  1. installazione dell'IDE, cenni di architettura degli elaboratori
  2. sintassi del C, programmazione strutturata
  3. ancora sulla sintassi, i tipi di dato, le variabili
  4. variabili parte seconda: gli array
  5. introduzione delle funzioni
  6. operatori aritmetici e logici
  7. costrutti di selezione
  8. costrutti di iterazione
  9. ancora sull'iterazione
  10. array multipli e struct
In questo capitolo:
  • la ricorsione

Ricorsione

Nella lezione 5 abbiamo visto le funzioni, analizzando il passaggio di parametri e il valore di ritorno.

Naturalmente, abbiamo visto nuovi tipi di dato in seguito (e in particolare le struct); va da sé che è possibile ritornare anche questi tipi di dato, e non è raro che delle funzioni ritornino proprio delle strutture dati o degli array.


Alle volte, per come sono strutturati i nostri parametri, sarebbe interessante poter processare solo un "pezzettino" del nostro dato in ingresso e poi ridare in pasto alla funzione quello che avanza.

Ad esempio, siamo d'accordo che visualizzare la stringa "hello world!" è equivalente alla scomposizione in questi due sottoproblemi:
  1. stampare la prima lettera ("h")
  2. stampare il resto della stringa

Dunque, se avessimo una funzione intelligente di questo tipo (pseudocodice):

Code:
super_print( stringa ) {

   c = primo_carattere_stringa( stringa ) 
   resto = resto_della_stringa( stringa ) 

   stampa( c )

   super_print( resto )

}
Ebbene, questo programma funziona benissimo dal punto di vista concettuale: carattere per carattere stampiamo tutto, fino ad esaurire i caratteri in stringa. "L'esaurimento" avviene richiamando la funzione in cui ci troviamo con una istanza più piccola del problema.

Ovviamente, chi ha seguito il corso con attenzione finora sa che una stringa è un array di caratteri, di cui magari non sappiamo la dimensione. Il problema può essere ovviato passando due numeri alla funzione: la posizione cui siamo arrivati e la lunghezza totale della stringa. Alla luce di questo, guardiamo il codice in C:

Code:
void super_print( char stringa[] , int posizione , int dimensione )  {
   
    printf( "%c", stringa[posizione] );

    /* chiamata ricorsiva */
    super_print( stringa, ++posizione , dimensione );

}
Se ragionate su questo codice, vedete che è perfettamente logico e consistente. La funzione può essere richiamata dentro sé stessa perché è stata dichiarata prima del suo utilizzo.

Tuttavia, dovrebbe suonarvi un campanellino d'allarme. Perché il programma dovrebbe fermarsi? noi continuiamo a incrementare la posizione e potremmo finire fuori dai limiti dell'array! Servirà quindi un caso base, ovvero un controllo di qualche tipo che ci avvisa quando l'esecuzione è completata

Code:
void super_print( char stringa[] , int posizione , int dimensione )  {

    /* caso base */   
    if (posizione>dimensione) return;

    printf( "%c", stringa[posizione] );

    super_print( stringa, ++posizione , dimensione );

}
Dunque per utilizzare questa nuova versione di stampa con la stringa "hello world" scriveremmo nel main

Code:
super_print( "hello world", 0, 11);
L'esempio è volutamente banale, perché l'argomento ricorsione è mostruosamente complesso, attraversa l'informatica teorica, allaga l'intelligenza artificiale e sfocia pure nella filosofia. Farò ora un esempio di come la ricorsione può rendere molto semplici problemi che, coi costrutti iterativi, risultano ostici.

Rullo di Tamburi: la successione di Fibonacci.

Leonardo de' Bonacci, figlio del facoltoso mercante Guglielmo, era un matematico pisano.

Un giorno il padre gli disse "sentimi bene fijolo. t'ho fatto studiare in giro pe' lo mondo, t'ho mandato in arabia a leggere gli scritti di Muhammad ibn Musa al-Khwarizmi (l'inventore degli algoritmi), smetti di fare i' bischero e trovami un sistema per hapì 'uanto mi si riproduhono i honigli che nun ce la si fa più, nun ce la si fa".

I conigli erano davvero un problema, perché diventano fertili dopo un mese, e producono una nuova coppia di figli già al secondo mese. Dopo pochi mesi, i Bonacci erano sommersi di pelo.


Messa in termini matematici, la questione è così ponibile: sapendo la quantità di conigli un mese fa, e la quantità questo mese, la loro somma ci da la quantità di conigli il mese prossimo.

F(t) = F(t-1) + F(t-2)

Dunque, partendo dall'arrivo di una coppia di conigli ( t=0 )

1

il mese dopo (t=1) avremo una coppia fertile

1

il mese successivo (t=2) si avrà la coppia di figli più la coppia di partenza

1 + 1 = 2

Il mese dopo (t=3) sarà uguale a (t=2) + (t=1) e cioé

2 + 1 = 3

e così via. Si osserva che la successione è

1 1 2 3 ...

cioè per fare il nuovo numero devo sommare i due precedenti (2+3 = 5)

1 1 2 3 5 ...


La domanda che si fece il Fibonacci fu: quanti conigli ho dopo un anno? ovvero, qual è il numero di conigli quando t=12? Riflettiamoci: è possibile determinarlo direttamente? Ritorneremo su questa domanda più avanti, nel frattempo osserviamo che

F(12) = F(11)+F(10)

ovvero, se sapessimo quanto vale F ai tempi 11 e 10 potremmo risolvere F(12)! Ma questa è esattamente la definizione ricorsiva che abbiamo introdotto all'inizio della lezione, stiamo risolvendo un problema scomponendolo in problemi più piccoli e richiamando su di essi la stessa funzione.


Esercizio 1: definire (a parole) il/i caso/i base della funzione ricorsiva di Fibonacci.

Esercizio 2 (media difficoltà): implementarlo.

Esercizio 3 (facoltativo ma istruttivo): implementare Fibonacci in maniera iterativa
__________________
Lode a Bacco, in saecula saeculorum.
Emergent

Last edited by Arësius; 22nd December 2010 at 00:08.
Arësius is offline   Reply With Quote
Old 20th December 2010, 14:34   #2
nanomad
Dietro le sbarre
 
nanomad's Avatar
 
Join Date: Apr 2005
Location: Papia (olim Ticinum)
Posts: 5,221
In tema di Fibonacci e per alleggerire un po' la lezione:
__________________
Rivuoi i video nel forum? Usa questa estensione (chrome)
Source & firefox version
"(...) the three great virtues of a programmer: laziness, impatience, and hubris." -- LarryWall
nanomad is offline   Reply With Quote
Old 20th December 2010, 14:38   #3
Slim Babu
Continue Testing
 
Slim Babu's Avatar
 
Join Date: Sep 2009
Posts: 1,258
Slim Babu is offline   Reply With Quote
Old 20th December 2010, 17:19   #4
Mokujin
Only Luck & Ping
 
Mokujin's Avatar
 
Join Date: Jun 2001
Location: AnyWhere
Posts: 627
Salve, esco dalla nuvoletta del lurker per cimentarmi nell'esercizio 3

Spoiler:

Code:
int fibonacci(int t) {
   int res = 1; // fibonacci(0)
   int back = 1; //fibonacci(1)
   int i=0;

   for(i=2;i<=t;i++) {
       int temp = res;

       res += back;
       back = temp;
   }

   return res;

}




Saluti!


p.s. perdonate eventuali cavolate, è una vita che non scrivo C, domani leggo le correzioni
__________________
Moku is a crow.
In love with Final Fantasy XI .. no more.

Last edited by Mokujin; 21st December 2010 at 09:07. Reason: Added +=
Mokujin is offline   Reply With Quote
Old 20th December 2010, 17:33   #5
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
va benissimo (a parte la variabile i dichiarata nel for, che in C non va fatto). me lo metti sotto spoiler?
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arësius is offline   Reply With Quote
Old 20th December 2010, 17:43   #6
nanomad
Dietro le sbarre
 
nanomad's Avatar
 
Join Date: Apr 2005
Location: Papia (olim Ticinum)
Posts: 5,221
Aresio hai fatto un po' di casini con gli indici negli esempi
__________________
Rivuoi i video nel forum? Usa questa estensione (chrome)
Source & firefox version
"(...) the three great virtues of a programmer: laziness, impatience, and hubris." -- LarryWall
nanomad is offline   Reply With Quote
Old 20th December 2010, 18:22   #7
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
dimmi quali che correggo!
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arësius is offline   Reply With Quote
Old 20th December 2010, 18:36   #8
nanomad
Dietro le sbarre
 
nanomad's Avatar
 
Join Date: Apr 2005
Location: Papia (olim Ticinum)
Posts: 5,221
Tipo tutti

Code:
    printf( "%c", stringa[i] );
Che cavolo è i?
__________________
Rivuoi i video nel forum? Usa questa estensione (chrome)
Source & firefox version
"(...) the three great virtues of a programmer: laziness, impatience, and hubris." -- LarryWall
nanomad is offline   Reply With Quote
Old 20th December 2010, 19:04   #9
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
ah lol, per rendere più chiaro il codice ho sostituito "i" con "posizione" volo!
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arësius is offline   Reply With Quote
Old 21st December 2010, 09:07   #10
Mokujin
Only Luck & Ping
 
Mokujin's Avatar
 
Join Date: Jun 2001
Location: AnyWhere
Posts: 627
Quote:
Originally Posted by Arësius View Post
va benissimo (a parte la variabile i dichiarata nel for, che in C non va fatto). me lo metti sotto spoiler?

fatto (e corretto l'errore )
__________________
Moku is a crow.
In love with Final Fantasy XI .. no more.
Mokujin is offline   Reply With Quote
Old 21st December 2010, 19:33   #11
Pier4R
Ex falso quodlibet
 
Pier4R's Avatar
 
Join Date: Jul 2004
Location: equgpbc.r2.Frisia
Posts: 18,664
**(ma avevo scritto alt+255 -.- )
__________________
Ngi the e.FlameeXperience .Fe ! ngi.agorà@twitter (sottoscrivi per essere incluso)
You must play online: warSow EnemyTerritory + etpro quake 4 + q4max & quake 3 + cpma & quakelive Teeworlds! hoi2series

Ringrazio i grammar nazi che mi fanno comprendere gli errori ; my.IL
; lettere porno
Pier4R is offline   Reply With Quote
Old 21st December 2010, 21:44   #12
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
ma ci siamo persi per strada il 90% della "classe"?
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arësius is offline   Reply With Quote
Old 21st December 2010, 22:13   #13
Pier4R
Ex falso quodlibet
 
Pier4R's Avatar
 
Join Date: Jul 2004
Location: equgpbc.r2.Frisia
Posts: 18,664
arè ancora c'è gente che rimurgina sulla lezione 10, eddai! Tu continua imperterrito!
__________________
Ngi the e.FlameeXperience .Fe ! ngi.agorà@twitter (sottoscrivi per essere incluso)
You must play online: warSow EnemyTerritory + etpro quake 4 + q4max & quake 3 + cpma & quakelive Teeworlds! hoi2series

Ringrazio i grammar nazi che mi fanno comprendere gli errori ; my.IL
; lettere porno
Pier4R is offline   Reply With Quote
Old 22nd December 2010, 00:28   #14
[En][gma]
Registered User
 
[En][gma]'s Avatar
 
Join Date: Dec 2001
Posts: 2,929
Quote:
Originally Posted by Pier4R View Post
arè ancora c'è gente che rimurgina sulla lezione 10, eddai! Tu continua imperterrito!
presente!

mi spiace ma le prime 4 lezioni ero in ferie...
ora dopo una giornata di lavoro non sempre mi viene voglia di leggere e fare esercizi...
non che abbia perso l'entusiasmo eh
solo ci metto più tempo.
__________________
.: NoS - Nitrous Oxide System :.

Last edited by [En][gma]; 22nd December 2010 at 00:29.
[En][gma] is offline   Reply With Quote
Old 22nd December 2010, 09:33   #15
uizz
Registered User
 
uizz's Avatar
 
Join Date: Jan 2010
Posts: 513
Ciao, ci sono, è che non ho avuto tempo per gli esercizi...ecco l'esercizio 2 (ammetto che ho preso qualche spunto dalla rete):

Spoiler:
Code:
int fibonacci(int x);

int main (){
    int a;
    printf("inserire numero\n");
    scanf("%d", &a);
    int y = fibonacci(a);
    printf("fibonacci = %d\n", y);
    system("pause");
    return 0;    
    
}

   int fibonacci (int x) {
       
       if (x==0 || x==1){   //caso base
          return x;
       }
       return fibonacci(x-1)+fibonacci(x-2);    //chiamata ricorsiva
       
   }


Spiegato a parole...beh il caso base è il caso finale a cui vogliamo arrivare. La prima cosa che fa la funzione è controllare se x corrisponde al caso base. Se non corrisponde prova la somma ma con dei numeri più piccoli, che se a loro volta non corrispondono vengono rimpiccioliti, così si ha più somme di più casi di sottrazione. (itagliano aiuto )
Fino ad arrivare al caso base...cioè quando ritorna ritorna la somma di 0+1 più la somma di 1+1 più la somma di 1+2 più la somma di 2+3, ecc...

Detto in parole fighe: "Ci sono chiamate ripetute della funzione finchè non si raggiunge il caso base".
uizz is offline   Reply With Quote
Reply

Bookmarks

Thread Tools
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 20:45.


Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright 1998-2014 by NGI SpA