Tour d'Hanoï : Différence entre versions

(Page créée avec « {{Tuto Details |Licences=Attribution (CC-BY) |Description=Le jeu des tours d'Hanoï est un jeu simple qui permet de comprendre la notion d'algorithme. |Disciplines scienti... »)
 
Ligne 1 : Ligne 1 :
 
{{Tuto Details
 
{{Tuto Details
 +
|Main_Picture=Tour_d_Hano__IMG_20200504_175352634.jpg
 
|Licences=Attribution (CC-BY)
 
|Licences=Attribution (CC-BY)
 
|Description=Le jeu des tours d'Hanoï est un jeu simple qui permet de comprendre la notion d'algorithme.
 
|Description=Le jeu des tours d'Hanoï est un jeu simple qui permet de comprendre la notion d'algorithme.
Ligne 9 : Ligne 10 :
 
}}
 
}}
 
{{Introduction
 
{{Introduction
|Introduction=Avant de se lancer dans le jeu, il faut le construire. Rien de plus simple : du carton, du papier, un peu de bricolage et hop, c'est prêt !
+
|Introduction=Avant de se lancer dans le jeu, il faut le construire. Rien de plus simple : du carton, des cure-dents, des ciseaux et des feutres, un peu de bricolage et hop, c'est prêt !
 +
 
 +
 
 +
La Tour d'Hanoï est un jeu constitué de disques de différentes tailles empilées sur une tige. Le principe du jeu est de déplacer la pile de disques d'une tige à l'autre.
 
}}
 
}}
 
{{Materials
 
{{Materials
Ligne 15 : Ligne 19 :
 
|Item=Carton
 
|Item=Carton
 
}}{{ItemList
 
}}{{ItemList
|Item=Feuille papier 80g
+
|Item=Ciseaux
 +
}}{{ItemList
 +
|Item=Scotch
 
}}{{ItemList
 
}}{{ItemList
|Item=Colle
+
|Item=Polystyrène
 
}}{{ItemList
 
}}{{ItemList
|Item=Ciseaux
+
|Item=Feutre de couleur
 +
}}{{ItemList
 +
|Item=Compas
 
}}{{ItemList
 
}}{{ItemList
|Item=Scotch
+
|Item=Cure-dents
}}{{ItemList}}
+
}}
 +
}}
 +
{{Tuto Step
 +
|Step_Title=Construire les cercles
 +
|Step_Content=Sur du carton, tracer 5 cercles de diamètres différents.
 +
 
 +
Les découper et les décorer.
 +
|Step_Picture_00=Tour_d_Hano__IMG_20200504_145111212.jpg
 +
|Step_Picture_01=Tour_d_Hano__IMG_20200504_150224387.jpg
 +
|Step_Picture_02=Tour_d_Hano__IMG_20200504_152018853.jpg
 +
}}
 +
{{Tuto Step
 +
|Step_Title=Préparer le plateau de jeu
 +
|Step_Content=Planter 3 cure-dents dans le bloc de polystyrène.
 +
 
 +
 
 +
Attention, il faut que les 3 cure-dents soient suffisamment éloignés.
 +
|Step_Picture_00=Tour_d_Hano__IMG_20200504_152147052.jpg
 +
}}
 +
{{Tuto Step
 +
|Step_Title=Préparer le jeu
 +
|Step_Content=Faire un trou dans chacun des disques préparés à l'étape 1.
 +
 
 +
 
 +
Sur le pic numéro 1, empiler les différents disques du plus grand au plus petit.
 +
|Step_Picture_00=Tour_d_Hano__IMG_20200504_152158086.jpg
 
}}
 
}}
 
{{Tuto Step
 
{{Tuto Step
|Step_Title=Construire le jeu
+
|Step_Title=Jouer
 +
|Step_Content=Le but du jeu est de déplacer toute la pile du pic numéro 1 sur un autre pic.
 +
 
 +
 
 +
Les règles du jeu sont les suivantes :
 +
 
 +
- on ne peut déplacer qu'un seul disque à la fois (toujours un disque qui est sur le haut d'une pile)
 +
 
 +
- on ne peut pas mettre un grand disque sur un plus petit (comme sur la photo 2)
 +
 
 +
 
 +
Chaque déplacement de disque compte pour un mouvement. Il faut essayer de faire le moins de déplacements possibles.
 +
|Step_Picture_00=Tour_d_Hano__IMG_20200504_152306156.jpg
 +
|Step_Picture_01=Tour_d_Hano__IMG_20200504_152238000.jpg
 +
|Step_Picture_01_annotation={"version":"3.5.0","objects":[{"type":"image","version":"3.5.0","originX":"left","originY":"top","left":-3,"top":0,"width":2976,"height":3968,"fill":"rgb(0,0,0)","stroke":null,"strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":0.2,"scaleY":0.2,"angle":0,"flipX":false,"flipY":false,"opacity":1,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"crossOrigin":"","cropX":0,"cropY":0,"src":"https://www.wikidebrouillard.org/images/9/9d/Tour_d_Hano_IMG_20200504_152238000.jpg","filters":[]},{"type":"textbox","version":"3.5.0","originX":"center","originY":"center","left":534.99,"top":291,"width":120,"height":22.6,"fill":"#0054FF","stroke":"#0054FF","strokeWidth":1,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":1,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"text":"Petit disque","fontSize":20,"fontWeight":"normal","fontFamily":"sans-serif","fontStyle":"normal","lineHeight":1.16,"underline":false,"overline":false,"linethrough":false,"textAlign":"left","textBackgroundColor":"","charSpacing":0,"minWidth":20,"splitByGrapheme":false,"styles":{} },{"type":"textbox","version":"3.5.0","originX":"center","originY":"center","left":108.27,"top":268,"width":137.47,"height":22.6,"fill":"#000000","stroke":"#000000","strokeWidth":1,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":1,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"text":"Grand disque","fontSize":20,"fontWeight":"normal","fontFamily":"sans-serif","fontStyle":"normal","lineHeight":1.16,"underline":false,"overline":false,"linethrough":false,"textAlign":"left","textBackgroundColor":"","charSpacing":0,"minWidth":20,"splitByGrapheme":false,"styles":{} },{"type":"wfarrow2line","version":"3.5.0","originX":"center","originY":"center","left":443.5,"top":265,"width":53,"height":32,"fill":"rgba(255,0,0,0)","stroke":"#0054FF","strokeWidth":4,"strokeDashArray":null,"strokeLineCap":"round","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":1,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"x1":26.5,"x2":-26.5,"y1":16,"y2":-16,"x2a":-13.513663886772822,"y2a":1.1858975428777558,"x2b":-5.243758302230144,"y2b":-12.511133581521056},{"type":"wfarrow2circle","version":"3.5.0","originX":"center","originY":"center","left":470,"top":281,"width":16,"height":16,"fill":"#aaa","stroke":"#666","strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":0.5,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"radius":8,"startAngle":0,"endAngle":6.283185307179586},{"type":"wfarrow2circle","version":"3.5.0","originX":"center","originY":"center","left":417,"top":249,"width":16,"height":16,"fill":"#aaa","stroke":"#666","strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":0.5,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"radius":8,"startAngle":0,"endAngle":6.283185307179586},{"type":"wfarrow2line","version":"3.5.0","originX":"center","originY":"center","left":145,"top":208,"width":98,"height":78,"fill":"rgba(255,0,0,0)","stroke":"#000000","strokeWidth":4,"strokeDashArray":null,"strokeLineCap":"round","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":1,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"x1":-49,"x2":49,"y1":39,"y2":-39,"x2a":38.3334820680096,"y2a":-20.28569009537014,"x2b":28.369549149503598,"y2b":-32.804477608364856},{"type":"wfarrow2circle","version":"3.5.0","originX":"center","originY":"center","left":96,"top":247,"width":16,"height":16,"fill":"#aaa","stroke":"#666","strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":0.5,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"radius":8,"startAngle":0,"endAngle":6.283185307179586},{"type":"wfarrow2circle","version":"3.5.0","originX":"center","originY":"center","left":194,"top":169,"width":16,"height":16,"fill":"#aaa","stroke":"#666","strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":0.5,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"radius":8,"startAngle":0,"endAngle":6.283185307179586},{"type":"wfline","version":"3.5.0","originX":"center","originY":"center","left":311,"top":157.5,"width":522,"height":215,"fill":"rgba(255,0,0,0)","stroke":"#FF0000","strokeWidth":4,"strokeDashArray":null,"strokeLineCap":"round","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":1,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"x1":-261,"x2":261,"y1":-107.5,"y2":107.5},{"type":"wfarrow2circle","version":"3.5.0","originX":"center","originY":"center","left":50,"top":50,"width":16,"height":16,"fill":"#aaa","stroke":"#666","strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":0.5,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"radius":8,"startAngle":0,"endAngle":6.283185307179586},{"type":"wfarrow2circle","version":"3.5.0","originX":"center","originY":"center","left":572,"top":265,"width":16,"height":16,"fill":"#aaa","stroke":"#666","strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":0.5,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"radius":8,"startAngle":0,"endAngle":6.283185307179586},{"type":"wfline","version":"3.5.0","originX":"center","originY":"center","left":308,"top":163.5,"width":518,"height":259,"fill":"rgba(255,0,0,0)","stroke":"#FF0000","strokeWidth":4,"strokeDashArray":null,"strokeLineCap":"round","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":1,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"x1":-259,"x2":259,"y1":129.5,"y2":-129.5},{"type":"wfarrow2circle","version":"3.5.0","originX":"center","originY":"center","left":49,"top":293,"width":16,"height":16,"fill":"#aaa","stroke":"#666","strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":0.5,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"radius":8,"startAngle":0,"endAngle":6.283185307179586},{"type":"wfarrow2circle","version":"3.5.0","originX":"center","originY":"center","left":567,"top":34,"width":16,"height":16,"fill":"#aaa","stroke":"#666","strokeWidth":0,"strokeDashArray":null,"strokeLineCap":"butt","strokeDashOffset":0,"strokeLineJoin":"miter","strokeMiterLimit":4,"scaleX":1,"scaleY":1,"angle":0,"flipX":false,"flipY":false,"opacity":0.5,"shadow":null,"visible":true,"clipTo":null,"backgroundColor":"","fillRule":"nonzero","paintFirst":"fill","globalCompositeOperation":"source-over","transformMatrix":null,"skewX":0,"skewY":0,"radius":8,"startAngle":0,"endAngle":6.283185307179586}],"height":450,"width":600}
 +
}}
 +
{{Notes
 +
|Observations=Il faut tester plusieurs combinaisons pour réussir ce défi.
 +
 
 +
<br />
 +
|Avertissement=Attention à bien respecter les règles du jeu :
 +
 
 +
- jamais un grand disque sur un petit
 +
 
 +
- toujours 1 seul disque déplacé à la fois.
 +
|Explanations=La Tour d'Hanoï permet de comprendre la notion d'algorithme : on refait plusieurs fois la même séquence d'actions qui visent  reformer une pile de disques de plus en plus grands sur une autre tige.
 +
 
 +
 
 +
Pour déplacer une tour de n disques, il faut au minimum (2^n)-1 déplacements (lire : "2 puissance n, moins 1")
 +
|Applications=Les programmes informatiques intègrent des algorithmes, qui permettent d'augmenter la vitesse de calcul.
 +
|Animation=Pour prendre en main plus facilement le jeu et éviter que le participant se décourage trop vite, on peut commencer à lancer le défi avec seulement 3 disques, à déplacer d'une tige  à l'autre.  Cela permet de comprendre la base de l'algorithme :
 +
 
 +
# Déplacer le petit disque sur une tige, puis le moyen sur un autre.
 +
# Mettre le petit disque sur le moyen pour libérer une tige.
 +
# Déplacer le grand disque sur la tige ainsi libérée.
 +
# Déplacer le petit disque pour libérer le moyen.
 +
# Déplacer le moyen sur le grand
 +
# Et enfin remettre le petit sur le haut de la pile !
 +
 
 +
 
 +
Une fois que ce mécanisme est compris, on peut introduire un disque supplémentaire, puis un autre.
 +
 
 +
Avec 5 disques, il faut faire au minimum 31 mouvements.
 +
|Notes=Pour tester en ligne la Tour d'Hanoï et lire la légende qui s'y rapporte : http://sorciersdesalem.math.cnrs.fr/Vulgarisation/Hanoi/hanoi.html
 +
 
 +
Explication du lien entre les tours d'Hanoï et le code binaire, pour les plus initiés : https://www.nagwa.com/fr/videos/323158594734/
 +
 
 +
 
 +
 
 +
<br />
 
}}
 
}}
{{Notes}}
 
 
{{Tuto Status
 
{{Tuto Status
 
|Complete=Draft
 
|Complete=Draft
 
}}
 
}}

Version du 4 mai 2020 à 17:34

Auteur avatarGwen72 | Dernière modification 4/05/2020 par Gwen72

Tour d Hano IMG 20200504 175352634.jpg

Introduction

Avant de se lancer dans le jeu, il faut le construire. Rien de plus simple : du carton, des cure-dents, des ciseaux et des feutres, un peu de bricolage et hop, c'est prêt !


La Tour d'Hanoï est un jeu constitué de disques de différentes tailles empilées sur une tige. Le principe du jeu est de déplacer la pile de disques d'une tige à l'autre.

Étape 1 - Construire les cercles

Sur du carton, tracer 5 cercles de diamètres différents.

Les découper et les décorer.


Étape 2 - Préparer le plateau de jeu

Planter 3 cure-dents dans le bloc de polystyrène.


Attention, il faut que les 3 cure-dents soient suffisamment éloignés.




Étape 3 - Préparer le jeu

Faire un trou dans chacun des disques préparés à l'étape 1.


Sur le pic numéro 1, empiler les différents disques du plus grand au plus petit.




Étape 4 - Jouer

Le but du jeu est de déplacer toute la pile du pic numéro 1 sur un autre pic.


Les règles du jeu sont les suivantes :

- on ne peut déplacer qu'un seul disque à la fois (toujours un disque qui est sur le haut d'une pile)

- on ne peut pas mettre un grand disque sur un plus petit (comme sur la photo 2)


Chaque déplacement de disque compte pour un mouvement. Il faut essayer de faire le moins de déplacements possibles.



Comment ça marche ?

Observations : que voit-on ?

Il faut tester plusieurs combinaisons pour réussir ce défi.


Mise en garde : qu'est-ce qui pourrait faire rater l'expérience ?

Attention à bien respecter les règles du jeu :

- jamais un grand disque sur un petit

- toujours 1 seul disque déplacé à la fois.

Explications

La Tour d'Hanoï permet de comprendre la notion d'algorithme : on refait plusieurs fois la même séquence d'actions qui visent reformer une pile de disques de plus en plus grands sur une autre tige.


Pour déplacer une tour de n disques, il faut au minimum (2^n)-1 déplacements (lire : "2 puissance n, moins 1")

Applications : dans la vie de tous les jours

Les programmes informatiques intègrent des algorithmes, qui permettent d'augmenter la vitesse de calcul.

Éléments pédagogiques

Pistes pour animer l'expérience

Pour prendre en main plus facilement le jeu et éviter que le participant se décourage trop vite, on peut commencer à lancer le défi avec seulement 3 disques, à déplacer d'une tige à l'autre. Cela permet de comprendre la base de l'algorithme :

  1. Déplacer le petit disque sur une tige, puis le moyen sur un autre.
  2. Mettre le petit disque sur le moyen pour libérer une tige.
  3. Déplacer le grand disque sur la tige ainsi libérée.
  4. Déplacer le petit disque pour libérer le moyen.
  5. Déplacer le moyen sur le grand
  6. Et enfin remettre le petit sur le haut de la pile !


Une fois que ce mécanisme est compris, on peut introduire un disque supplémentaire, puis un autre.

Avec 5 disques, il faut faire au minimum 31 mouvements.

Sources et ressources

Pour tester en ligne la Tour d'Hanoï et lire la légende qui s'y rapporte : http://sorciersdesalem.math.cnrs.fr/Vulgarisation/Hanoi/hanoi.html

Explication du lien entre les tours d'Hanoï et le code binaire, pour les plus initiés : https://www.nagwa.com/fr/videos/323158594734/



Dernière modification 4/05/2020 par user:Gwen72.

Commentaires

Draft