Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Suite de fibonicci Programmation Dynamique CHAPITRE III III Exemple introductif la suite de Fibonacci La suite de Fibonacci est la suite d ? entier un n ? d ?e ?nie r ?ecursivement par F F F F F F F F F F u u un un ?? un ?? ??n ? On peut traduire directem

Programmation Dynamique CHAPITRE III III Exemple introductif la suite de Fibonacci La suite de Fibonacci est la suite d ? entier un n ? d ?e ?nie r ?ecursivement par F F F F F F F F F F u u un un ?? un ?? ??n ? On peut traduire directement cette d ?e ?nition en un algorithme r ?ecursif Algorithm Fibonacci procedure Fibonacci n if n ? then return n else return Fibonacci n ?? Fibonacci n ?? end if end procedure Pour analyser la complexit ?e de cet algorithme on remarque que chaque appel a Fibonacci se fait en temps constant si on ne tient pas compte des appels r ?ecursifs lanc ?es Il su ?t donc de compter le nombre d ? appels pour n en entr ?ee que l ? on va noter An La suite An v ?eri ?e F F F F F F F F F F a a an an ?? an ?? ??n ? Cette suite ressemble a la su ??ite de Fibonacci On peut l ? ?etudier math ?ematiquement et on trouve que An ?? n ou ?? est le nombre d ? or La complexit ?e de l ? algorithme est donc exponentielle D ? ou vient une telle complexit ?e Si on d ?eveloppe le calcul de u on a u u u u u u u u u u u u u u u COn remarque que les m emes calculs sont e ?ectu ?es un nombre important de fois Pour am ?eliorer la performance de l ? algorithme on peut stocker les r ?esultats interm ?ediaires obtenus et les r ?eutiliser directement quand on en a besoin au lieu de les recalculer C ? est l ? id ?ee de la programmation dynamique Cela donne Algorithm Fibonacci procedure Fibonacci n T if n ? then return n end if if T n n ? est pas d ?e ?ni then T n Fibonacci n ?? Fibonacci n ?? end if return T n end procedure La complexit ?e devient alors lin ?eaire on ne remplit la case T n qu ? une fois donc le nombre d ? appels a Fibonacci i pour chaque valeur i ? n est d ? au plus une fois pour le calculer une fois quand on calcule Fibonacci i et une fois quand on calcule Fibonacci i On peut d ?e-r ?ecursiver l ? algorithme Il s ? agit de remplir le tableau T directement case par case On s ? aper coit qu ? il faut faire le contraire de ce que fait l ? algorithme r ?ecursif commencer par les petites valeurs Algorithm Fibonacci procedure Fibonacci n Allouer T avec n cases T T for i de a n ?? do T i T i ?? T i ?? end for return T n end procedure Il est imm ?ediat que l ? algorithme est bien lin ?eaire Il prend aussi une quantit ?e de m