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

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

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

## 2. 問題分析

簡単な質問から始めましょう

64 枚のプレートについて直接考えるのは難しいかもしれませんが、以下に示すように 1 枚のプレートから始めることができます:

1 つのプレート

A -> C

プレートが 1 つしかない場合は、柱 A のプレートを柱 C

に直接移動できます。

一度移動する必要がある

2 つのプレートがある場合は、次の方法でも実現できます:

A -> B A -> ;C B->C

3 回移動する必要があります

1. A ->B

##2. A -> C

3. B -> C

プレート 3 枚

プレートが 3 枚の場合、移動手順は次のようになります。 C

合計 7 回移動する必要があります

## 1. A -> C

##2. A -> B

# 3. C -> B

#4. A -> C

## 5. B -> A

6. B -> C

7. A -> C

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

板が4枚ある場合、この問題は実は非常に複雑です。

ルール導出

1 枚のプレート 1 回移動

2 枚のプレート 3 回移動

3 枚のプレート 7 回移動

......

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

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

3. 問題を解決します

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

#N 個のプレートがある場合、どのように移動するか?

全体的なアイデア

まず、列 C を使用して N - 1 枚のプレートを列 A から列 B に移動し、次に残りのプレートを列 A から列 C に移動し、さらに移動します。柱 B の N - 1 枚のプレートが柱 A の助けを借りて柱 C に移動され、すべての柱の移動が完了します (途中の具体的な移動プロセスについては今のところ説明しません) ##

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 はターゲット ピラーです。

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

実行結果:

これで、プレートの移動が正常に完了しました。

4. ブラフマンはブラフマーのタスクを完了できますか?

方法64 枚の皿を動かすのにどれくらい時間がかかりますか?

ここでは、バラモンは非常に賢く、何も考えずに正しい移動方法を直接知ることができると仮定します。皿を移動するのに 1 秒かかりますが、彼らは動き続けます

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 サイトの他の関連記事を参照してください。