ハノイタワー

ハノイの塔
ハノイのタワー(Towers of Hanoi)は、3本の柱の間から円盤を移動させ、小さな円盤が上にあり、大きな円盤が下にあるようにする問題です.すべてのディスクのサイズは異なり、最初はすべてのディスクが規則的に最初の面柱に積み上げられていました.この状態で、すべての円盤を3本目の柱に移動する最小回数でよい.移動の回数は最小限で、各ディスクは1つしか移動できません.小さなディスクには大きなディスクはありません.
始点柱かいしゅう:円盤が最初に配置された柱えんばん
ターゲット柱:移動先の柱
ちゅうかん柱
Aは、円盤が1つのグループに移動するプロセス、すなわち1および2である.

Bは、1が1つのグループに移動するプロセスである.

以上の2つの過程から見ると、ハノの塔は一連の過程を経験した.

ハノイの塔は以下の3つの過程を通ります.

下部円盤を除くグループ(円盤[1]~円盤[no-1])を始柱から中間柱に結ぶ.出力

底部円盤noは、始点柱から目標柱に移動する.

底部円盤以外のグループ(円盤[1]~円盤[no~1])を中間柱から目標柱に移動します.

この問題を細分化し,細分化した小問題の解法と組み合わせて問題全体を解く方法をdivideandconquence(分割解決法)と呼ぶ.
ハノイタワーの実施計画を見てみましょう.
円盤の個数はno、始柱番号はx、目標柱番号はyである.
私はハノイのtopアルゴリズムをコードで作成して3つのプロセスを実施しただけです.

#include <stdio.h> 

/* 원반[1] ~ 원반[no]를 x기둥에서 y기둥으로 옮김*/
void move(int no, int x, int y) {
	if (no > 1) // 베이스 케이스(중단 조건)
		move(no - 1, x, 6 - x - y); // 그룹을 시작기둥에서 중간기둥으로 옮김
	printf("원반[%d]를 %d 기둥에서 %d 기둥으로 옮김\n", no, x, y); // 바닥 원반 no를 시작 기둥에서 목표기둥으로 옮겼음을 출력
	if (no > 1)  // 베이스 케이스(중단 조건)
		move(no - 1, 6 - x - y, y); // 그룹을 중간기둥에서 목표기둥으로 옮김
}

int main(void)
{
	int n;

	printf("하노이의 탑\n원반 개수 : ");
	scanf("%d", &n);
	move(n, 1, 3);
	return 0;
}

move関数のパラメータには、残りのディスク数と、xカラムからyカラムに移動する2つの変数が含まれます.
割り込み条件がディスク数が0の場合、出力されるたびにディスク番号と何本目の柱から何本目の柱に移動します.
コードは、中間カラムを6-x-yとして表します.柱番号は1、2、3であり、柱番号の和は6であり、始柱と目標柱以外の残りの柱が6-x-yであることを示す.そうすれば、どの柱からでも、目標柱からでも、結果は良くなります.