Precedente :: Successivo |
Autore |
Messaggio |
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 25 Apr 2006 20:57 Oggetto: * QUIZ: Fibonacci e le api 2 |
|
|
Fibonacci e le api 2
Si considerino due righe adiacenti di celle esagonali di un alveare come in figura.
Si supponga che l'ape voglia raggiungere la cella I.
Calcolare il numero di differenti percorsi che l'ape può seguire per raggiungere tale cella sotto l'ipotesi che l'ape, passando da cella a cella, possa muoversi solo da sinistra verso destra (quindi, ad esempio, dalla cella E l'ape potrà passare unicamente alla cella F oppure alla cella G).
L'ultima modifica di ulisse il 01 Mag 2006 16:09, modificato 1 volta |
|
Top |
|
|
camicius Mortale pio
Registrato: 29/12/05 19:46 Messaggi: 28
|
Inviato: 27 Apr 2006 14:31 Oggetto: |
|
|
Citazione: |
Sono i numeri di fibonacci, quindi la risposta è 34.
Guardiamo questa figura
è la "mappa di connettività tra le celle" con le celle messe in fila.
che la souzione siano i numeri di fibonacci si può trovare con questo ragionamento:
i modi che ho per arrivare al nodo n-esimo sono 2:
in tutti i modi con i quali arrivo al nodo precedente, aggiungendo il salto "corto", oppure in tutti i modi con i quali arrivo al nodo precedente al precedente, aggiungendo il salto lungo.
Questo implica che sol(n)=sol(n-1)+sol(n-2).
i casi che iniziano la ricorsione sono quelli con uno e due nodi (entrambi un modo solo)
Quindi posso iniziare la ricorsione
p.s. nella figura manca il nodo iniziale. Non cambia nulla ai sensi del ragionamento fatto.
|
|
|
Top |
|
|
lordbluto Mortale adepto
Registrato: 21/01/06 12:50 Messaggi: 37
|
Inviato: 29 Apr 2006 22:13 Oggetto: il buon vecchio Fibo... |
|
|
vediamo se il buon fibo ha ragione...
Citazione: | per raggiungere la casella A(1) ovviamente c'è un unico percorso
per la B(2) sono due, A->B o direttamente B
per la C(3) sono tre, i due precedenti che portano da B a C più il passaggio A->C
per la D ovviamente sono i tre che portano in C più i due che portano in B insomma la serie di fibonacci, il numero di passaggi per una lettera è pari alla somma dei passaggi per raggiungere le due precedenti
1-1-2-3-5-8-13-21-34-55
questo è il numero relativo a I(9) |
scusate, ho visto dopo che molti quotano così per lasciare agli altri la possibilità di risolvere autonomamente ed ho modificato |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 01 Mag 2006 13:33 Oggetto: |
|
|
La successione di Fibonacci è definita per ogni n = 1,2,3,... dalla seguente relazione ricorsiva:
F(n) = F(n-1) + F(n-2)
con le condizioni iniziali F(1) = F(2) = 1
Quindi:
Citazione: | avendo ricavato che sol(n) = sol(n-1) + sol(n-2)
ma
sol(1) = 1 e sol(2) = 2
possiamo dedurre che la successione delle soluzioni è la successione di Fibonacci traslata ovvero che sol(n) = F(n+1)
da cui sol(9) = F(10) = 55 |
Pertanto:
ottimo il ragionamento di camicius
esatta la correzione di lordbluto
|
|
Top |
|
|
|