La tour de Hanoï, entre jeu, algorithmes et fractals

[@EmilyLaMaline]

Préparer mon grand oral avec cette vidéo a été d'une simplicité inégalée. Merci beaucoup Benoît Rittaud pour ces explications simples et intéressantes.

[@mathis_plvz]

je fais aussi mon GO dessus, tu peux m'envoyer ce que tu as fais stp.

[@sabrifreih1538]

vous pouvez m'envoyer ce que vous avez fait mddrr

[@carosse3512]

@@sabrifreih1538 on est ensemble aha

[@mattedjon-veryaccuratetabs]

J'ai cliqué sur la vidéo en voyant sur la miniature quelque chose qui ressemblait à un jouet de mon bébé. Et c'est effectivement le cas ! J'aurais jamais cru qu'on puisse faire autant de chose avec !! Et c'est fascinant en plus, j'y ai passé l'après-midi. Un grand merci !

[@_Darrow_]

Merci! Grâce à cette vidéo j'ai préparé super facilement un bon grand oral.

[@Yanis-eh3hf]

Salut moi aussi je fais mon grand oral dessus c'est quoi ta problématique ?

[@_Darrow_]

@@Yanis-eh3hf Comment obtenir le nombre minimum de coups pour n disques de tours de Hanoi?

[@tidio__]

mdrr je fais aussi mon grand oral dessus

[@xque45]

Limpides explications ! Très clair même pour un novice ! Merci

[@troyblaine370]

Dont know if you guys gives a damn but if you're stoned like me during the covid times you can stream pretty much all of the latest movies and series on instaflixxer. Have been watching with my brother recently :)

[@tysondaxton3911]

@Troy Blaine yea, been using instaflixxer for months myself =)

[@gaellucas8705]

@Troy Blaine Yup, been watching on InstaFlixxer for years myself :)

[@eismaail]

Merci pour votre partage de connaissance, je viens de découvrir votre chaine et je me suis abonné de suite avant même de regarder la vidéo. ça me rappelle des souvenirs quand j'étais étudiant en Informatique. Il faut dire qu'un informaticien doit faire de temps en temps des exercices en algorithmique comme une sorte de sport pour le cerveau, et ça aide énormément à résoudre les problèmes dans le contexte du travail et à trouver les solutions le plus rapidement possible.

[@simonrancourt7834]

Souvenir : début années '80, dans mes.cours d'informatique, on avait eu comme exercice d'écrire un programme en utilisant l'algorithme récursif pour résoudre la tour à 7 disques. En COBOL. Sur cartes perforées.

[@youssfgh-x9l]

Merci . Le sujet que vous avez presenté est interessant . Mais c'est surtout la façon avec laquelle vous exposez qui m'interesse entant que pedagogue .

[@urluberlu2757]

Hé ben, c'est la deuxième vidéo que je regarde ce soir, et ça fait 2 fois que j'apprend de nouvelles choses sur un sujet auquel je me suis déjà intéressé. Merci 👍

[@Pio2001]

Très bien présenté ! Un autre casse-tête binaire connu est le baguenaudier. Le principe est le même, mais il est un peu plus difficile à appréhender car contrairement à ce qui se passe dans la tour de Hanoï, où ôter le petit disque d'un tas libère le disque immédiatement en-dessous, dans le baguenaudier, ôter le premier anneau libère l'anneau qui est derrière l'anneau qui est derrière lui (l'anneau n-2, si vous me suivez, et non l'anneau n-1). Mais il comporte de grandes similitudes avec la tour de Hanoï : une fois sur deux, c'est l'anneau du bout qui se déplace (ou les deux anneaux du bout), et une fois sur deux, un seul autre anneau est susceptible de se déplacer. Par contre, il n'y a pas de notion de "troisième piquet", de sorte que le graphe des configurations est totalement linéaire (si on excepte les configurations physiquement possibles, mais trivialement inutiles). Le baguenaudier a aussi la particularité d'avoir une position homogène à une extrémité du graphe (tous les anneaux sortis), mais l'autre positions homogène (tous les anneaux enfilés) se trouve au trois-quarts du graphe. On peut donc poursuivre jusqu'au bout du graphe, et après 2 puissance n mouvements, on se retrouve dans une position hétérogène (tous les anneaux ressortis, sauf le dernier, et c'ets la fin de la séquence). Cela a une conséquence redoutable sur la résolution du puzzle. Le point de départ, c'est d'avoir tous les anneaux enfilés. Si au départ on se trompe de direction en réalisant le premier mouvement, ce n'est qu'arrivé tout au bout de la séquence qu'on s'aperçoit qu'on s'est fourvoyé dans un gigantesque cul-de-sac ! Il existe également toute une catégorie de casse-tête itératifs, appelés "N-ary" puzzles par Goetz Schwandtner, grand collectionneur. Son site web (en anglais) contient plusieurs articles intéressants, pour peu qu'on fouille dans les diverses pages ( puzzles.schwandtner.info/ ).

[@KahlieNiven]

ahhhh le triangle de Sierpinsky....c'est lui qui m'avait poussé à l'apprentissage du basic sur cpc464 quand j'avais 9 ans (puis au codage et à l'algorithmique en général). (par contre le lien avec les tours de Hanoï, là, je le découvre)

[@Piffsnow]

Pour plus d'infos et aussi pour le lien entre la tour de Hanoï et le décompte en binaire, tu peux aller voir ces vidéos kzbin.info/www/bejne/aIS4p4qcg6-Gqa8 kzbin.info/www/bejne/mJWwl52ciZWfgc0

[@KahlieNiven]

@@Piffsnow merci pour le lien (déso pour la semaine de retard, c'est compliqué en ce moment).

[@Piffsnow]

@@KahlieNiven T'inquiète ^^ Je n'attendais pas particulièrement de réponse. :)

[@marcozini8915]

Pour la Tour de Hanoi, je propose une solution simple et mnémonique. La règle est la suivante: - déplacez le plus petit disque, circulairement, dans le sens des aiguilles d'une montre, de deux manières différentes: ˗ pour les disques pairs (2, 4, 6, 8…): a -> b -> c -> a ->… ˗ pour les disques impairs (1, 3, 5, 7, 9…): a -> c -> b -> a ... - déplacer le plus petit disque, des deux à gauche, sur le majeur, c'est la seule opération possible, - au prochain mouvement, déplacez à nouveau le plus petit disque de manière circulaire, comme vu ci-dessus - dans le prochain mouvement, déplacez le disque de la seule façon possible ... et ainsi de suite, jusqu'à ce que tous les disques du piquet initial "a" au piquet de destination finale "c" soient amenés. J'espère avoir été clair, merci pour votre attention et profitez-en.

[@lemaxdeculture-chainesecon6415]

Super vidéo ! Très clair et très instructif ! Merci beaucoup à vous !

[@mouradbelkas598]

Merci M. Rittaud, tres interessant, bravo tres bonne explication...

[@adrienlegras5552]

Encore une superbe vidéo !

[@sionelbaz9899]

OH SUBLIME LA TOUR DE HANOI n-disques dévoile le paradoxe de Zenon touchant à la course d'Achille et la tortue (sachant que là la tortue est représenté par le troisième piquet !!!!!! vu qu'elle est visiblement pas rapide !!! JOLI SUBLIME MERCIIIIIII !!!!

[@sionelbaz9899]

ACHILLE SUR LE PREMIER POTEAU :-)))))))

[@sionelbaz9899]

À MOINS de dire que Achille est un disque plus grand que celui qui représente la tortue !!!!!! superbe votre truc

[@MBJanus]

Il y a une trentaine d'années, grâce à l'aide d'Olivier Sotiriades, j'avais utilisé sa méthode pour tester la mémoire "implicite" de la résolution du jeu : même des sujets à la mémoire apparemment déficiente amelioraient leur performance. La méthode était généralisée pour aller d'une position quelconque à une autre au plus court, avec une solution unique. J'ai perdu mes notes sur le sujet, les paramètres mesurés étaient le nombre d'erreurs et la vitesse de résolution. Chaque position était nommée par 3 chiffres (1 par piquet) et la méthode était itérative et courte. Pourriez-vous après ces 30 ans m'aider à retrouver la méthode et la notation ? O. Sotiriades dont j'ai perdu l'adresse évoquait je crois l'avantage de la "godelisation" pour noter chaque position. J'aurais aimé compléter l'article dans le cas de certains troubles neuropsychiques non étudiés à l'époque, et comme je vous le disais j'ai perdu la méthode allant d'un lieu à l'autre au plus court. Merci en tout cas de votre vidéo. Cordialement, Milos [e-mail]

[@benoitrittaud492]

Une telle méthode figure sans doute dans le livre de Hinz (cf. la biblio du lien donné dans la présentation de la vidéo). Je ne l'ai pas sous la main, mais je vais voir si je peux la retrouver et je vous envoie un mail. Cordialement, BR.

[@ninayopstrom6201]

Bonjour MB, Le jeu de la tour de Hanoï est utilisé dans les logiciels de remédiation cognitive, pour aider à travailler vos capacités cognitives par exemple en situation de dépression. Vous avez par exemple le logiciel happyneurone.fr qui contient ce jeu et un autre qui y ressemble avec des paniers basket qui demande en plus de la mémoire car vous devez tout faire de tête. Le logiciel en question est utilisé dans les cliniques psychiatriques, par exemple dans des programmes pour gérer la dépression. (Je n'ai aucun lien avec le logiciel, je suis du côté utilisateur ^^)

[@Yann-je-dois-rajouter-un-truc]

Il m'a donné envie de me fabriquer une tour de Hanoï et de m'amuser avec, le con ^^

[@joelcherpin4533]

pareil,lol

[@MrSinalta]

ca tombe bien les gars, on va a voir un peu de temps a la maison

[@Electro_Mic]

J'en ai construit une il y a dix ans, un bout de bastaing pour la base, trois trous du diamètre d'un manche à balais, puis découper des carrés ou cercles de différents format. La toure que j'ai fait contient huit étages, tous mes enfants font régulièrement des concours pour résoudre les huit étages, c'est amusant, ça demande de la concentration et un peu de logique. Aujourd'hui mon plus grand passe un licence administrateur réseau, le deuxième est toujours premier de sa classe depuis la sixième et passe un BTS en fin d'année, et le troisième est premier dans les trois matières scientifique de quatrième, à savoir, maths, physique ainsi que science et vide de la Terre. Aucune idée si cela a pu avoir un impacte, mais bon... 🤔

[@rrgghuhgfvjhdrgfzejjg]

C'est beau .ça réveille les neurones.

[@ytrezazerty1]

c'est du binaire moins 1 , les 64 plateaux donnent la même somme de déplacements que les grains de riz cumulés sur l'échiquier de Sissa, il y a aussi 64 cases sur un échiquier.

[@RobertAparicio-mt4kk]

On place les tours sur un cercle. On définit le sens de rotation des pairs et des impairs. On déplace le plus gros possible. C'est une méthode avec reprise puisque le dernier ne se déplace qu'une seule fois et donc on peut déterminer à tout moment le sens de rotation.

[@ketzalkoatl5093]

Génial, merci pour cette excellente vidéo!

[@amineamine1980]

C'est juste magique,!!!

[@lemniskate_ayd]

Pour le triangle de Sierpiński, les « trous » sont des triangles et non pas des hexagones irréguliers (11:36). Est-ce qu’on peut alors considérer qu’il s’agit de triangles avec un nombre d’itérations très élevé ?

[@lemniskate_ayd]

Sinon, superbe vidéo !

[@benoitrittaud492]

C'est l'idée, oui. Par exemple, à mesure que le nombre de disques devient grand, le gros trou central du graphe est un hexagone dont trois côtés deviennent négligeables devant les trois autres, si bien qu'à la limite on a un triangle. (Bien sûr, tout ça devrait être écrit de façon plus rigoureuse.)

[@JeromeFortias]

Brillant et clair ! Merci énormément

[@dlep9221]

Brillant ! merci

[@DomOikos]

2^64-1 déplacements ... soit 584.5 milliard d'années si ils en déplacent 1 par seconde ... la fin du monde sera arrivée avant vu que le soleil se mort depuis longtemps

[@youssef5666]

bien bien avant en effet soleil encore 5 milliards d annees mais vu evolution soleil conditions impossible pour la vie dans moins d un milliard apres il y a l evolution des especes au pire quelques millions d annees avant homo sapien disparaisse enfin il y a la folie des humains a detruire les conditions de survie et la c est peut etre qu une question de siecles et encore je n integre ni catastrophe naturelle majeure ni epidemie ni guerre car dans ce cas la ca pourrait etre encore plus vite

[@Shmolitz]

Trop beau!

[@loucahoornaert6013]

Pourquoi le Z n'est pas en argument dans la partie récursivité ?

[@olivierlabatut9333]

passionnant !

[@pierrekilgoretrout3143]

Est-ce qu'on peut représenter une position par un nombre triadique? (3-adique) Dans ce cas, est-ce qu'il y a des opérations sur ces nombres qui représentent des mouvements intéressants, ou qui permettent d'analyser une position (p ex donner le nombre min ou max de mouvements restants)?

[@benoitrittaud492]

Il y a 3^n (notation pour 3 puissance n) états possibles du jeu. Il est donc en effet naturel d'exprimer chacune d'elles par un entier en base 3, qui n'est pas un nombre 3-adique mais simplement un entier à n chiffres. De la même façon, les états visités par la solution optimale sont au nombre de 2^n (un de plus que le nombre de déplacements, c'est l'histoire des piquets et des intervalles), donc on peut représenter ces états à l'aide d'un nombre à n chiffres en base 2. Il y a en effet plein de choses à dire dans cette direction, qui impliquent ce qu'on appelle les codes de Gray. Il y faudrait une deuxième vidéo…

[@Jeehd]

Mind blowing 💀

[@kibi4979]

J’adore. Merci

[@devue4183]

Super bien expliqué bravo.

[@xcrabe]

Génial, par contre je me pose la question, vous avez fait l'étude en modulant le nombre de disques, mais si on module le nombre de piquet, qu'est ce que cela donne???

[@benoitrittaud492]

C'est beaucoup plus difficile. Il y a des résultats récents dans le domaine, notamment de Thierry Bousch pour le jeu à 4 piquets : projecteuclid.org/euclid.bbms/1420071861

[@ikari38460]

@@benoitrittaud492 vraiment ? c'est contre intuitif, puisque 4 piquet permet de ne plus bouger une fois sur deux le plus petit mais une fois sur trois ... cela semble donc plus rapide. à moins qu'il y ai une règle supplémentaire.

[@benoitrittaud492]

@@ikari38460 Pardon, je reformule : c'est plus difficile de trouver l'algorithme optimal.

[@ikari38460]

@@benoitrittaud492 ha d'accord. merci de la précision :)

[@pierremartin867]

Marrant le nombre de déplacements des disques c'est la formule de la montante hawk à la roulette 🤩

[@razafindrabetokinirina]

J'aime ce jeu

[@xandutheil8767]

On l’avait étudié en td de math... c’est super intéressant je trouve

[@julien8279]

Salut, pourrais-je savoir en quelle année (quel cursus) tu as fait le td ?

[@xandutheil8767]

Ben Loti en mpsi et c’était un TD d’informatique en fait mais là grande partie des aspects de la video a été traités .

[@refusneant]

magnifique merci

[@ninovladovic2937]

Trop cool !

[@ao9779]

c'est beau : )

[@jules2pommes]

masterclass

[@ainsworth_elias]

C beau les maths !

[@jeromesnail]

Ce mindfuck à la fin !

[@ghoghoghogho325]

J'ai besoin de l'algorithme récursivité s'il vous plaît🙏🙏🙏🙏🙏🙏🙏

[@jjvv7578]

J'adore ce jeu , c'est le seul que je résous très vite . Pour aller plus vite , j'enlève les trois axes verticaux , qui ralentissent énormément les manipulations.

[@Tostakyful]

Je savais pas que les mathématiques pouvaient être belle

[@DanielBWilliams]

Haha, les mathématiques sont remplies de ce genre de choses !

[@gabrieldomain7820]

1:06 ce déplacement est interdit, un disque plus grand que celui qui est en dessous ne peut pas passet au dessus de celui-ci

[@benoitrittaud492]

La règle est : on ne *dépose* pas un disque sur un disque plus petit. À 1:06, le disque n'est pas déposé sur le disque plus petit, il passe directement sur le dernier piquet. Cela dit, votre remarque suggère une variante intéressante du jeu, je vais regarder.

[@benoitrittaud492]

Voilà, j'ai trouvé. Si on ajoute la contrainte qu'un disque ne peut aller du piquet initial au piquet final (ou l'inverse) qu'à condition qu''il ne passe pas "par dessus" un disque plus petit situé sur le piquet du milieu, on tombe alors sur une variante qui ressemble beaucoup à l'algorithme le plus lent. Le nombre de déplacements nécessaires est égal à 2×3^n - 1 (pour 1 disque, 2 disques, etc., ça donne 2, 5, 17, 53…). C'est un peu plus rapide que les 3^n - 1 de la solution la plus lente, parce qu'on a maintenant le droit de faire passer le petit disque directement du piquet initial au piquet final (et inversement) - mais il se trouve qu'il n'y a que lui qui peut le faire. C'est d'ailleurs ce qu'il fait dans cette variante, dont un algorithme est : on déplace le petit disque une fois sur deux en le faisant zigzaguer entres les piquets initial et final, et quand ce n'est pas à lui de bouger on fait l'unique autre déplacement possible. Détails à vérifier. En tout cas je ne crois pas que cette variante du jeu était connue !

[@youssef5666]

precision la nombre maximum de deplacement c est 3^n - 1 car il y a 3^n etats mais comme l etat de depart est l un de ces etats ca fait un deplacement de moins

[@angladephil]

Remarquable !

[@ikari38460]

il manque (Benoit Rittaud)

[@lockhart1895]

S'est pas du gateau

[@f-trt]

wha ! on peut jouer avec des fractale :-p

[@vincentcousin5332]

😲👍🏻

[@invanish]

j'aime phuong anh

[@plm7728]

ekip

[@3kornx]

C'est n'importe quoi. Le plus rapide c'est de tourner le jeu à 180°. Bim, solution en 1 coup !

[@herveborisfototalla6110]

😂🙄

[@herveborisfototalla6110]

😂🙄

[@billybob8836]

Je n'ai absolument rien compris car je suis une grosse nouille

[@DanielBWilliams]

Pas même les règles du jeu des tours de Hanoï ?

[@JohnnySimard]

Je me demande ? si les comptables en connaisse les ficelles , pour embobiner le client . les banquiers pour entourloupé ? Et les bourses pour tout affoler . Pas sur ? mais ce je sais , c'ait qu ils magouilles ha ha ha