Scribd
Importer
235 vues2 pages

Algos Fibonacci PDF

Transféré par

Has Saadaoui
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
235 vues2 pages

Algos Fibonacci PDF

Transféré par

Has Saadaoui
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Licence d’Informatique 2014–2015 Semestre 6

Probabilités et Combinatoire J1IN6016

Trois algorithmes de calcul des nombres de


Fibonacci

Dans cette série d’exercices, nous nous intéressons de la complexité dite


arithmétique. Ce modèle prend en compte uniquement le nombre des opérations
arithmétiques, sans se soucier de la taille des nombres en question.
L’objectif des trois algorithmes présentés ci-dessous est le calcul du nème
nombre de Fibonacci fn .

Exercice 1 (Algorithme récursif ) Soit l’algorithme suivant :


si n = 0 ou n = 1 alors
f ib (n) = 1
sinon
f ib (n) = f ib (n − 1) + f ib (n − 2)
fin-si
Estimer la complexité de cet algorithme.

Exercice 2 (Algorithme itératif ) Soit l’algorithme suivant :


si n = 0 ou n = 1 alors
f ib (n) = 1
sinon
a=1
b=1
pour i de 2 à n faire
c=a+b
a=b
b=c
fin-pour
f ib (n) = c
fin-si
Estimer la complexité de cet algorithme.

Exercice 3 (Algorithme matriciel) Soit A la matrice suivante :


 
0 1
A = .
1 1

1. Montrer que    
fn−1 fn
A· = .
fn fn+1

1
2. Conclure que    
fn 1
= A ·n
.
fn+1 1
3. Proposer un algorithme très efficace de calcul de fn basé sur l’obsrevation
précédante. (Une présentation formelle de cet algorithme n’est pas demandée.)
Estimer la complexité de cet algorithme.

Exercice 4 (Généralisation) Adapter la même méthode à la suite récurrente


suivante :

a0 = 1
a1 = 2
a2 = 1
an = 2an−1 + 5an−2 − an−3 pour n ≥ 3.

Vous aimerez peut-être aussi