[BOJ]白峻11729号ハノイタワー移動順

リンク

https://www.acmicpc.net/problem/11729

質問する

3本の棒があり、1本目の棒にはn個の半径の異なる円板が積み上げられている.各円板は半径の大きい順に積み上げられている.現在、修道僧たちは以下の規則に従って、最初の棒から3番目の棒に移動します.
一度に1枚の原版を別の塔に移すしかない.
積み上げられたフィルムはいつも上のほうが下のより小さい.
プログラムを作成し、この操作を実行するために必要な移動順序を出力します.ただし、移動回数を最小限に抑える必要があります.
下図は5枚のバックグラウンドの例です.

入力

第1行は、第1の棒に積まれた円板の個数N(1≦N≦20)を与える.

しゅつりょく

1行目に移動した回数出力K.
2行目から実行プロセスの出力を開始します.2行目から、2つの整数A BをK行に分けて出力します.これは、A番タワーの一番上の円板をB番タワーの一番上に移動することを意味します.

に答える

 #include <iostream>

using namespace std;
int k; 


void func(int a, int b, int n) {
	if (n == 1) {
		cout << a << ' ' << b << '\n';
		return;
	}
	func(a, 6 - a - b , n - 1);
	cout << a << ' ' << b << '\n';
	func(6 - a - b, b, n - 1);
	
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> k;
	cout << (1 << k) - 1 << '\n';
	func(1, 3, k);
}

説明:

復帰する
n号円板のみに集中すると、何があっても円板をすべて柱1から柱3に移動したい場合は、n号円板を柱3に移動します.
1番からn-1番の円板を全部譲って、柱2まで行きます.彼らのいずれかが柱3に行くと、小さな円板には円板のルールを大きくすることができないので、n番の円板は柱3に移動できません.

n-1の円板を柱1から柱2に移動します.

の後、n番の円板を柱3に移動します.

次いで、

は、n−1円板をカラム2からカラム3に移動する.

n-1個の円盤が任意の位置に移動可能であれば、n個の円盤も移動可能である->復帰する
1枚のフィルムの場合、フィルムを私のほしいところに移すことができます.
オリジナルがk個の場合に移動可能であれば、オリジナルがk+1個の場合にも移動可能である.
1.関数の定義void func(int a, int b , int n):n個の円板をa番柱からb番柱に移動する方法の関数を出力する
2. base condition
n=1時cout << a << ' ' << b << '\n;3.回帰式
n-1枚の円板を柱aから柱6-a-bに移動します.func(a, 6-a-b, n-1);->回数A回
n番の円板を柱aから柱bに移動します.cout << a << ' ' << b << '\n;->回数A+1回
n-1枚の円板を柱6-a-bから柱bに移動します.func(6-a-b, b, n-1);->回数2 A+1回->秒項が1であるため、この数列の一般項は2^k-1である.
🧷 (1<<k):「<<」はleft shiftと呼ばれるビット演算子で、1をビットとしてk格子を押す必要があるため、2^kになります.
source : ドック実戦アルゴリズム0 x 0 B鋼