J'aime bien le code "hackaton"
J'ai fait cet exercice il y a qq mois (en utilisant Java et les BigInteger, donc, pas limité à fibonnacci(164)), en utilisant aucune des méthodes décrites.
Premier algo, c'est celui qu'on fait naturellement, "à la main". On connait fibo(0) et fibo(1), puis, via une simple boucle for, on calcule fibo(2), fibo(3) ... jusqu'à fibo(n) recherché. Ici, on calcule chaque valeur entre 1 et N une seule fois; et comme, à chaque calcule, seules les 2 dernières valeurs sont utiles; je n'utilise qu'un tableau de 3 éléments. A chaque étape, le dernier élément calculé devient le n-1, l'ancien n-1 devient n-2 et le résultat du calcul passe dans l'ancien n-2 (ça fait une fonction de calcul d'indice relatif entre le fibo et la tableau un peu complexe, mais c'est très économique.
Le second algo part sur la remarque que :
fibo(n) = fibo(n-1)*fibo(1) + fibo(n-2)*fibo(0) = fibo(n-2)*fibo(1) + fibo(n-3)*fibo(1) + fibo(n-2)*fibo(0) = fibo(n-2)*fibo(2) + fibo(n-3)*fibo(1)
On voit facilement, par récursivité, que :
fibo(2*n) = fibo(n)² + fibo(n-1)²
fibo(2*n + 1) = fibo(n) * (fibo(n+1) + fibo(n-1))
Du coup, en codant simplement ce système récursif avec un mécanisme de "Mémoisation" (une simple Map), on ne calcule qu'environ log2(n) éléments.
Pour info,
fibo(1440) = 39148665084314713611487939879536073000884287539729085016573824046902113615010632646259788823155802905194474577
2829337376406678858402406939880042845977014235081189477072987319401028174973366140751380465125202666913528379206343180700
4225506814702922160621247026028619389629299722842113162285992338142080
calculé en presque 6 millisecondes pour le premier algo et 2 millisecondes pour le second.
Partager