Basic Pascal Tutorial/Chapter 4/Programming Assignment/ja

│ български (bg) │ English (en) │ français (fr) │ 日本語 (ja) │ 中文（中国大陆）‎ (zh_CN) │

4G - 練習問題：ハノイの塔 (著者: Tao Yue, 状態: 原文のまま変更なし)

古典的な再帰問題で、すべてのコンピュータ科学コースで教えられるのはハノイの塔である。この問題では３つの垂直な棒がある。最も左の棒にはピラミッド型の塔があり、それは一連のドーナッツ型の円盤からなっている。たとえば、4階建ての塔は次のように見える。

   |       |       |
   |       |       |
   *       |       |
  ***      |       |
 *****     |       |
*******    |       |

棒は左から右へ 1、2、3 と番号をつけられている。挑戦すべきことは塔を棒 1 から棒 3 へ移動させることである。その際に、大きい円盤はより小さい円盤の上に置いてはいけないし、１度に１つの円盤（棒の一番上の円盤）しか動かせない。

この問題は１枚や２枚の円盤では、たいしたことはないように思えるかもしれない。１枚の円盤では棒 1 から棒 3 へ円盤を動かすだけでよい。２枚の円盤では棒 1 から棒 2 へ頂上の円盤を動かし、それから棒 1 から棒 3 へ円盤を動かし、最後に棒 2 から小さい円盤を棒 3 に動かせばよい。

この問題は３つ以上の円盤になるとずっと難しくなる。３つの円盤では棒 1 から棒 3 に動かし、それから棒 1 から棒 2 に動かし、そして棒 3 から棒 2 に動かす。こうすると2階の塔が棒 2 に作られる。その後、最大の円盤を棒 1 から棒 3 に動かす。そうして大きな円盤の上に２階の塔を移す。すなわち、棒 2 から棒 1へ、棒 2 から棒 3 へ、棒 1 から棒 3 へ移す。

あなたの課題はどんな数の円盤に対してもハノイの塔が解けるように再帰手続きを用いた（これは必須条件である）プログラムを書くことである。最初にユーザーにもとの塔の高さを尋ねる。それからある棒から別な棒へ個々の円盤を動かすステップごとの指示を出力する。例えば、３つの円盤の問題なら、以下のような出力が出なくてはならない。

1 to 3
1 to 2
3 to 2
1 to 3
2 to 1
2 to 3
1 to 3

再帰recursionのセクションで書いたように、再帰は理解がより難しいトピックの一つである。人によってはこの問題をみて、非常に簡単と思うかもしれない。他の人はこれと苦闘することになるだろう。しかしながら、いったん再帰を理解するというハードルを克服すると問題の実際のコーディングはかなり簡潔になる。

だから、自分に挑戦したいなら、ここで読むのを止めるとよい。少し難しいと感じるのなら、ヒントを読みなさい。

---

ヒント: 再帰の問題はすべて同様なのだが、この問題は各ステップごとを単純にすることで、問題自体を単純化できる。３つの円盤の問題を覚えているだろうか？ 最初に棒 2 に２階の塔を作成した。それによって棒 1 の一番下の円盤を棒 3 に動かすことが可能になった。それから２階の塔を棒 3 の上に動かした。

それは４つの円盤でも同じである。最初に棒 2 の上に３階の塔を作り、棒 3 に最大の円盤を移動させる。そして、３階の塔を棒 3 に移動させる。どのように３つの円盤の塔を作成しただろうか？　単純なことだ。すでに３つの円盤の塔を棒 1 から棒 3 に移動させるやり方は知っている。今度は、棒 1 から棒 2 動かし、それから最大の円盤を決まった位置においてから、塔を棒 2 から棒 3 へ動かす。この手続きで、大きい円盤は存在していないかのように扱うことができる。なぜなら、それが他のものより大きいことは確実であり、従って問題にはならないからである。数字の配置を入れ替えて、３つの円盤の解法を利用するだけでよいのである。

Good luck!

previous

contents

next