teaching:progappchim:suite_de_fibonacci-4

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Prochaine révision		 Révision précédente
teaching:progappchim:suite_de_fibonacci-4 [2013/11/08 05:52] – créée villersdteaching:progappchim:suite_de_fibonacci-4 [2017/02/24 09:09] (Version actuelle) – villersd
Ligne 1: Ligne 1:
 ====== Suite de Fibonacci : encore un algorithme ====== ====== Suite de Fibonacci : encore un algorithme ======
  
-La page Wikipedia sur la suite de Fibonacci introduit aussi un [[http://fr.wikipedia.org/wiki/Suite_de_Fibonacci#Algorithme_logarithmique|algorithme logarithmique]]. Même s'il est très intéressant à décortiquer, on peut se contenter de simplement l'appliquer :+Voici le programme complété pour la technique récursive : 
 +<code python fibonacci07_fonction_recursive.py3> 
 +#! /usr/bin/env python 
 +# -*- coding: utf-8 -*- 
 +""" 
 +Calculs des premiers éléments de la suite de Fibonacci. 
 +Référence : http://fr.wikipedia.org/wiki/Suite_de_Fibonacci 
 +Application de la définition par récursivité. 
 +""" 
 +def fibonacci_item_recursive(n): 
 +    """ 
 +    Renvoie l'élément d'indice n de la suite de Fibonacci 
 +    """ 
 +    if n == 0: 
 +        return 0 
 +    elif n == 1: 
 +        return 1 
 +    return fibonacci_item_recursive(n-1)+fibonacci_item_recursive(n-2) 
 + 
 +if __name__ == '__main__': 
 +    i = input("Suite de Fibonacci. Donnez l'indice de l'élément souhaité ? ") 
 +    print("Élément de la suite : "), 
 +    printfibonacci_item_recursive(i) 
 +    print('Premiers éléments de la suite : ') 
 +    for j in range(10): 
 +        print(j,fibonacci_item_recursive(j)) 
 +</code> 
 + 
 + 
 +La page Wikipedia sur la suite de Fibonacci introduit aussi un [[wp>fr:Suite_de_Fibonacci#Algorithme_logarithmique|algorithme logarithmique]]. Même s'il est très intéressant à décortiquer, on peut se contenter de simplement l'appliquer :
  
-<sxh python; title : fibonacci08_fonction_algo_log.py>+<code python fibonacci08_fonction_algo_log.py3>
 #! /usr/bin/env python #! /usr/bin/env python
 # -*- coding: utf-8 -*- # -*- coding: utf-8 -*-
Ligne 14: Ligne 43:
 def fibo2(n): def fibo2(n):
     """Renvoie F_{n-1}, F_n"""     """Renvoie F_{n-1}, F_n"""
-    if (n == 0):  # cas de base+    if n == 0:  # cas de base
         return 1, 0  # F_{-1}, F_0         return 1, 0  # F_{-1}, F_0
     else:         # récurrence     else:         # récurrence
Ligne 29: Ligne 58:
  
 if __name__ == '__main__': if __name__ == '__main__':
-    i=input("Suite de Fibonacci. Donnez l'indice de l'élément souhaité ? ") +    i = input("Suite de Fibonacci. Donnez l'indice de l'élément souhaité ? ") 
-    print ("Élément de la suite : "), +    print("Élément de la suite : "), 
-    print fibonacci_item_logarithmic(i) +    printfibonacci_item_logarithmic(i) 
-    print ('Premiers éléments de la suite : ')+    print('Premiers éléments de la suite : ')
     for j in range(10):     for j in range(10):
-        print j,fibonacci_item_logarithmic(j) +        print(j,fibonacci_item_logarithmic(j)) 
-</sxh>+</code> 
 + 
 +Sur la même page wikipedia, on trouve une [[wp>fr:Suite_de_Fibonacci#Expression_fonctionnelle|expression fonctionnelle]], de complexité apparente en temps constant, aussi connue sous le nom de [[wp>fr:Suite_de_Fibonacci#Avec_la_formule_de_Binet|formule de Binet]], mais qui passe par le calcul du nombre irrationnel $\sqrt{5}$, ce qui pose un problème pour conserver une précision des chiffres significatifs par rapport à l'arithmétique entière. 
 + 
 +Le langage Python permet également de mettre en œuvre des générateurs (generator) : //cf.// [[http://www.koderdojo.com/blog/python-fibonacci-number-generator]] et [[http://www.bogotobogo.com/python/python_generators.php]] 
 + 
 +<code python fibonacci09_generator.py3> 
 +#! /usr/bin/env python 
 +# -*- coding: utf-8 -*- 
 +""" 
 +Calculs des premiers éléments de la suite de Fibonacci. 
 +Référence : http://fr.wikipedia.org/wiki/Suite_de_Fibonacci 
 +""" 
 +def fibonacci_gen(n): 
 +    """ 
 +    Renvoie l'élément d'indice n de la suite de Fibonacci 
 +    """ 
 +    a, b = 0, 1 
 +    for _ in range(n): 
 +        yield a 
 +        a, b = b, a + b 
 + 
 +if __name__ == '__main__': 
 +    i = int(input("Suite de Fibonacci. Donnez l'indice max des éléments souhaités ? ")) 
 +    print("Le générateur : "), 
 +    print(fibonacci_gen(i)) 
 +    print('Éléments de la suite : ') 
 +    for j in fibonacci_gen(i): 
 +        print(j) 
 +</code>
  
-Nous disposons à présent de 4 méthodes/fonctions pour calculer les éléments de la suite de Fibonacci.+Nous disposons à présent de plusieurs méthodes/fonctions pour calculer les éléments de la suite de Fibonacci.
  
 Pour rechercher quel est le meilleur algorithme, [[suite_de_fibonacci-5|cliquez ici !]] Pour rechercher quel est le meilleur algorithme, [[suite_de_fibonacci-5|cliquez ici !]]
  • teaching/progappchim/suite_de_fibonacci-4.1383886366.txt.gz
  • Dernière modification : 2013/11/08 05:52
  • de villersd