I. Les tours de Hanoï
Pré-requis : suite récurrente + rais. par récurrence (pour Hanoï) T°S - D.M. Les tours de Hanoï et la légende de Sissa (J. Mathieu). Page 1 sur 8. TS-DM ...
Les tours de Hanoï
? Calculer des termes d'une suite définie explicitement par récurrence ou par un algorithme. Lien avec Les maths au quotidien : Loisirs. Tours de Hanoï. Le
Mathématiques
- Liste des premiers termes d'une suite : suites de Syracuse suite de Fibonacci. Approfondissements. - Tour de Hanoï. Page 8. Mathématiques
Le Rallye 974 Maths clé en main de 2014 à 2020
Problème 4 : Les tours de Hanoï bicolores mathématiques ont un rôle indéniable à jouer pour relever les défis des décennies à venir.
Le jeu des tours de Hanoï. - Compte rendu dune séance de
2) On suppose qu'il faut 5 secondes pour déplacer un disque combien de temps le jeu durera-t- il avec trente disques en travaillant jour et nuit ? J'ai demandé
La récurrence de lapproche au raisonnement
La légende de l'échiquier où l'approche d'une suite géométrique Le professeur de mathématiques décide de faire des binômes pour son prochain DM avec les ...
Terminale NSI TP - Les Tours de Hanoï Récursivité
De même pour déplacer n – 1 disques on peut auparavant déplacer n – 2 disques. Ainsi de suite jusqu'à ne plus avoir de disque. Donc
801 énigmes. . . de Âne à Zèbre
F F C pour jouer deux fois de suite aux fléchettes puis une fois Énigme. Voilà le problème « des tours de Hanoï » de Lucas revisité !
Stage olympique de Grésillon II
Montrer que la suite (an) définie par a1 = 1 et an = an?1 + a[n/2] pour n Les contrôleurs choisissent `a tour de rôle un passager sans billet et lui.
Chapitre 7 Récursivité et fractales
Écrivez en Python une fonction itérative donnant la suite de Syracuse Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas ...
L'informatique au lycéeChapitre 7
http://ow.ly/mKyXLChapitre 7
Récursivité et fractales
7.1. La récursivité
En mathématiques, en informatique, en biologie, mais aussi dans notre quotidien, nous faisonssouvent face à des situations où un problème doit être résolu en utilisant une méthode de résolution
qui est répétée plusieurs fois. Dans l'itération, cette méthode est appliquée par paliers de façon
séquentielle, dans la récursivité, la méthode s'appelle elle-même.La récursivité est un principe de pensée exigeant et est souvent désigné comme " trop
compliqué ». La récursivité est cependant si fondamentale qu'il n'est pas possible de l'éviter.
M. C. Escher
1898 - 19727.1.1.Dans les arts
Dans le domaine des arts, c'est l'artiste néerlandais Maurits Cornelis Escher qui fait le plus grand
usage de la récursivité.Didier Müller7-1août 2015
Récursivité et fractales
En anglais, on parle
de " Droste effect » pour " mise enabyme ».De son côté, la publicité a aussi utilisé la mise en abyme, rendant célèbres les fromages " La vache
qui rit », le vermouth " Dubonnet », et le chocolat " Droste ». Signalons enfin la pochette de l'album de Pink Floyd " Ummagumma » :7.1.2. Biologie
La récursivité est particulièrement présente en biologie, notamment dans les motifs de végétaux
et les processus de développement. Les diatomées présentent en particulier de belles structures
récursives.7.1.3. Vie courante : le format A4
La norme DIN-A détermine la taille du papier. Le format A0 qui est le plus grand formatnormalisé (1 mètre carré de surface) se décline jusqu'au format A10. La longueur du format inférieur
est systématiquement égale à la largeur du format supérieur. Le format inférieur est donc obtenu en
pliant le format supérieur en deux dans sa largeur. Quel que soit le format, on trouve toujours le rapport2 entre longueur et largeur.Didier Müller7-2août 2015
L'informatique au lycéeChapitre 7
A(i) est obtenu de A(i-1) en pliant dans sa longueur la feuille de papier. La relation de récurrence
est donc : •Longueur de A(i)) = Largeur de A(i-1) •Largeur de A(i) = ½ Longueur de A(i-1)7.2.Fonctions récursives et itératives
En informatique et en mathématiques, une fonction qui s'appelle elle-même est dite récursive.
Deux fonctions peuvent s'appeler l'une l'autre, on parle alors de récursivité croisée, qui est très
commune dans le style de programmation fonctionnelle et est souvent utilisée dans les langages LISP, Scheme, Prolog et autres langages similaires.7.2.1.Élévation d'un entier x à une puissance n
La fonction puissance existe en Python. Mais si elle n'existait pas, voici une manière ingénieuse
de l'implémenter. def puissance(x,n): if n==0: return 1 elif n==1: return x elif n%2==0: return puissance(x*x, n//2) else: return puissance(x*x, n//2)*xExercice 7.1Exercice 7.1
Ce programme calcule xn. Expliquez comment il fonctionne.Calculez " à la main » puissance(2,9).
Didier Müller7-3août 2015
Récursivité et fractales
7.2.2.Calcul de la factorielle
Rappel : n! = n·(n-1)·(n-2)· ... ·2·1. Cas particulier : 0! = 1. def factorielle(n): if n==1 or n==0 : return 1 else : return n*factorielle(n-1) Le cas n=1 est appelé cas de base. Sans sa présence, l'algorithme ne peut pas se terminer. On peut évidemment écrire une fonction itérative de la factorielle : def factorielle(n): resultat = 1 for i in range(1,n+1): resultat *= i return resultat Le calcul de la factorielle est rarement utilisé tel quel en pratique. Pour des valeurs de n supérieures à 10, la formule de Stirling donne un résultat correct à 0.8% près : n! @ 2nn en , avec e = 2.718281828459... Un appel de fonction est une opération plus coûteuse en soi que, par exemple, une opérationarithmétique ou un test. C'est pourquoi on préfère souvent la fonction itérative à la version récursive.
Dans le cas de la factorielle, on prendra plutôt la version itérative, mais il y a des cas où la fonction
récursive est clairement préférable, par exemple pour parcourir des arbres (voir chapitre 8), ou faire
des tris (voir chapitre 9).7.2.3.Coefficients binomiaux
La fonction C(n, p) donne le nombre de manières de prendre p éléments parmi n. Une importante
relation que l'on peut observer dans le triangle de Pascal ci-dessous, lie les coefficients binomiaux :
C(n+1, p+1) = C(n, p) + C(n, p+1) (formule de Pascal)Didier Müller7-4août 2015
L'informatique au lycéeChapitre 7
def C(n,p): if (n>p) and (p>0): return C(n-1,p-1)+C(n-1,p) else: return 1Syracuse est ici le
nom d'une ville universitaire américaine (NewYork).Exercice 7.2Exercice 7.2
La suite de Syracuse est définie par :{x1=a∈ℕ* xn1= {xn2sixnestpair
3xn1sixnestimpair1.Écrivez en Python une fonction itérative donnant la suite de Syracuse commençant par a.
2.Écrivez une version récursive.
La terminaison d'un algorithme récursif peut être un problème extrêmement difficile. Ainsi,
personne n'a jusqu'à présent été capable de démontrer que la fonction Syracuse présentée plus haut se
termine pour toute valeur de n.Exercice 7.3Exercice 7.3
Écrivez un programme récursif permettant d'évaluer un nombre écrit en chiffres romains.Rappelons que :
•M = 1000 •D = 500 •C = 100 •L = 50 •X = 10 •V = 5 •I = 1Comme exemple, évaluons le nombre MCMXCIX.
|On est sur le premier M. |Son successeur est C, il est plus petit, donc notre résultat final sera la |valeur de M (1000) plus la valeur du reste (CMXCIX). | La valeur du reste est la suivante : | C est plus petit que M (une soustraction aura lieu) donc la valeur de | CMXCIX est égale à la valeur de MXCIX moins la valeur de C | | La valeur de MXCIX est la suivante : | | |M est plus grande que X donc on a 1000+valeur(XCIX). | | | La valeur de XCIX est égale à la valeur de CIX moins la valeur de X | | | |car le premier X est plus petit que son successeur. | | | | La valeur de CIX est égale à 100 + valeur(IX) car C est plus | | | | |grand que I. | | | | | La valeur de IX est égale à la valeur de X moins la valeur | | | | | de I, soit 10-1 = 9. | | | | CIX = C + 9 = 109 | | | XCIX = CIX - X = 109 - 10 = 99 | | MXCIX = M + XCIX = 1000 + 99 = 1099 | CMXCIX = MXCIX - C = 1099 - 100 = 999MCMXCIX = 1000 + 999 = 1999
Didier Müller7-5août 2015
Récursivité et fractales
On voit la forme de l'algorithme général :
•Soit un nombre romain. Si la première lettre de ce nombre a une valeur inférieure audeuxième, alors on le soustrait de la valeur de tout le reste. Sinon, on l'additionne à la valeur
de tout le reste. •Si le nombre romain a un seul chiffre, alors on prend simplement la correspondance (M = 1000, D = 500, ...). On constate qu'avec l'algorithme ci-dessus, le nombre MIM (qui pourtant n'existe pas chez lesromains) est évalué à 1999. Le programme n'effectuera pas un test d'exactitude de la chaîne passée
en paramètre, il se contentera de l'évaluer.7.3.Les dangers de la récursivité
Utiliser une fonction récursive n'est pas toujours une bonne idée. Prenons la suite de Fibonacci : 1, 1, 2, 3, 5, 8, 13, 21, 34, ... Un terme est la somme des deuxprécédents. On va écrire deux fonctions (une récursive et une itérative) qui calculent le k-ième terme
de cette suite, puis on comparera les temps de calcul. import time def fib1(n): # algorithme récursif if n==1 or n==2 : return 1 else : return fib1(n-1) + fib1(n-2) def fib2(n): # algorithme itératif i=1 j=1 k=3 s=2 if n==1 or n==2 : return 1 else : while k<=n : s=i+j i=j j=s k+=1 return s for k in range(5): print((k+1)*10) a=time.clock() fib1((k+1)*10) b=time.clock() print("récursif :", b-a) a=time.clock() fib2(k) b=time.clock() print("itératif :", b-a) Voici une table des résultats (ces temps sont approximatifs et dépendent évidemment du processeur, mais ils mettent bien en évidence les problèmes de la récursivité) :Didier Müller7-6août 2015
L'informatique au lycéeChapitre 7
Fonction récursive (fib1)Fonction itérative (fib2) kTemps (en secondes)Temps (en secondes)107⋅10-53⋅10-620
3⋅10-33⋅10-6300.5
3⋅10-64058
4⋅10-6507264
4⋅10-6Pourquoi une telle différence ? Pour le comprendre, il faut observer comment se passe le calcul
récursif. Calculons fib(5) avec la méthode récursive : fib(5) -> fib(4) + fib(3) -> (fib(3) + fib(2)) + fib(3) -> (fib(2) + fib(1)) + fib(2)) + fib(3) -> ((1 + fib(1)) + fib(2)) + fib(3) -> ((1 + 1) + fib(2)) + fib(3) -> (2 + fib(2)) + fib(3) -> (2 + 1) + fib(3) -> 3 + fib(3) -> 3 + (fib(2) + fib(1)) -> 3 + (1 + fib(1)) -> 3 + (1 + 1) -> 3 + 2 -> 5 On peut aussi représenter les appels de fonction dans un arbre.On voit que ce n'est pas efficace : par exemple, fib(3) est appelé deux fois, ce qui est une perte de
temps. De plus on imagine bien que l'arbre va devenir très vite gigantesque, avec un très grand
nombre d'appels inutiles.La mise en oeuvre des algorithmes récursifs nécessite le plus souvent une pile. C'est la difficulté
d'implanter cette pile ou d'éviter son emploi qui a fait dire pendant longtemps que les programmes
récursifs étaient moins efficaces que les programmes itératifs, mais la situation a changé. En fait, le
débat sur le choix entre codage récursif ou itératif est aussi vieux que l'informatique et les progrès de
la compilation des langages de programmation réduit encore la différence d'efficacité. Voici quelques
arguments en faveur de la présentation récursive :•La présentation récursive permet de présenter simplement des algorithmes beaucoup plus
astucieux (et donc plus efficaces) et cela a été admirablement montré par Tony Hoare avec son algorithme de tri rapide (Quicksort). •Les compilateurs d'aujourd'hui sont tellement astucieux que plus le programme leur est présenté de façon abstraite et sans effets de bord, plus ils peuvent mettre en oeuvre leurs optimisations et aboutir à des codes objets efficaces.Didier Müller7-7août 2015
Récursivité et fractales
•Des structures de données récursives ont été conçues pour leur efficacité. On ne voit pas
comment on pourrait exécuter sur elles des algorithmes non récursifs.Texte et images de
ce paragraphe tirés de [4], pp. 112-1147.4.Les tours de Hanoi Le casse-tête des tours de Hanoï est un jeu de réflexion consistant à déplacer des disques de diamètres différents d'une tour de " départ » à une tour d' " arrivée » en passant par une tour " intermédiaire » et ceci en un minimum de coups, tout en respectant les règles suivantes : •on ne peut pas déplacer plus d'un disque à la fois, •on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.On suppose que cette dernière règle est également respectée dans la configuration de départ.
Le problème mathématique des tours de Hanoï a été inventé par Édouard Lucas (1842-1891). Il est
publié dans le tome 3 de ses Récréations mathématiques, parues à titre posthume en 1892. Il
annonce que ce problème est dû à un de ses amis, N. Claus de Siam, prétendument professeur au
collège de Li-Sou-Stian (une double anagramme de Lucas d'Amiens, sa ville de naissance, et SaintLouis, le lycée où Lucas enseignait).
Sous le titre " Les brahmes tombent », Lucas relate que " N. Claus de Siam a vu, dans ses voyagespour la publication des écrits de l'illustre Fer-Fer-Tam-Tam, dans le grand temple de Bénarès, au-
dessous du dôme qui marque le centre du monde, trois aiguilles de diamant, plantées dans une dalle
d'airain, hautes d'une coudée et grosses comme le corps d'une abeille. Sur une de ces aiguilles,Dieu enfila au commencement des siècles, 64 disques d'or pur, le plus large reposant sur l'airain, et
les autres, de plus en plus étroits, superposés jusqu'au sommet. C'est la tour sacrée du Brahmâ. Nuit
et jour, les prêtres se succèdent sur les marches de l'autel, occupés à transporter la tour de la
première aiguille sur la troisième, sans s'écarter des règles fixes que nous venons d'indiquer, et qui
ont été imposées par Brahma. Quand tout sera fini, la tour et les brahmes tomberont, et ce sera la
fin des mondes !».Solution pour 3 disques
Un jeu à 64 disques requiert un minimum de 264-1 déplacements. En admettant qu'il faille 1seconde pour déplacer un disque, ce qui fait 86'400 déplacements par jour, la fin du jeu aurait lieu au
bout d'environ 213'000 milliards de jours, ce qui équivaut à peu près à 584,5 milliards d'années, soit
43 fois l'âge estimé de l'univers (13,7 milliards d'années selon certaines sources).
7.4.1.Résolution récursive
Pour résoudre le problème des tours de Hanoï, il faut raisonner récursivement. Pour fixer les
idées, prenons par exemple quatre disques. Parmi eux, un est remarquable : le plus grand. Il ne peut
être posé sur aucun autre, il est donc le plus contraignant à déplacer. Une solution idéale ne devrait
Didier Müller7-8août 2015
L'informatique au lycéeChapitre 7
déplacer ce disque qu'une seule fois. Nommons A, B et C les trois piquets, la pile de disques audépart sur A. Idéalement, donc, le plus grand disque sera déplacé de A à C en une seule fois. Comme
il ne peut être posé sur aucun autre disque - car il est le plus grand -, cela ne pourra se faire que si
aucun disque n'est présent sur C. Autrement dit, on ne pourra effectuer ce déplacement particulier
que si le grand disque est seul sur A, et que tous les autres disques sont sur B. Incidemment, nousvenons de réduire le problème : pour pouvoir déplacer nos quatre disques de A vers C, il faut d'abord
déplacer (seulement) trois disques de A vers B, puis déplacer le grand sur C, etnfin déplacer les trois
disques de B vers C.Le grand disque présente une autre particularité : il est le seul sur lequel on peut poser n'importe
lequel des autres disques. Donc, dans le cadre d'un déplacement des trois disques supérieurs, il n'a
aucune incidence : tout se passe comme s'il n'était pas là. Cette remarque nous amène à un constat
intéressant : on peut traiter le problème du déplacement des trois disques exactement de la même
manière que nous avons traité celui des quatre. La figure ci-dessous, dans sa partie droite, montre
comment la première des trois étapes peut elle-même être décomposée en trois " sous-étapes » :
déplacer les deux disques supérieurs, puis le disque inférieur, puis déplacer les deux disques
supérieurs. La troisième étape de la partie gauche pourrait être décomposée de la même façon.
Didier Müller7-9août 2015
Récursivité et fractales
En résumé, déplacer n disques de A vers C en passant par B consiste à :1.déplacer (n-1) disques de A vers B (en passant par C);
2.déplacer le plus grand disque de A vers C ;
3.déplacer (n-1) disques de B vers C (en passant par A).
Les étapes 1 et 3 peuvent elles-mêmes se décomposer selon le même principe, sauf que les rôles
des paquets sont intervertis. Par exemple, dans la première, on va de A vers B, donc forcément par
1'intermédiaire de C. Voici la marche à suivre, donnée sur deux niveaux :
1.déplacer (n-1) disques de A vers B (en passant par C);
1.1. déplacer (n-2) disques de A vers C (en passant par B);
1.2. déplacer un disque de A vers B ;
1.3. déplacer (n-2) disques de C vers B (en passant par A).
2.déplacer le plus grand disque de A vers C ;
3.déplacer (n-1) disques de B vers C (en passant par A).
3.1. déplacer (n-2) disques de B vers A (en passant par C);
3.2. déplacer un disque de B vers C ;
3.3. déplacer (n-2) disques de A vers C (en passant par B).
Et ainsi de suite...
Ce qui donne en Python :
def hanoi(n,de,a,par): if n>0: hanoi(n-1, de, par, a) print(de,"-->",a) hanoi(n-1, par, a, de) print("""Tours de Hanoi
Il faut deplacer les disques de la tour A vers la tour C n = int(input("Nombre de disques : ")) hanoi(n,"A","C","B")7.4.2.Résolution itérative
Il existe également une procédure itérative pour résoudre le problème des tours de Hanoï. Elle
consiste à effectuer successivement les deux déplacements suivants :•déplacer le plus petit disque d'un emplacement à l'emplacement suivant (de A vers B, de B
vers C, ou de C vers A) •déplacer un autre disqueet à poursuivre itérativement ces deux déplacements jusqu'à ce que la tour complète soit déplacée,
le dernier déplacement se limitant alors à celui du plus petit disque sur le sommet de la tour. L'action
de déplacer un autre disque est non ambiguë puisque, en dehors du plus petit disque, un seul mouvement d'un autre disque est possible.Contrairement à la procédure récursive, la procédure itérative n'utilise aucune mémorisation de
l'arbre des déplacements à effectuer et nécessite seulement de se souvenir si on doit déplacer le plus
petit disque ou non, et dans quel sens sont effectués les déplacements du petit disque. Il permet
également, à tout moment, de revenir à la situation de départ : il suffit pour cela d'inverser le sens
dans lequel se déplace le plus petit disque.Exercice 7.4Exercice 7.4
Écrivez un programme en Python résolvant les tours de Hanoï sans utiliser la récursivité. Vous
trouverez une ébauche sur le site web compagnon.Didier Müller7-10août 2015
L'informatique au lycéeChapitre 7
http://ow.ly/4tqwT7.5.Le compte est bon D'après le jeu " Des chiffres et des lettres » d'Armand Jammot (France 2).Le principe du jeu
En choisissant 6 nombres (on peut choisir plusieurs fois le même) dans l'ensemble {1, 2, 3, 4, 5,6, 7, 8, 9, 10, 25, 50, 75, 100} et en leur appliquant les quatre opérations élémentaires (addition,
soustraction, multiplication et division), il s'agit d'atteindre le résultat demandé (ceci est possible
dans 94% des cas). Tous les résultats des calculs intermédiaires doivent être des nombres entiers
positifs. Chacun des nombres (parmi ceux de départ et ceux obtenus par un calcul intermédiaire) ne
peut être utilisé qu'une fois au plus. Si le résultat demandé ne peut pas être atteint, il faut l'approcher
au plus près. Exemple : atteindre 952 avec les nombres 25, 50, 75, 100, 3, 6.100 + 3 = 103
103 x 6 = 618
618 x 75 = 46350
46350 / 50 = 927
927 +25 = 952
Algorithme de résolution
1.on sélectionne une paire de nombres
quotesdbs_dbs46.pdfusesText_46[PDF] La tour de monparnasse
[PDF] la tour de pise
[PDF] La tour de Pise a huit étages
[PDF] la tour de pise histoire des arts pdf
[PDF] La tour de Pise problème de math
[PDF] la tour de piseet scratch
[PDF] La tour de Shanghai/Géographie-Terminale technologique
[PDF] La Tour Eiffel
[PDF] La tour Eiffel (Art Plastique)
[PDF] La tour Eiffel : comparaisons et metaphores
[PDF] la tour eiffel a une masse d' environ 7200 tones pour une hauteur de 320 m
[PDF] la tour eiffel contexte historique
[PDF] la tour eiffel dans le monde
[PDF] la tour eiffel document