Divina proportione …
1:a=a:b
0,618
Prof. Fabrizio Camuso
www.camuso.it
Diap. 1
In geometria …
Il rettangolo aureo
Prof. Fabrizio Camuso
www.camuso.it
Diap. 2
In geometria …
Pentagono e pentangolo
Prof. Fabrizio Camuso
www.camuso.it
Diap. 3
In geometria …
Spirale aurea
Prof. Fabrizio Camuso
www.camuso.it
Diap. 4
Nella natura !!
Spirale aurea
• fasi di sviluppo di esseri viventi
• conchiglie
• parte inferiore onde marine
• corna, zanne, becchi, artigli
• galassie
• coda comete
• posizione ombelico
Prof. Fabrizio Camuso
www.camuso.it
Diap. 5
Fibonacci - 1
0 1 1 2 3 5 8 13 21 34 …
Prof. Fabrizio Camuso
www.camuso.it
Diap. 6
Fibonacci - 2
Sulla testa di un tipico girasole, per esempio, il numero delle
spirali rientra molto spesso in questo schema: 89 spirali che si
irradiano ripide in senso orario; 55 che si muovono in senso
antiorario e 34 che si muovono in senso orario ma meno ripido.
Questi sono tre numeri adiacenti delle sequenza di Fibonacci.
Il più grande girasole che si sia mai conosciuto
aveva 144, 89 e 55 spirali.
Prof. Fabrizio Camuso
www.camuso.it
Diap. 7
Fibonacci - 3
In molte specie vegetali, prime fra tutte le Astaracee (girasoli,
margherite, ecc.), il numero dei petali di ogni fiore è di solito un
numero di Fibonacci, come 5, 13, 55 o perfino 377, come nel caso
della diaccola.
Prof. Fabrizio Camuso
www.camuso.it
Diap. 8
Fibonacci - 4
In molte specie vegetali, prime fra tutte le Astaracee (girasoli,
margherite, ecc.), il numero dei petali di ogni fiore è di solito un
numero di Fibonacci, come 5, 13, 55 o perfino 377, come nel caso
della diaccola.
E le pigne ???
Prof. Fabrizio Camuso
www.camuso.it
Diap. 9
Fibonacci - 5
Le foglie sono disposte sui rami in modo tale da non coprisi l’una
con l’altra per permettere a ciascuna di esse di ricevere la luce del
sole. Se prendiamo come punto di partenza la prima foglia di un
ramo e passiamo di foglia in foglia in senso orario o antiorario, il
numero di giri che compiremo prima di trovare una foglia sopra
quella di partenza corrisponde sempre ad un numero di Fibonacci.
Partendo da una foglia qualunque,
dopo uno, due, tre o cinque giri dalla
spirale si trova sempre una foglia
allineata con la prima. a seconda
delle specie, questa sarà la seconda,
la terza, la quinta, l'ottava o la
tredicesima foglia.
Prof. Fabrizio Camuso
www.camuso.it
Diap. 10
Fibonacci – 6
I NUMERI DI FIBONACCI E LA BORSA DI MILANO
Un’applicazione moderna dei numeri di Fibonacci si può
riscontrare presso la borsa azionistica di Milano. Prendendo
spunto da Leonardo Fibonacci da Pisa, uno dei più grandi
protagonisti della storia della matematica, Ralph Elson Elliot
elaborò una precisa teoria di previsione dei mercati finanziari con
la quale in tempi recenti sono stati anticipati i più grandi rialzi e i
più grandi crolli di borsa. Usando le onde di Elliot ed i numeri di
Fibonacci, il docente universitario G. Migliorino ha previsto con
incredibile precisione il punto minimo del drammatico ribasso
dell’estate ‘98. .
Prof. Fabrizio Camuso
www.camuso.it
Diap. 11
Fibonacci – 7
I NUMERI DI FIBONACCI NEL PROCESSORE PENTIUM
I numeri di Fibonacci sono utilizzati anche nel sistema informatico
di molti computer. In particolare vi è un complesso meccanismo
basato su tali numeri, detto "Fibonacci heap" che viene utilizzato
nel processore Pentium della Intel per la risoluzione degli
algoritmi.
Prof. Fabrizio Camuso
www.camuso.it
Diap. 12
Fibonacci – 8
Anche la musica non sfugge al fascino del rapporto aureo.
Anzitutto le note: in una scala completa (compreso il do della
scala successiva) i rapporti fra le note corrispondono molto
precisamente ai numeri di Fibonacci …
Un ambiente d' ascolto, ma anche una cassa acustica, minimizzerà
le risonanze se le dimensioni sono in rapporto aureo tra loro.
Ancora oggi la sezione aurea è ampliamente utilizzata: le
dimensioni standard di carte di credito, tessere telefoniche, badge
per ogni applicazione, corrispondono (salvo tolleranze di
fabbricazione) al rettangolo aureo.
Prof. Fabrizio Camuso
www.camuso.it
Diap. 13
Fibonacci – 9
George Cardas decide di sfruttare il concetto di rapporto aureo per
la costruzione di cavi audio ad alte prestazioni e questa trovata e'
protetta da ben due brevetti (US Pat. 4.628.151 e 4.980.517).
Prof. Fabrizio Camuso
www.camuso.it
Diap. 14
Fibonacci
(Versione Iterativa)
dueIndietro
dueIndietro
if (num==1)
return 0;
unoIndietroelse
if (num==2)
return 1
else;
{
dueIndietro=0; unoIndietro=1;
for (int i=3; i<=num; i++)
{
prossimo=unoIndietro+dueIndietro;
dueIndietro=unoIndietro;
unoIndietro=prossimo;
}
return prossimo
}
www.camuso.it
Diap. 15
}
0 1 1 2 3 5 8 13 …
0 1 1 2 3 5 8 13 ? …
prossimo
prossimo
Prof. Fabrizio Camuso
/* versione iterativa */
int fib_ite(int num)
{
int i=0, prossimo=0,
unoIndietro=0,dueIndietro=0;
Fibonacci
(Versione Ricorsiva)
/* versione ricorsiva */
int fib_ric(int num)
{
if (num==1)
Base della
return 0;
ricorsione
else
if (num==2)
return 1;
else
return fib_ric(num-2)+fib_ric(num-1);
}
Prof. Fabrizio Camuso
www.camuso.it
Niente
Var locali !!
Passo
ricorsivo
Diap. 16
La torre di Hanoi - 1
* Di cosa si tratta …(videolezione ‘Ricorsione’ - minuto19.45)
Prof. Fabrizio Camuso
www.camuso.it
Diap. 17
protected void iterativeSolve(int n, int da, int a, int per) {
int[] pioli = {da, a, per};
int dim;
int n_mvs;
int from;
int to;
for (int i = 0; i < mvlist.length; i++) {
dim = calcDim(i + 1);
n_mvs = i / (int)Math.pow(2, dim) + 1 / 2;
if ((n - dim + 1) % 2 == 1) {
from = (int)(n_mvs % 3);
to = (from + 1) % 3;
} else {
from = (int)(-(n_mvs % 3 - 3) % 3);
to = (from + 2) % 3;
}
mvlist[i] = new HanoiMove(pioli[from], pioli[to]);
}
}
private int calcDim(int mv) {
int pos = 0;
while (mv > 0) {
pos++;
if (mv % 2 == 1) mv = 0;
else mv /= 2;
}
return pos;
Prof. Fabrizio Camuso
}
La torre di Hanoi – 2
(versione iterativa)
??????
www.camuso.it
Diap. 18
La torre di Hanoi – 3
(versione ricorsiva)    
void move(int N, int start, int final, int temp)
{
if (count > 0)
Passo
{ move(N-1,start,temp,final);
ricorsivo
cout << "Muovi da {0} a {1}\n“ << start << final;
Passo
move(N-1,temp,final,start);
ricorsivo
}
}
Dov’è la
base della ricorsione ?
Prof. Fabrizio Camuso
www.camuso.it
Diap. 19
Strutture ad albero – 1
Radice (root)
arco
Struct Nodo
{
string info;
sx: Nodo *;
dx: Nodo *;
}
nodo
figlio
foglia
fratelli
Prof. Fabrizio Camuso
www.camuso.it
Diap. 20
Strutture ad albero – 2
void stampa(Nodo * albero)
{
if (albero!=null)
{
stampa(albero->sx);
StampaAlbero(inizio)
cout << albero->info << endl;
stampa(albero->dx)
}
StampaAlbero(inizio^.dx)
StampaAlbero(inizio^.sx)
}
StampaAlbero(inizio^.dx^.dx)
StampaAlbero(inizio^.sx^.sx)
…
…
StampaAlbero(nil)
Prof. Fabrizio Camuso
StampaAlbero(nil)
StampaAlbero(nil)
www.camuso.it
Diap. 21
Altre applicazioni
algoritmi importanti pronti
per le architetture parallele
int binsearch(int a[], int sx, int dx, int el)
{ int x;
if (dx < sx)
return -1;
x = (dx + sx)/2;
if (el < a[x])
return binsearch(a,sx,x-1,el);
else
if (el == a[x])
return x;
else
return binsearch(a,x+1,dx,el); }
Prof. Fabrizio Camuso
www.camuso.it
Diap. 22
Altre applicazioni - quicksort
Prof. Fabrizio Camuso
www.camuso.it
Diap. 23
Altre applicazioni – XML parsing
Prof. Fabrizio Camuso
www.camuso.it
Diap. 24
Altre applicazioni – backtracking
Una tecnica classica consiste nell'esplorazione di
strutture ad albero e tenere traccia di tutti i nodi e i
rami visitati in precedenza, in modo da poter tornare
indietro al più vicino nodo che conteneva un
cammino ancora inesplorato nel caso che
la ricerca nel ramo attuale non abbia successo.
Esiste addirittura un famoso linguaggio di
programmazione usatissimo per risolvere problemi di
intelligenza artificiale basato interamente per il suo
funzionamento sul backtracking: il prolog
Prof. Fabrizio Camuso
www.camuso.it
Diap. 25
Riassumendo …
La base della ricorsione: è il caso più semplice, quello per il quale
sappiamo subito ‘calcolare’ il risultato. Quello a cui il meccanismo
ricorsivo tenta di ricondursi un poco alla volta, passo dopo passo.
Il passo ricorsivo: quando non siamo di fronte al caso più semplice
dobbiamo tentare di esprimerlo attraverso una ‘formula’ che
richiama lo stesso sottoprogramma che stiamo scrivendo ma con
argomenti semplificati che ci avvicinano al caso che rappresenta la
base della ricorsione
Prof. Fabrizio Camuso
www.camuso.it
Diap. 26
Fattoriale …
1 se N =0
Fatt( N ) =
N * Fatt(N-1) se N>0
Prof. Fabrizio Camuso
www.camuso.it
Diap. 27
xy , con x e y interi positivi
1 se y =0
XallaY(x,y) =
x * XallaY(x,y-1) se y>0
Prof. Fabrizio Camuso
www.camuso.it
Diap. 28
X*Y
x se y =1
XperY(x,y) =
x + XperY(x,y-1) se y>0
Prof. Fabrizio Camuso
www.camuso.it
Diap. 29
Fibonacci
0 se N =1, 1 se N=2
Fib(n) =
Fib(N-2)+Fib(N-1) se N>2
Prof. Fabrizio Camuso
www.camuso.it
Diap. 30