Javaを使用してハノイの塔問題を分析する方法

1. ハノイの塔問題の原因

ハノイの塔としても知られるハノイの塔は、古代インドの伝説に由来する知育玩具です。ブラフマー神が世界を創造したとき、3本のダイヤモンドの柱を作り、1本の柱には64枚の金の円盤を下から上に大きさの順に積み上げました。ブラフマーはバラモンに、別の柱の上にある円盤を下から大きい順に並べ替えるよう命じました。そして、小さな円盤では円盤を拡大することはできず、3 つの柱の間で一度に移動できる円盤は 1 つだけであると規定されています

に直接移動できます。

1. A ->B

##2. A -> C

3. B -> C

プレート 3 枚

##2. A -> B

# 3. C -> B

#4. A -> C

## 5. B -> A

6. B -> C

7. A -> C

これで3枚の板の移動が完了です

ルール導出

1 枚のプレート 1 回移動

#N 枚のプレートは 2^N - 1 回移動します

したがって、64 枚のプレートは 2^64 - 1 回移動する必要があります

3. 問題を解決します

再帰によってこの問題を解決し、正しい移動方法を取得できます

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");
}

この段落 コードでは、src はソース ピラー、help は補助ピラー、dest はターゲット ピラーです。

これは双方向の再帰です。

実行結果:

2^64 - 1 秒を年に換算すると、約 5849 4241 7355 年 (5849 億 4200 万年) 地球が存在してからわずか 45 億年、太陽系の寿命は数百億年と言われています年。実に5,849億4,200万年が経ち、太陽系や天の川銀河は言うに及ばず、少なくともバチカン塔や寺院などを含む地球上のすべての生命が絶滅して久しい。

関連予言

これが完成すると宇宙は瞬く間に滅亡するという予言がある。また、バラモンは今でも常にディスクを動かしていると信じている人もいます。

コンピューターが 64 枚のプレートを動かすのにどれくらい時間がかかりますか?

私のコンピューターのコア周波数は 2.90GHz で、これは 1 秒あたり 29 億回の演算に相当します。したがって、2^64 - 1 回移動するのに必要な時間は約 201 年です

以上がJavaを使用してハノイの塔問題を分析する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。