[Challenge] Suite de Fibonacci

[(gile)]

Salut,

 

Vous connaissez certainement ou en tout cas vous avez déjà entendu parler de la suite de Fibonacci.

Cette suite d'entier naturels commence par 0 et 1 et chaque terme étant égal à la somme des deux termes pécédents.

 

Je propose un petit challenge qui consiste à définir une fonction qui retourne le Nième terme de la suite de Fibonnacci, N étant l'argument de la fonction.

 

(fib 0) doit retourner 0

(fib 1) doit retourner 1

(fib 2) doit retourner 1

(fib 3) doit retourner 2

(fib 4) doit retourner 3

(fib 5) doit retourner 5

etc.

(mapcar 'fib '(0 1 2 3 4 5 6 7 8 9)) doit retourner : (0 1 1 2 3 5 8 13 21 34)

(fib 46) doit retourner 1836311903 (46 est le rang maximal accessible avec des entier signés sur 32 bits qui ne peuvent excéder 2147483647).

[lecrabe]

Hello

 

En recherchant sur Google avec ces mots :

fibonacci series program in lisp

On est "noye" par les retours ...

 

Bye, lecrabe

[(gile)]

Salut,

 

C'est vrai que c'est un classique...

[Patrick_35]

Hello

 

En recherchant sur Google avec ces mots :

fibonacci series program in lisp

On est "noye" par les retours ...

 

Bye, lecrabe

Oui, mais le plus interressant est de trouver par soi-même.

Pour le moment, je suis en train de poser sur papier la logique

 

@+

[Patrick_35]

La voila en itérative

 

(defun fib (a / b c d e)
 (setq b 0)
 (while (<= b a)
   (cond
     ((eq b 0) (setq c 0 d 0))
     ((member b '(1 2)) (setq c 0 d 1))
     (T (setq e c c d d (+ d e)))
   )
   (setq b (1+ B))
 )
 (+ c d)
)

 

@+

[(gile)]

Super.

On peut faire un (tout petit) peu plus concis et rapide...

[Patrick_35]

En un peu plus concis

 

(defun fib (a / b c d e)
 (setq b 0 c 0 d 0)
 (while (<= b a)
   (cond
     ((zerop B))
     ((member b '(1 2)) (setq d 1))
     (T (setq e c c d d (+ d e)))
   )
   (setq b (1+ B))
 )
 (+ c d)
)

 

@+

 

ps : maintenant, je vais regarder de plus près ta réponse sur l'autre challenge

[bonuscad]

Une variante avec la formule de Binet.

(defun fibo (n / )
(fix (* (/ 1 (sqrt 5)) (- (expt (* (1+ (sqrt 5)) 0.5) n) (expt (* (- 1 (sqrt 5)) 0.5) n))))
)

[zebulon_]

Je ne connaisais pas la formule de Binet, mais cela semble être imbattable en terme de vitesse principalement pour des n grands. En effet, il n'y a ni itération ni récursivité puisqu'il n'y a pas besoin de connaitre les 2 termes précédents pour trouver celui qui nous intéresse. En prime, on y retrouve le nombre d'or.

 

Ma contribution, en utilisant une liste

 

(defun fib (n / lfib)
 (cond
   ((zerop n) (setq lfib '(0)))
   (T
     (setq lfib '(1 0))
     (repeat (- n 1)
       (setq lfib (cons (+ (car lfib) (cadr lfib)) lfib))
     )
   ) 
 )
 (car lfib)
)

 

on pourrait aussi ne pas garder toute la liste, mais uniquement les 2 derniers termes dans la boucle repeat :

(setq lfib (list (+ (car lfib) (cadr lfib)) (car lfib)))

 

Amicalement

Vincent

[bonuscad]

mais cela semble être imbattable en terme de vitesse

 

Certe, mais d'après ce que j'ai compris; avec des grands nombres cela peut apporté une imprécision à cause de l'usage de racine de 5.

Mais comme (gile) à précisé jusqu'à 46, cela ne pose pas de problème dans ce cas précis...

[zebulon_]

Certe, mais d'après ce que j'ai compris; avec des grands nombres cela peut apporter une imprécision à cause de l'usage de racine de 5.

 

Ah oui, bien sûr. On ne peut pas tout avoir :P

 

Amicalement

Vincent

[(gile)]

Bravo à bonuscad pour avoir suivi une autre route.

 

Mes propositions :

 

Récursion simple, la plus concise, mais de loin la plus lente

(defun fib (i)
 (cond
   ((< i 2) i)
   (T (+ (fib (- i 1)) (fib (- i 2))))
 )
)

 

Récursion terminale

(defun fib (i / loop)
 (defun loop (a b i)
   (if	(= 0 i)
     a
     (loop b (+ a B) (1- i))
   )
 )
 (loop 0 1 i)
)

 

Itération avec while (traduction itérative de la précédente)

(defun fib (i / a b c)
 (setq	a 0 b 1 )
 (while (< 0 i)
   (setq i (1- i) c (+ a B) a b b c)
 )
 a
)

 

Itération avec repeat

(defun fib (i / a b c)
 (cond
   ((< i 2) i)
   ((setq a 0 b 1)
    (repeat (1- i)
      (setq c (+ a B) a b b c)
    )
   )
 )
)

[DenisHen]

Bonjour à tous,

 

Il est vrai que la suite de Fibonacci est un classique, surtout que c'est une des seules "logiques mathématiques" que l'on retrouve dans la nature...

 

Mais de la à faire ce que vous avez fait messieurs... C'est autre chose...

 

Je l'avais fais sous VB, mais en LiSP... Vous avez trop d'expérience pour que je fasse quoi que ce soit...

 

Je ne m'infligerais pas la "honte" de faire un code en plus 50 lignes (et c'est un minimum), ne serait-ce que pour vous parodier...

 

Juste une remarque, je n'ai pas vu le fameux "lambda", très cher au LiSP, dans vos propositions...

 

Mais encore une fois, j'apprend beaucoup avec vos codes... C'est fou...

 

Merci à (gile) pour cette "énigme du profsseur (gile)", voire même, "le coup du père (gile)", vieille ruse ancestrale détenue que par certains druides et autres magiciens...

 

Cordialement et bonne soirée à tous...

 

Denis...

[Patrick_35]

Salut

 

Vous avez trop d'expérience pour que je fasse quoi que ce soit...

 

Je ne m'infligerais pas la "honte" de faire un code en plus 50 lignes (et c'est un minimum), ne serait-ce que pour vous parodier...

Au contraire. Plus on est de fous...

Cela permet aussi d'apporter sa pierre et une autre manière de voir.

Quand (gile) m'avais indiqué que je pouvais faire plus concis, à la lecture de son code, il a raison. Je n'y avais tout simplement pas pensé.

Les challenges sont aussi pédagogiques et c'est en essayant de les réaliser (quel que soit son niveau) qu'on progresse

 

Juste une remarque, je n'ai pas vu le fameux "lambda", très cher au LiSP, dans vos propositions...

lambda permet de définir une fonction anonyme.

Par exemple, quand on utilise la fonction mapcar, on envoie des infos dans une autre fonction.

Dans l'exemple (mapcar 'fib '(0 1 2 3 4 5 6 7 8 9)), on envoie la valeur 0 à la fonction fib, puis la valeur 1, la valeur 2, etc...

Autre exemple pour ajouter + 1 à une liste --> (mapcar '1+ '(0 1 2 3 4))

Et pour finir avec le fameux lambda qui permet la fonction anonyme, par exemple ajouter + 5 à notre liste --> (mapcar '(lambda(x)(+ 5 x)) '(0 1 2 3 4))

On évite ainsi de créer une fonction spécifique et pas vraiment utile pour ajouter 5.

 

@+

[VDH-Bruno]

Salut,

 

AutoLISP ne supportant pas les mémo-fonctions avec l'accès au P-liste (Cf page 54 du lien http://www.ai.univ-paris8.fr/~hw/lisp/letout.pdf pour un exemple appliqué à l'algorithme de FIBONACCI) comme cela peut exister avec LE_LISP.

 

On peut tout de même tenter quelque chose d'approchant sur le principe en utilisant la redéfinition de fonction avec defun-q pour stocker dans le corps de fonction les résultat précédemment calculé, comme cela à déjà été proposé sur ce forum par (gile) sur l'exemple du PGCD.

 

Le code:

(defun-q fib
 (n)
 (list 1 0)
 (cond ((nth n (reverse (cdr(cadr fib)))))
       ((setq fib
	       (vl-list*
		 (car fib)
		 (cons
		   'list
		   (cons (+ (car (cdadr fib)) (cadr (cdadr fib))) (cdadr fib))
		 )
		 (cddr fib)
	       )
	)
	(fib n)
       )
 )
)

 

Code qui à un intérêt seulement sur ce type de traitement:

(mapcar 'fib '(0 1 2 3 4 5 6 7 8 9)) doit retourner : (0 1 1 2 3 5 8 13 21 34)

 

A+

[VDH-Bruno]

Re,

 

Une autre moins hors sujet que la précédente...

(defun fib (i / f)
 (defun f (i / l)
   (cond ((< 1 i) (cons (+ (car (setq l (f (1- i)))) (cadr l)) l))
         ((= 1 i) '(1 0))
         ((zerop i) '(0))
   )
 )
 (car (f i))
)

 

(ps: @(gile) il y a un problème de parenthèses dans tes versions itératives avec repeat & while)

[(gile)]

(ps: @(gile) il y a un problème de parenthèses dans tes versions itératives avec repeat & while)

 

Oups !...

C'est réparé, merci.

[Olivier Eckmann]

Bonjour,

 

J'ai suivi cette discussion très intéressante et je viens de tomber sur cet article.

 

Olivier

[ElpanovEvgeniy]

my version:

(defun f (i l)
 (cond ((not l) (f i '(1 0)))
       ((< i 3) (+ (car l) (cadr l)))
       ((f (1- i) (list (+ (car l) (cadr l)) (car l))))
 )
)

 

 

(mapcar '(lambda (a) (f a nil)) '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21))
;; (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946)

 

code uses a line calculation

Not:

(f n-1) + (f n-2)

as (gile) Récursion terminale

[bonuscad]

Super Evgeniy, (son terrain de predilection).

 

Concis, même pas une variable en locale, juste les arguments et efficace ... saurais jamais faire! :(

 

Bravo!

[didier]

Coucou

 

il est vraiment trop fort, je l'adore et dès que je vois son nom je me jette sur le message et à chaque fois je me trouve tout petit tout petit...

 

amicalement

[bseb67]

Bonjour à tous,

 

je profite d'une panne serveur* :(, pour répondre au post :

Je ne l'avais pas fait en lisp, mais en c à l'époque en BTS.

L'astuce réside aussi à stocker la valeur de fib(n).

En lisp je pencherai pour stocker sous forme de liste :

(fib(0) fib(1) fib(2) ...)

Avec nth on peut alors appeler (nth (n-2)) et (nth (n-1)).

 

 

 

* : Les sauvegardes c'est bien, assez rapides, mais la restauration, une vraie misère.

[lrdb@home]

Bonjour à tous,

Pour les fans de Fibonacci , drôle en plus à 11'20"

https://www.youtube.com/watch?v=nZRKNth6OSA