Niveau logiciels

Autour de fibonacci

Posté par
nirosane 28-02-18 à 13:14

Bonjour, pourriez vous s'il vous plait m'aider pour cet exercice :

La suite de Fibonacci (F_i)_iest définie par F₀=0 , F₁=1 et pour tout entier i positif :

F_i+2=F_i+1 + F_i

Les premiers nombres de Fibonacci sont :
F₂=1 F₃ = 2 F₄=3 F₅=5 F₆=8 F₇=13 et F₈=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] b_iF_i
Où (b_i)_2p-1 sont des éléments de [0,1] avec b_p-1 = 1. A cette décomposition est associé le codage de Fibonacci de n noté (b_p-1,......,b₂) le i-ème symbole de ce mot binaire est un 1 si F_i est présent dans la décomposition de Fibonacci de n , un 0 sinon.

1.a: Que vaut leproduit b_ib_i+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 [F₂,F₃,....,F_p-1 ] où F_p-1 est le plus grand terme de la suite vérifiant F_in.
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.

Posté par re : Autour de fibonacci 28-02-18 à 13:46

Bonjour,

1)a)

Citation :
n peut se décomposer de manière unique comme la somme de nombre de Fibonacci distincts et non consécutifs

Alors que vaut $b_ib_{i+1}$ ?

Posté par re : Autour de fibonacci 28-02-18 à 13:54

Bonjour,
je ne suis pas sûr mais comme les b_i sont des éléments de [0,1] le produit fera soit 0 soit 1.

Posté par re : Autour de fibonacci 28-02-18 à 14:02

Voyons, on ne peut pas avoir dans la somme deux nombres de Fibonacci successifs.

  Donc si   $F_i$ est présent dans la somme (donc codé avec $b_i=1$ ) nécessairement $F_{i+1}$ est absent (donc codé par $b_{i+1}=0$ ) en sorte que:

     $b_ib_{i+1}=0$

  De la même manière, si $b_{i+1}=1$ , nécessairement $b_i=0$ et on a encore:

   $b_ib_{i+1}=0$

Bref, ton code est constitué de $1$ isolés encadrés par des $0$

Posté par re : Autour de fibonacci 28-02-18 à 14:27

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

Posté par re : Autour de fibonacci 28-02-18 à 14:49

Du code, je ne sais pas, mais je peux te montrer sur un exemple la procédure pour coder:

Soit $n=75$

On dispose de la suite: $F_2=1,F_3=2,F_4=3,F_5=5,F_6=8\cdots$

  On cherche le plus grand nombre de la suite inférieur ou égal à $n=75$ :

    c'est $F_{10}=55$

   $n-F_{10}=20$

  On cherche le plus grand nombre de la suite inférieur ou égal à $n-F_{10}=20$

   c'est $F_7=13$

   $n-F_{10}-F_7=7$

  On cherche le plus grand nombre de la suite inférieur ou égal à $n-F_{10}-F_7=7$

   c'est $F_5=5$

$n-F_{10}-F_7-F_5=2$

  On cherche le plus grand nombre de la suite inférieur ou égal à $n-F_{10}-F_7-F_5=2$

  c'est $F_3=2$

  et $n-F_{10}-F_7-F_5-F_3=0$    On arrête quand on tombe sur $0$

et $n=F_3+F_5+F_7+F_{10}$

qui correspond au code:

   $010101001$