Inscription / Connexion Nouveau Sujet
Niveau Licence Maths 1e ann
Partager :

Algo : déplacer une pile

Posté par
mankathada
08-03-17 à 13:14

Bonjour, comment ça va ?

Voilà j'essaie de résoudre un algo assez casse tête, je vous dis l'énoncé :

Il y a trois tours dans un temple, dans une des tours on a 32 disques de pierres empilé du plus grand au plus petit.

A chaque fois qu'on vient pour prier, on doit déplacer un disque du sommet de la pile d'une tour à une autre en respectant 2 règles :

- on ne doit pas poser un disque sur un autre disque plus petit

- on ne déplace qu'un disque à la fois

Et le but est de transférer la pile de disques d'une tour à une autre en un minimum de mouvements.

Ca fait des heures que je me casse la tete, mais j'arrive pas à trouver la solution.

Merci pour votre aide.

Posté par
cocolaricotte
re : Algo : déplacer une pile 08-03-17 à 13:21

Bonjour

Regarde ce que tu pourrais trouver sur les tours de Hanoi

Posté par
mathafou Moderateur
re : Algo : déplacer une pile 08-03-17 à 13:33

Bonjour,

C'est avec le calcul des décimales de pi le gargarisme du programmeur, cette tour de Hanoï.

on ne compte plus le nombre de façons de résoudre ça.
choisir parmi les diverses méthodes proposées une méthode que tu pourrais imaginer toi-même.
et compatible avec ce que tu sais programmer (boucles, sous programmes récursifs, parcours d'arbres, étude mathématique conduisant à des suites etc...)

pour imaginer soi-même une méthode c'est comme d'hab : un travail d'introspection pour comprendre réellement ce qu'on fait quand on fait quelque chose.
comprendre ce que l'on fait quand on résout le problème à la main (avec un petit nombre de disques)

écrire un algorithme sera alors formaliser les opérations que l'on a identifiées dans ce qu'on fait vraiment à la main.

Posté par
carpediem
re : Algo : déplacer une pile 08-03-17 à 14:05

enfin la meilleure façon de faire est celle qui permet d'apprendre ... tout seul ...

Posté par
jsvdb
re : Algo : déplacer une pile 08-03-17 à 15:23

Et histoire de "visualiser" pour de petits nombres de disques :
On pige vite avec cette petite animation !
Sachant que pour 8 disques le nombre minimal est de 255 mouvements (j'ai réussi, avec un peu de patience, le niveau 6)... alors pour 32, je crois que je risque de manquer de patience.

Posté par
mathafou Moderateur
re : Algo : déplacer une pile 08-03-17 à 15:39

il parait que avec 64 disques c'est la fin du monde
("les Brahmes tombent" disait Sam Loyd, les bras me tombent pour ceux qui n'auraient pas saisi l'humour de Sam, j'avoue que je n'ai identifié le jeu de mot que parce que je l'ai lu)

Posté par
jsvdb
re : Algo : déplacer une pile 08-03-17 à 16:06

Ah oui ! Sam dit quelque chose ...

Posté par
sylvainc2
re : Algo : déplacer une pile 08-03-17 à 21:23

Il y a une méthode facile à apprendre et à exécuter pour un cerveau humain.  On visualise les 3 tiges comme si elles étaient placées sur un cercle, aux sommets d'un triangle équilatéral, et on applique les deux règles suivantes à répétition, 1,2,1,2,etc, jusqu'à avoir déplacé tous les disques:

1- déplacer le plus petit disque sur la tige suivante en tournant dans l'ordre, disons, horaire.
2- déplacer un autre disque (autre que le plus petit) selon le seul déplacement qui est légalement permis.

C'est facile à faire puisqu'il y a seulement deux sortes de déplacements possibles à apprendre, et aussi parce qu'au #2 on peut facilement reconnaitre, en regardant, quel disque il faut déplacer.

Avec cà on est certain de réussir dans le nombre minimum de coups.  On peut même faire une pause, noter où on est rendu, puis reprendre plus tard.

Posté par
mankathada
re : Algo : déplacer une pile 11-03-17 à 11:14

bonjour,

merci pour vos pistes je devrais réussir à le faire,

Je vous montrerai mon algo, et vous me direz si vous valider.

Posté par
alb12
re : Algo : déplacer une pile 11-03-17 à 12:04

on est impatient



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1741 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !