ハノイの塔をC#で解く（再帰アルゴリズム）

5713 ワード
再帰 C# ハノイの塔 C# テキストリンク

ハノイの塔

ハノイの塔 - Wikipedia より

以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。

出典：André Karwath aka Aka - 投稿者自身による作品, CC 表示-継承 2.5, リンクによる

  • 3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
  • 最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
  • 円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。

n枚の円盤すべてを移動させるには最低 2n − 1 回の手数がかかる。（奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、216–217頁。ISBN 4-87408-414-1。）

アルゴリズム

GOAL: move n disks from A to C

move n-1 disks from A to B -> 再帰
move disk n from A to C
move n-1 disks from B to C -> 再帰

ソースコード

GitHubにも同じソースコードあり

Hanoi.cs
using System;

class Hanoi {
  public void Move(int n, char from, char to, char other) {
    if(n >= 1) {
      Move(n - 1, from, other, to);
      Console.WriteLine("move disk {0} from {1} to {2}.", n, from, to);
      Move(n - 1, other, to, from);
    }
  }
}

class HanoiMain {
  public static void Main(string[] args) {
    Hanoi hanoi = new Hanoi();

    Console.Write("How many disks? ");
    int n = int.Parse(Console.ReadLine());

    // n枚のdiskをAからCへ移す
    hanoi.Move(n, 'A', 'C', 'B');
  }
}

実行例（n=3）

こちらから実行可（入力は半角数字）

How many disks? -> 3

move disk 1 from A to C.
move disk 2 from A to B.
move disk 1 from C to B.
move disk 3 from A to C.
move disk 1 from B to A.
move disk 2 from B to C.
move disk 1 from A to C.