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のセクションで書いたように、再帰は理解がより難しいトピックの一つである。人によってはこの問題をみて、非常に簡単と思うかもしれない。他の人はこれと苦闘することになるだろう。しかしながら、いったん再帰を理解するというハードルを克服すると問題の実際のコーディングはかなり簡潔になる。
だから、自分に挑戦したいなら、ここで読むのを止めるとよい。少し難しいと感じるのなら、ヒントを読みなさい。
ヒント: 再帰の問題はすべて同様なのだが、この問題は各ステップごとを単純にすることで、問題自体を単純化できる。３つの円盤の問題を覚えているだろうか？ You first create a two-disc tower on peg 2, which allows you to move the bottommost disc on peg 1 to peg 3. Then you move the two-disc tower on top of peg 3.
It's the same with four discs. First create a three-disc tower on peg 2, then move the biggest disc over to peg 3 and move the three-disc tower to peg 3. How do you create the three-disc tower? Simple. We already know how to move a three-disc tower from peg 1 to peg 3. This time, you're just moving from peg 1 to peg 2, then when the biggest peg is in place, you're moving the tower from peg 2 to peg 3. In this whole procedure, we can act as though the big disc doesn't exist, since it's guaranteed to be bigger than the others and thus poses no problem. Just utilize the three-disc solution, switching the numbers around.
Good luck!
| previous | contents | next |
