再帰処理の例と言えば、ハノイの塔ですね。 ハノイの塔というゲームは、ウィキペディアによれば、下記のルールで移動しますね。 ＋3本の杭(a,b,c)と、中央に穴の開いた大きさの異なる複数の円盤から構成される。 ＋最初はすべての円盤が左端の杭(a)に小さいものが上になるように順に積み重ねられている。 円盤を一回に一枚ずつどれかの杭に移動させることができるが、 ＋小さな円盤の上に大きな円盤を乗せることはできない。 ＋以上のルールに従ってすべての円盤を右端の杭(c)に移動させられれば完成。言い換えれば、複数の円盤を杭(a)から、杭(b)を利用して、杭(c)にルールに従って移動するのですね。 c++プログラムコードは以下の通りですが、すごく簡単です。
#include <iostream>
using namespace std;
void hanio(int n, char a, char b, char c) {
if (n > 1) {
hanio(n - 1, a, c, b);
}
cout << a << " -> " << b << endl;
if (n > 1) {
hanio(n - 1, b, a, c);
}
}
int main()
{
hanio(4, 'a', 'b', 'c');
return 0;
}
円盤移動の過程は以下の通りです。
a -> c a -> b b -> a a -> c c -> b c -> a a -> c a -> b b -> a b -> c c -> b b -> a a -> c a -> b b -> aヤバいですね、でも結果としての円盤移動の過程は読みづらいですね。 c++プログラムコードは以下の通りです。
#include <iostream>
#include <vector>
#include <string>
#pragma warning(disable:4996)
using namespace std;
#define NN 4
vector<string> saved_move;
void hanio_save(int n, char a, char b, char c) {
if (n > 1) {
hanio_save(n - 1, a, c, b);
}
char mv[20]; sprintf(mv, "%c->%c", a, c);
saved_move.push_back(string(mv));
if (n > 1) {
hanio_save(n - 1, b, a, c);
}
}
vector<string> a;
vector<string> b;
vector<string> c;
int main()
{
hanio_save(NN, 'a', 'b', 'c');
vector<string> a = { "4444444", " 33333 ", " 222 ", " 1 " };
vector<string> b;
vector<string> c;
// プリントアウト
cout << "移動前" << endl;
for (int l = NN; l > 0; l--) {
if (a.size() < l) cout << string(NN * 2-1, ' '); else cout << a[l - 1]; cout << " ";
if (b.size() < l) cout << string(NN * 2-1, ' '); else cout << b[l - 1]; cout << " ";
if (c.size() < l) cout << string(NN * 2-1, ' '); else cout << c[l - 1]; cout << endl;
}
cout << "-----------------------" << endl;
cout << " (a) (b) (c) " << endl << endl;
for (int n = 0; n < saved_move.size(); n++) {
// 移動
string strFrom;
if (saved_move[n][0] == 'a') { strFrom = a.back(); a.pop_back(); }
if (saved_move[n][0] == 'b') { strFrom = b.back(); b.pop_back(); }
if (saved_move[n][0] == 'c') { strFrom = c.back(); c.pop_back(); }
if (saved_move[n][3] == 'a') { a.push_back(strFrom); }
if (saved_move[n][3] == 'b') { b.push_back(strFrom); }
if (saved_move[n][3] == 'c') { c.push_back(strFrom); }
// プリントアウト
cout << saved_move[n] << endl;
for (int l = NN; l > 0; l--) {
if (a.size() < l) cout << string(NN * 2-1, ' '); else cout << a[l - 1]; cout << " ";
if (b.size() < l) cout << string(NN * 2-1, ' '); else cout << b[l - 1]; cout << " ";
if (c.size() < l) cout << string(NN * 2-1, ' '); else cout << c[l - 1]; cout << endl;
}
cout << "-----------------------" << endl;
cout << " (a) (b) (c) " << endl << endl;
}
return 0;
}
プリントアウトの処理は即座にモニターに出さないで、①移動の動作(a->c)をsaved_moveという配列に保存し、②円盤を
1 222 33333 4444444のように表現します。円盤を保管するために、vector
移動前
1
222
33333
4444444
-----------------------
(a) (b) (c)
a->b
222
33333
4444444 1
-----------------------
(a) (b) (c)
a->c
33333
4444444 1 222
-----------------------
(a) (b) (c)
b->c
33333 1
4444444 222
-----------------------
(a) (b) (c)
a->b
1
4444444 33333 222
-----------------------
(a) (b) (c)
c->a
1
4444444 33333 222
-----------------------
(a) (b) (c)
c->b
1 222
4444444 33333
-----------------------
(a) (b) (c)
a->b
1
222
4444444 33333
-----------------------
(a) (b) (c)
a->c
1
222
33333 4444444
-----------------------
(a) (b) (c)
b->c
222 1
33333 4444444
-----------------------
(a) (b) (c)
b->a
1
222 33333 4444444
-----------------------
(a) (b) (c)
c->a
1
222 33333 4444444
-----------------------
(a) (b) (c)
b->c
1 33333
222 4444444
-----------------------
(a) (b) (c)
a->b
33333
222 1 4444444
-----------------------
(a) (b) (c)
a->c
222
33333
1 4444444
-----------------------
(a) (b) (c)
b->c
1
222
33333
4444444
-----------------------
(a) (b) (c)
以上です。
|