Inscription / Connexion Nouveau Sujet
Niveau logiciels
Partager :

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 (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.

Posté par
lake
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
nirosane
re : Autour de fibonacci 28-02-18 à 13:54

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.

Posté par
lake
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
nirosane
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
lake
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

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !