Comment analyser le problème de la Tour de Hanoï en utilisant Java

1. Source du problème de la Tour de Hanoï

La Tour de Hanoï, également connue sous le nom de Tour de Hanoï, est un jouet éducatif issu d'anciennes légendes indiennes. Lorsque Brahma a créé le monde, il a construit trois piliers de diamant. Sur un pilier, 64 disques d'or étaient empilés par ordre de taille, de bas en haut. Brahma a ordonné au brahmane de réorganiser les disques sur un autre pilier par ordre de taille à partir du bas. Et il est stipulé que le disque ne peut pas être agrandi sur le petit disque, et qu'un seul disque peut être déplacé entre les trois piliers à la fois

2. Analyse du problème

Commencez par un problème simple

Pensez-y 64 assiettes, Cela peut être difficile, on peut commencer avec 1 assiette, comme indiqué ci-dessous :

Une assiette

A -> sur le pilier La plaque est déplacée vers le pilier C

Il faut la déplacer une fois

Deux plaques

Lorsqu'il y a deux plaques, on peut également y parvenir de la manière suivante :

A -> >C B-> C

Doit bouger 3 fois

1 A -> B

2 -> les étapes de déplacement sont les suivantes :

A -> C A -> B A -> A B -> 1. A -> C

2. A -> A

6. B -> Compris Mouvement de 3 assiettes

Quand il y a 4 assiettes, ce problème est en fait très compliqué

Dérivation des règles

1 assiette bouge 1 fois

2 assiettes bouge 3 fois

3 plaques bougent 7 fois

......

N plaques bougent 2 ^ N - 1 fois

Ensuite, 64 plaques doivent être déplacées 2 ^ 64 - 1 fois

3. Nous pouvons résoudre ce problème par récursion et obtenir le bon Comment se déplacer

Comment se déplacer s'il y a N plaques ?

Idée générale

Nous pouvons d'abord déplacer N - 1 plaques de la colonne A à la colonne B à l'aide de la colonne C, puis déplacer la plaque restante de la colonne A à la colonne C, puis déplacer N - 1 plaques sur la colonne B. la plaque se déplace du pilier A au pilier C, complétant ainsi le mouvement de tous les piliers (le processus de déplacement spécifique au milieu ne sera pas abordé pour l'instant)

Téléchargez le code

public static void hanoi(int num, String src, String help, String dest) {
    if (num == 1) {     // 只有一个盘子的时候直接移动
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
    } else {
        hanoi(num - 1, src, dest, help);   // 将n - 1个盘子从源柱子借助目标柱子挪到辅助柱子
        System.out.print(src + "->" + dest + "  ");  // 将一个盘子从源柱子挪到目标柱子
        hanoi(num - 1, help, src, dest);  // 将辅助柱子上n - 1个盘子借助源柱子挪到目标柱子
    }
}
public static void main(String[] args) {
    hanoi(3, "A", "B", "C");
}

Dans ce code, src est le pilier source, aide est le pilier auxiliaire, et dest est le pilier cible

Il s'agit d'une récursion bidirectionnelle

Résultat d'exploitation :

Cela a permis de terminer avec succès le mouvement des plaques

4. ? Combien de temps faut-il pour déplacer 64 assiettes

Ici, nous supposons que les brahmanes sont très intelligents et peuvent connaître directement la bonne façon de se déplacer sans réfléchir. Il faut une seconde pour déplacer une assiette et continuer à bouger

.

Convertir 2^64 - 1 seconde en un an équivaut à environ 5849 4241 7355 ans (584,942 milliards d'années), et la Terre n'existe que depuis 4,5 milliards d'années, et la durée de vie attendue du système solaire est estimée à des dizaines de milliards d'années. années. Cela fait en réalité 584,942 milliards d'années. Sans parler du système solaire et de la Voie lactée, au moins toute vie sur terre, y compris les tours du Vatican, les temples, etc., a été anéantie depuis longtemps.

Prophéties associées

Il y a une prophétie selon laquelle lorsque cette chose sera terminée, l'univers sera détruit en un éclair. Certaines personnes croient également que les brahmanes déplacent encore les disques tout le temps.

Combien de temps faut-il à l'ordinateur pour déplacer 64 plaques ?

La fréquence centrale de mon ordinateur est de 2,90 GHz, soit 2,9 milliards d'opérations par seconde, donc le temps nécessaire pour se déplacer 2 ^ 64 - 1 fois est d'environ 201 ans

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!