Pagina 1 di 1
Combinatoria ricorsiva
Inviato: 24/03/2018, 14:21
da Filippo 01
In quanti modi posso mettere in fila i numeri interi da 1 a 10 in modo da seguire le seguenti regole? :
- Il primo numero è sempre 1
- La differenza tra due posti che occupano posizioni consecutive non è mai superiore a 2
Riuscite a risolverlo in maniera ricorsiva? Se sì potete scrivere il procedimento?
Re: Combinatoria ricorsiva
Inviato: 30/07/2019, 9:54
da ronny
Ci provo:
Primo numero 1 e poi devo mettere in fila 9 numeri usando solo la regola 2:
- scelgo il numero 2 e poi devo mettere in fila i rimanenti 8 numeri da 3 a 10. Chiamo questo valore [tex]A_8[/tex]
- scelgo il numero 3, quindi il successivo deve per forza essere il 2 (altrimenti poi il 2 diventa troppo lontano per tutti i numeri rimantenti) e quindi rimangono 7 numeri consecutivi da
scegliere con l'algoritmo ricorsivo, cioè [tex]A_7[/tex]
Quindi [tex]A_{9} = A_8 + A_7[/tex], in generale [tex]A_{n} = A_{n-1} + A_{n-2}[/tex] con [tex]A_2 = 2[/tex] e [tex]A_1 = 1[/tex]
In pratica una successione di Fibonacci che inizia da 1 e 2 invece che da 0 e 1
Si calcola anche a mano [tex]A_{9} = 55[/tex]
Sai se il risultato è giusto?