ハノイの塔についてはわかりません。再帰を使ってこれに関するプログラムを書きたいです。
3687 次
6 に答える
7
別の宿題。先生のAを私に渡してください;）
出典： http： //www.soc.napier.ac.uk/~andrew/hanoi/rechelp.html
ボーナス：ステップバイステップのYouTubeビデオ。
ハノイの塔について少し
これの分析と（発明された）神話と4つのペグバージョンの議論はrec.puzzlesFAQで誘導/ハノイを探して見つけることができます。
ハノイの塔の問題には、再帰的な解決策があります。
再帰的ソリューションの作成
このような問題を解決するには、「 n-1のケースを解決した場合、nのケースを解決できますか？」と自問してください。
この質問に対する答えが肯定的である場合は、n-1のケースが解決されたというとんでもない仮定の下で続行します。奇妙なことに、これは、特殊なケースとして扱うことができるいくつかの基本ケース（多くの場合、 nが0または1の場合）がある限り、機能します。
n個のリングを極Aから極Cに移動するにはどうすればよいですか？
n-1リングをある極から別の極に移動する方法を知っている場合は、n-1リングを予備の極に移動するだけです。現在、ソース極に残っているリングは1つだけです。それを目的の極に移動し、残りを積み重ねます。それらのスペアポールからデスティネーションポールへ。
たとえば、nが4の場合...
最初に3つを予備のポールに移動します（後でこれを行う方法が心配です）。
次に、1つのリングをソースポールからデスティネーションポールに移動します。
次に、3つのリングをスペアポールからデスティネーションポールに移動します
（これも後で行う方法について心配することができます）。
終了しました！
もっと簡潔に...
Bをスペアとして使用してn個のリングをAからCに移動するには：
- nが1の
場合
- 早くやれよ、
- そうでなければ...
- Cをスペアとして使用して、 n-1個のリングをAからBに移動します
- 1つのリングをAからCに移動します
- Aをスペアとして使用してn-1リングをBからCに移動します
ほとんどの再帰的ソリューションと同様に、いくつかの基本ケースを特別に処理する必要があります。ここでは、移動するリングが1つしかない基本ケースが発生します。
Cでそれを行う方法
/* Tower of Hanoi - the answer */
/* How to move four rings from pin 1 to pin 3 using pin 2 as spare */
#include <stdio.h>
void move(n, A, C, B)
/* number to move, source pole, destination pole and
spare pole respectively */
int n, A, B, C; {
if (n == 1) {
printf("Move from %d to %d.\n", A, C);
} else {
move(n - 1, A, B, C);
move(1, A, C, B);
move(n - 1, B, C, A);
}
}
main() {
move(4, 1, 3, 2);
}
于 2009-07-18T11:06:23.043 に答える
2
Lispでのコンパクトな実装は次のとおりです：http ：//www.kernelthread.com/projects/hanoi/html/gcl.html 。確かに再帰的ですが、それが正しいかどうかは確認しませんでした。
于 2009-07-18T11:08:08.517 に答える
1
#!/usr/bin/env python
discs = 3
T = [range(discs, 0, -1), [], []]
def show_towers():
"""Render a picture of the current state of the towers"""
def render_disc(t, y):
return ("-"*(t[y]*2-1) if y < len(t) else "|").center(discs*2)
for y in range(discs):
print " ".join(render_disc(t, discs-y-1) for t in T)
print "="*(discs*6+3)
def move(n, source, destination):
"""Recursively move n discs from source to destination"""
while n > 0:
temp = 3 - source - destination
move(n-1, source, temp)
T[destination].append(T[source].pop())
show_towers()
n, source = n-1, temp # Simulate tail recursion
show_towers()
move(discs, 0, 2)
ディスクの出力=3
- | |
--- | |
----- | |
=====================
| | |
--- | |
----- | -
=====================
| | |
| | |
----- --- -
=====================
| | |
| - |
----- --- |
=====================
| | |
| - |
| --- -----
=====================
| | |
| | |
- --- -----
=====================
| | |
| | ---
- | -----
=====================
| | -
| | ---
| | -----
=====================
于 2012-10-06T09:07:46.420 に答える
0
コンピュータプログラムの構造と解釈ビデオ講義には、この問題を解決するための役立つヒントと、その他の豊富な知識が含まれています。
于 2009-07-18T11:09:56.360 に答える
0
再帰的アルゴリズムの説明については、ウィキペディアのハノイの塔の記事を参照してください。
これは次のようになります。
#include <iostream> // ostream
#include <algorithm> // for_each
#include <deque> // I can iterate over towers & print state,<stack> works as well
#include <boost/array.hpp> // just a wrapper for array
#include <boost/lambda/lambda.hpp> // easy one line for_each iterating
using namespace std;
typedef std::deque< int > tower_t; // stack works as well, deque for printing
typedef boost::array< tower_t ,3 > towers_t; // 3 towers
enum peg { A = 0, B = 1, C = 2 };
印刷：
ostream & show(ostream & os, const tower_t & t)
{
os << "[";
for_each (t.begin(), t.end(), os << boost::lambda::_1 );
return os << "]";
}
ostream & show(ostream & os, const towers_t & t)
{
show(os, t[0]); show(os, t[1]); show(os, t[2]);
return os;
}
解決する：
void move(peg from, peg to, towers_t & t)
{
// show move and state before move
cout << "mv: " << t[from].back() << " " << from << " --> " << to << "\t\t";
show(cout, t); cout << " --> ";
// the actual move: move top peg `from` stick `to` stick (and `pop` old top)
t[to].push_back(t[from].back());
t[from].pop_back();
// show state after move
show(cout, t); cout << endl;
}
// move n discs from A to B via C
void move(int n, peg from, peg to, peg via, towers_t & t)
{
if (n == 1) { move(from, to, t); return; }
move(n-1, from, via, to, t);
move(from, to, t);
move(n-1, via, to, from, t);
return;
}
使用法、4つのペグで塔を解きます：
int main()
{
towers_t ttt;
tower_t & first_tower(ttt[0]);
first_tower.push_back(4);
first_tower.push_back(3);
first_tower.push_back(2);
first_tower.push_back(1);
move(first_tower.size(), A, C, B, ttt); // move n from A to C via B
}
最初のタワーに4つのペグがある3つのタワーを解決しました。最大のペグの数が最も多く、最小のペグは1です。
出力（mv: PegX FromTower ---> ToTower）に続いて、移動の前後の状態が表示されます。各タワーは左から右に、下から上にペグを示しています。上部は右側にあります。
mv: 1 0 --> 1 [4321][][] --> [432][1][]
mv: 2 0 --> 2 [432][1][] --> [43][1][2]
mv: 1 1 --> 2 [43][1][2] --> [43][][21]
mv: 3 0 --> 1 [43][][21] --> [4][3][21]
mv: 1 2 --> 0 [4][3][21] --> [41][3][2]
mv: 2 2 --> 1 [41][3][2] --> [41][32][]
mv: 1 0 --> 1 [41][32][] --> [4][321][]
mv: 4 0 --> 2 [4][321][] --> [][321][4]
mv: 1 1 --> 2 [][321][4] --> [][32][41]
mv: 2 1 --> 0 [][32][41] --> [2][3][41]
mv: 1 2 --> 0 [2][3][41] --> [21][3][4]
mv: 3 1 --> 2 [21][3][4] --> [21][][43]
mv: 1 0 --> 1 [21][][43] --> [2][1][43]
mv: 2 0 --> 2 [2][1][43] --> [][1][432]
mv: 1 1 --> 2 [][1][432] --> [][][4321]
于 2012-01-31T06:06:56.213 に答える