A la demande générale (ou pas), la version itérative
# Classiques
def is_empty(stack):
return len(stack) == 0
def top(stack):
return stack[len(stack)-1]
# Déplacer le disque du haut de la tour x
# vers la tour y.
def deplacer(tours, x, y):
tours[y].append(tours[x].pop())
print(tours);
# Faire un mouvement entre les tours x et y.
# Oui mais lequel ?
# Facile : celui qui est possible.
def mouvement(tours, x, y):
if is_empty(tours[x]) :
deplacer(tours, y, x)
elif is_empty(tours[y]) :
deplacer(tours, x, y)
elif top(tours[x]) < top(tours[y]) :
deplacer(tours, x, y)
else:
deplacer(tours, y, x)
# Et voila
def hanoi(n):
tours = [ [ n-i for i in range(n) ], [], [] ]
(a,b,c) = (1,2,0) if (n%2 == 1) else (2,1,0)
while not is_empty(tours[0]) or not is_empty(tours[1]):
mouvement(tours, b, c)
(a, b, c) = (b, c, a)
Si ça te prend une démonstration pour voir qu'une liste de liste est plus complexe qu'une liste, je démissionne d'essayer.
> on sait utiliser une liste Python.
Ha bon, je ne sais pas utiliser une liste Python? Démontres-moi ça.
>on a assez de capacité d'abstraction : 1) on représente un disque par un nombre - son diamètre - , et 2) une tige par une liste de nombres)
Pour l'abstraction, je peux bien te faire une liste de dictionnaires de listes de tuples si ça t'amuse.
Pour le diamètre, c'est ce que j'ai fait, regardes mon code. As-tu copié sur moi?
Chaque tige était bien représenté par une liste.
> def hanoi(n):
> print("et voila")
Il y a un lien "Voter pour cette réponse" mais pas de lien "Votez contre cette réponse"
Le PO a écrit à l'origine:
> T0 = [ 0, 1, 2, 3, 4, 5, 6, 7 ]
> #Disques de diamêtres 0 à 7, empilés du plus petit sur le plus grand
> T1 = [ [],[],[],[], [],[],[],[] ]
> T2 = [ [],[],[],[], [],[],[],[] ]
Il était parti pour faire 3 listes de listes (sauf la première). C'est ça que je n'amais pas.
yo@n97one a écrit:
PS 2 : @michelbillaud en fait j'ai l'impression qu'il préfère une solution avec trois listes et hanoi qui prend en paramètre ces trois listes (qu'on peut donc afficher).
Hé voilà!
@michelbillaud: ceci dit, j'aime bien ta version itérative.
PascalOrtiz a écrit:
Comprends pas pourquoi ce fil est en train de s'enflammer comme ça.
C'est une longue histoire entre Michel et moi.
- Edité par PierrotLeFou 27 mai 2020 à 18:41:51
Le Tout est souvent plus grand que la somme de ses parties.
Je n'ai absolument aucune prétention d'originalité sur le code, qui est une version en python de trucs qu'on voit partout depuis les débuts de la programmation.
PS: j'ai l'impression que tu comprends complètement de travers ce que je raconte. J'expliquais que faire un tableau de 3 listes au lieu de 3 listes, ça n'avait rien de plus compliqué que de faire un tableau de 3 nombres au lieu d'avoir 3 nombres.
Apparemment, ton argument, c'est que tu trouves ça lourd parce que tu n'aimes pas ? Et que tu n'aimes pas parce que tu trouves ça lourd ? :-)
Je n'ai absolument aucune prétention d'originalité sur le code, qui est une version en python de trucs qu'on voit partout depuis les débuts de la programmation.
PS: j'ai l'impression que tu comprends complètement de travers ce que je raconte. J'expliquais que faire un tableau de 3 listes au lieu de 3 listes, ça n'avait rien de plus compliqué que de faire un tableau de 3 nombres au lieu d'avoir 3 nombres.
Apparemment, ton argument, c'est que tu trouves ça lourd parce que tu n'aimes pas ? Et que tu n'aimes pas parce que tu trouves ça lourd ? :-)
- Edité par michelbillaud il y a 2 minutes
Je n'ai jamais prétendu que mon code était également original. J'ai même dit que j'avais pris l'algorithme sur Wikipedia.
Il se peut que je ne t'ai pas compris.
Comme je viens de le dire, je n'aimais pas l'idée d'avoir 3 listes de listes.
Faire UNE liste de liste comme tu l'as fait est tout de même à mon goût.
Le Tout est souvent plus grand que la somme de ses parties.
(pas d'affichage, pas de manipulation de listes) il met déjà environ 12s. Et grosso modo, ajouter un disque double le temps de calcul donc, ça va très vite saturer.
J'ai aussi essayé un code itératif «naif» :
n = 6
M = [] # les mouvements (from, to)
dstn = 2 if n % 2 == 1 else 1
med = 1 if n % 2 == 1 else 2
tiges = [list(range(1, n + 1))[::-1], [], []]
print(tiges)
for d in range(1, n + 1):
# Déplace la pile de d disques les plus hauts
# de la tige 0 vers la bonne tige (1 ou 2)
# Déplacement du d-ème disque à partir du haut
top = tiges[0].pop()
tiges[dstn].append(top)
# Déplacement du disque
temp = [(0, dstn)]
# Astuce pour renuméroter
t = [1, 2, 0] if med == 1 else [2, 0, 1]
# 2e déplacement des d-1 disques plus élévés
for (a, b) in M:
top = tiges[t[a]].pop()
tiges[t[b]].append(top)
temp += [(t[a], t[b])]
print(tiges)
# la nouvelles liste des mouvements
M.extend(temp)
dstn, med = 3 - dstn, 3 - med
Ci-dessus, j'ai affiché l'état du jeu à chaque fin d'étape de la boucle. L'idée est simple, l'étape d de la boucle déplace les d disques les plus hauts de la pile de gauche. L'étape d+1 consiste à déplacer deux fois les d disques les plus hauts : le premier déplacement est mémorisé et le 2e singe le premier en renumérotant. Comme les déplacements sont tous mémorisés, le coût est élevé. Ce serait peut-être possible de l'alléger en utilisant un itérateur (deux itérateurs à chaque étape). Sans doute la méthode la plus rapide serait d'utiliser la périodicité de 12 signalée par Michel et que j'ignorais.
Il me semble que le nombre d'itérations (ou lignes affichées) est pour la solution optimale de 2^n
On peut imaginer ce que ça donne pour n=64.
Ça ne fait pas partie de la légende que des moines "dans le ciel" sont en train de le faire et que lorsqu'ils auront fini, ce sera la fin du monde? ...
Je prend note de ton code itératif et celui de Michel et je vais voir si je peux trouver quelque chose.
Edit:
Le nombre de déplacements est 2^n - 1 et non 2^n
@PascalOrtiz: j'ai pris ton code simplifié pour le calculer, paresse oblige.
C'est évident pour de petits nombres comme 1, 2 ou 3
- Edité par PierrotLeFou 29 mai 2020 à 3:37:08
Le Tout est souvent plus grand que la somme de ses parties.
Vous aussi ça vous est arrivé d'avoir des révélation de code pendant vos rêves? Mais là honnêtement je vois pas où cette prof voulait en venir (quoique visuellement je vois apparaître le disque le moins large "0" au sommet et ainsi de suite). Enfin bref, pas eu le temps de dormir plus malheureusement
A force de parler de listes, de listes de listes (Et Pierrot qui a imaginé des listes de listes de listes), il y a eu une notion de récursivité qui s'est déclenchée tout d'un coup.
C'est normal, quand on passe un moment sur un problème , le cerveau continue à bricoler dessus. A sa façon, donc pas toujours raisonnablement.
Pas de révélation dans les rêves, mais j'ai le souvenir d'un bug dans un programme qui était de côté depuis une bonne semaine, et dont la solution m'est tombée dessus alors que je faisais la vaisselle, et que je n'y pensais absolument pas (en pleines vacances, après le repas pas léger du dimanche de Paques, imaginez). Ça fait bizarre.
Ça s'utilise pour être efficace : quand on on a un truc à faire, on y regarde de près très tôt. Si ça coince, on peut passer à autre chose, il y a des chances que ça avance tout seul quand même, et qu'on ait les idées plus claires quand on s'y remettra. Mais faut commencer en avance.
Il m'arrivait régulièrement de trouver des bugs dans le métro alors que j'avais bossé dessus toute la journée sans rien trouver.
L'inconscient a ses raisons que la raison ignore ...
C'est que le repos du cerveau a son importance, ne surtout pas le négliger...
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Où est-ce que j'ai mis une assignation à global compteur ?
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Montre ton code dans les balises adaptées, je ne vois pas où ça ne fonctionnerait pas... Tu as le même message d'erreur ?
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Ouais donc c'est pas le même message d'erreur, donc la question précédente est résolue.
Le message d'erreur suivant est clair pourtant, regarde à ce que compteur ne dépasse pas la longueur max de T.
Fait un print(compteur) et len(T), ça devrait te donner une idée de l'erreur.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Ouais donc c'est pas le même message d'erreur, donc la question précédente est résolue.
Le message d'erreur suivant est clair pourtant, regarde à ce que compteur ne dépasse pas la longueur max de T.
Fait un print(compteur) et len(T), ça devrait te donner une idée de l'erreur.
T a en effet une longueur par rapport au nombre d'élément de la liste, mais pour compteur (valeur numérique) je ne vois pas
- Edité par Rambert111 il y a environ 1 heure
C'est peut-être la variable i ?
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Le problème c'est que si tu supprimes des éléments de T, len(T) n'est plus constant, du coup ça merde dans les index...
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
def hanoi(i, j):
if i == j :
k=0
if i % 2 == 0 :
k = (k + 1) % 3
print("Déplace le disque", i,"->",k,"tour plus loin"); print()
else:
k = (k + 2) % 3
print("Déplace le disque", i,"-->",k,"tours plus loin"); print()
else:
hanoi(i, j - 1)
hanoi(j, j)
hanoi(i, j - 1)
hanoi(0, 7)
Déplace le disque 0 -> 1 tour plus loin
Déplace le disque 1 --> 2 tours plus loin
Déplace le disque 0 -> 1 tour plus loin
# Si le disque est en T2, faire +1 tour "plus loin" revient à revenir à T0
Déplace le disque 2 -> 1 tour plus loin
Déplace le disque 0 -> 1 tour plus loin
Déplace le disque 1 --> 2 tours plus loin
Déplace le disque 0 -> 1 tour plus loin
Déplace le disque 3 --> 2 tours plus loin
..
Bon. Là j'affiche ce de quoi un débutant se serait contenté. Mais je veux voir chaque étape du jeu avec des listes. Le problème c'est j'ai pas encore l'astuce pour récupérer la valeur du compteur k qui se réinitialise à zéro (initialisation obligatoire car variable non dans la fonction et là j'avoue que j'ai laissé tombé la manip de variable globale) chaque tour, afin de dire quel disque i doit aller dans quelle liste 0, 1 ou 2 par étape.
J'essaye comme ça
def hanoi(i, j):
if i == j :
if i % 2 == 0 :
k=+1
k = (k + 1) % 3
print("Déplace le disque", i,"->",k,"tour plus loin"); print()
else:
k=+2
k = (k + 2) % 3
print("Déplace le disque", i,"-->",k,"tours plus loin"); print()
else:
hanoi(i, j - 1)
hanoi(j, j)
hanoi(i, j - 1)
hanoi(0, 7)
Déplace le disque 0 -> 2 tour plus loin
Déplace le disque 1 --> 1 tours plus loin
Déplace le disque 0 -> 2 tour plus loin
Déplace le disque 2 -> 2 tour plus loin
Déplace le disque 0 -> 2 tour plus loin
Déplace le disque 1 --> 1 tours plus loin
Déplace le disque 0 -> 2 tour plus loin
Déplace le disque 3 --> 1 tours plus loin
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Découverte Python Doc Tkinter Les chaînes de caractères
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Le Tout est souvent plus grand que la somme de ses parties.