Bonjour, pourriez vous s'il vous plait m'aider pour cet exercice :
La suite de Fibonacci (Fi)iest définie par F0=0 , F1=1 et pour tout entier i positif :
Fi+2=Fi+1 + Fi
Les premiers nombres de Fibonacci sont :
F2=1 F3 = 2 F4=3 F5=5 F6=8 F7=13 et F8=21
Dans les années 70 un mathématicien a montré que tout nombre entier positif n peut se décomposer de manière unique comme la somme de nombre de Fibonacci distincts et non consécutifs.
De manière générale tout entier n peut se décomposer sous la forme :
n=i
[2;p-1] biFi
Où (bi)2p-1 sont des éléments de [0,1] avec bp-1 = 1. A cette décomposition est associé le codage de Fibonacci de n noté (bp-1,......,b2) le i-ème symbole de ce mot binaire est un 1 si Fi est présent dans la décomposition de Fibonacci de n , un 0 sinon.
1.a: Que vaut leproduit bibi+1 pour i [2,p-1].Que dire alors du codage de Fibonacci de n.
b. Ecrire une fonction pgf(n) qui reçoit un entier postifi n et retourne la liste [F2,F3,....,Fp-1 ] où Fp-1 est le plus grand terme de la suite vérifiant Fin.
c.Ecrire une fonction fibo-code(n) recroit une entier n et retourne le codage de Fibonacci associé.
d.Ecrire une fonction fibo-décode(n) qui réalise l'opération inverse.
Merci de bien vouloir m'aider car je n'y arrive vraiment pas.
Bonjour,
1)a)
Bonjour,
je ne suis pas sûr mais comme les bi sont des éléments de [0,1] le produit fera soit 0 soit 1.
Voyons, on ne peut pas avoir dans la somme deux nombres de Fibonacci successifs.
Donc si est présent dans la somme (donc codé avec
) nécessairement
est absent (donc codé par
) en sorte que:
De la même manière, si , nécessairement
et on a encore:
Bref, ton code est constitué de isolés encadrés par des
ah d'accord merci beaucoup.
pour la question b :
def pgf(n):
a=1
b=2
L=[a,b]
for k in L :
L.append(
....
je ne sais pas comment faire pour qu'il ajoute l'élément constituer des deux éléments précédent et de refaire l'opération encore et encore
Du code, je ne sais pas, mais je peux te montrer sur un exemple la procédure pour coder:
Soit
On dispose de la suite:
On cherche le plus grand nombre de la suite inférieur ou égal à :
c'est
On cherche le plus grand nombre de la suite inférieur ou égal à
c'est
On cherche le plus grand nombre de la suite inférieur ou égal à
c'est
On cherche le plus grand nombre de la suite inférieur ou égal à
c'est
et On arrête quand on tombe sur
et
qui correspond au code:
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :