Commentaires

Les tours de Hanoi

Les tours de Hanoi

La légende raconte que dans le grand temple de Varanasi, sous le dôme qui marque le centre du monde, se trouve une base en bronze sur laquelle sont fixées trois aiguilles en diamant d'un coude haut et l'épaisseur du corps d'une abeille .

Dans l'une de ces aiguilles, Dieu, au début des siècles, a placé soixante-quatre disques d'or pur, le plus grand sur la base de bronze, et les autres, par ordre décroissant de largeur, superposés au sommet. Voici la tour Brahma.

Jour et nuit, les prêtres se relaient dans l'occupation de transporter la tour de la première aiguille en diamant à la troisième, sans s'écarter des règles fixes et immuables imposées par Brahma: le prêtre ne doit pas déplacer plus d'un disque à la fois et vous ne devez pas placer un disque autre qu'une aiguille libre ou un disque plus gros. En suivant strictement ces recommandations, les soixante-quatre disques ont été transférés de l'aiguille dans laquelle Dieu les a placés au troisième, la tour et les brahmanes deviendront de la poussière et seront la fin du monde.

En supposant que les prêtres pouvaient bouger à chaque seconde,

Combien de temps faudra-t-il pour atteindre la fin du monde?

Solution

Le nombre minimum de coups pour résoudre le problème est de 2n - 1, étant n le nombre de disques, dans ce cas 64. Si nous effectuons le calcul, nous obtenons que 18 446 744 073 709 551 615 mouvements d'une seconde chacun sont nécessaires, ce qui représente environ 585 000 000 000 d'années.

Vous pouvez trouver plus d'informations sur l'approche et la résolution de ce problème sur cette page et dans le wikipedia.

Vidéo: La Tour De Hanoï Démonstration De La solution (Mai 2020).