3-Fibonacci

>>>>

Suite de Fibonacci.

Nous allons voir, ici, mille et une façons de calculer les nombres de la suite de Fibonacci.

Enfin... Mille, peut-être pas, mais quelques-unes en utilisant Common Lisp.

Ensuite, on évaluera le temps de calcul pour chaque méthode.

Et….Vous en déduirez ce que vous voudrez !

Bon, très bien. Mais qu’est-ce que la suite de Fibonacci ?

Non, non ! Je ne cherche pas à vexer qui que ce soit, mais simplement à établir les conditions de départ pour nous engager sur une bonne programmation.

La suite de Fibonacci est une suite de nombres, disons, u₀, u₁, u₂, u₃, … , u_n, … (on peut aller jusqu’à l’infini, si vous avez le temps), définis de la façon suivante :

u₀ = 0, u₁ = 1, u₂ = 1 (càd u₀ + u₁), u₃ = 2 (càd u₁ + u₂), … , u_n = u_n-2 + u_n-1, …

C’est-à-dire que chaque nombre de la suite est égal à la somme des deux précédents.

«u₀» vous fait faire la grimace : pourquoi ne pas commencer à 1, comme on fait en général ?

Question de programmation. Avec Common Lisp, les index commencent souvent à zéro. On pourrait commencer à 1, mais j’ai choisis la simplicité.

Donc quand je dirais « Le 1000ème nombre de la suite de Fibonacci », en fait ce sera « le 1001ème ». Que ce soit bien entendu !

Commençons la programmation !

Je vous propose quelques méthodes sans rien vous expliquez : c'est trop bon de découvrir par soi-même ! Reportez-vous aux fonctions données dans un autre article de ce blog ou bien à l’index des fonctions que vous trouverez sur internet : http://www.cs.cmu.edu/Groups/AI/html/cltl/clm/index.html .

J’attire, aussi, votre attention, sur le commentaire inclus dans la définition des fonctions : vous voyez, immédiatement, ce que fait la fonction.

À signaler, également, les commentaires sur la ligne de programme : juste après le « ; ».

Bien sûr, vous avez ouvert EMACS et SLIME dans une fenêtre : quelques copier-coller feront l’affaire (avec quelques problèmes, parfois, comme le passage à la ligne au milieu d'un commentaire).

Avec Common Lisp, une fonction peut faire appelle à … elle-même !

C’est la récursivité.

La récursivité n’est pas toujours bonne à utiliser ; essayer (fibonacci 50), puis (fibo 50) pour comparer les deux fonctions suivantes :

(defun fibonacci (n)

"rend le nième élément de la suite de Fibonacci, mais le temps de calcul croît de façon exponentielle quand n augmente."

(if (= n 0) 0

(if (= n 1) 1

(+ (fibonacci (1- n)) (fibonacci (- n 2)))))) ;cette procédure recalcule fibonacci(n-1) 3 fois!

(defun fibo (n)

"rend le nième élément de la suite de Fibonacci, mais en construisant la suite dans une liste à partir des deux précédents éléments."

(let* ((liste '(1 0)) (num (gensym)) (num n))

(loop for i from 2 to num do

(setf liste (cons (+ (car liste) (car (cdr liste))) liste))) ;le résultat est placé dans la liste, donc il sera lu et non recalculé

(car liste)))

Remarque : la variable num générée par gensym prend la 1ère valeur de n et reste constante dans la boucle loop, même si  : n=(random 10)

Vous dites ? Ces programmes sont vraiment courts !

Oui, c'est comme ça, avec ce … Stop ! Je ne veux pas faire de polémique, mais il y aurait beaucoup à dire dans un sens ou dans l’autre…

(defun fibo2 (n)

"rend le nième élément de la suite de Fibonacci en utilisant la macro DO."

(let ((num (gensym)))

(do ((p 0 (1+ p))

(cur 0 next)

(next 1 (+ cur next))

(num n))

((= num p) cur))))

Même remarque et de plus il n'y a pas de saut prévu pour num dans DO.

Ouvrons une parenthèse : vous pouvez utiliser la fonction suivante (et l'améliorer!) pour présenter les calculs. A la place de « fibo » choisissez la fonction fibo* qui vous convient.

(defun question-fibo ()

(format t "Vous cherchez un nombre de la suite de Fibonacci? (o/n)")

(let ((p (read-char)))

(cond

((string= p "n") "au revoir")

(t (format t "Entrez un nombre entier: ")

(let ((n (read)))

(cond

((integerp n) (format t "Le ~aème nombre de la suite de Fibonacci est: ~a.~%" n (fibo n)) (question-fibo))

(t (question-fibo))))))))

Toujours le calcul d'un nombre de la suite, mais en utilisant une plist(La plist n'occupe-t-elle pas plus d'espace mémoire que la liste précédente dans FIBO?):

(defun mem-fib (n)

(cond

((= n 0) 0)

((= n 1) 1)

((get 'mem-fib n))

(t (setf (get 'mem-fib n) (+ (mem-fib (1- n)) (mem-fib (- n 2)))))))

Vos remarques et explications m'intéressent, débutants ou confirmés.

Même chose, mais, ici, mem-fib est une fonction locale de la fonction fibonacci1:

(defun fibonacci1 (p)

"Rend le pième élément de la suite de Fibonacci, en utilisant une fonction locale récursive mem-fib."

(if (integerp p)

(labels ((mem-fib (n) ; définition de mem-fib

(cond

((= n 0) 0)

((= n 1) 1)

((get 'mem-fib n))

(t (setf (get 'mem-fib n) (+ (mem-fib (1- n)) (mem-fib (- n 2))))))

))

(mem-fib p)) ; appel de mem-fib

(error "~a n'est pas un nombre entier" p)))

Voici deux autres méthodes, très intéressantes, qui font réfléchir. Ayez les définitions de DO et LOOP sous les yeux !

(defun fibo3 (p)

"rend le pième élément de la suite de Fibonacci."

(do ((n 0 (1+ n))

(cur 0 next)

(next 1 (+ cur next)))

((= p n) cur)))

Remarque: c'est fibo2 en moins bien!

(defun fibo4 (n)

"rend le nième élément de la suite de Fibonacci."

(loop for i below n

and a = 0 then b

and b = 1 then (+ b a)

finally (return a)))

Vous voulez me proposer d'autres fonctions fibo, n'hésitez pas : contactez-moi.

J'espère que vous avez passé un bon moment (disons un long plaisir).

Il me reste à parler de la durée d'exécution de ces fonctions :

(time (fibo3 10))

Si ça va trop vite, essayez :

(time (fibo3 10000))

… !!! Tout ça ! Oui, car le résultat de la fonction fibo s'affiche aussi. Et là, le résultat est très grand.

La prochaine fois, nous verrons: "LOOP: tout un programme!".