ハノイの塔非再帰版

Question

C言語ハノイの塔について
初心者です。
以下のプログラムを非再帰に直した場合どうなるのか教えて頂きたいです。

#include<stdio.h>

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);
if(no>1) move(no-1,6-x-y,y);
}

int main(){
int n;
printf("ハノイの塔¥n円盤の枚数:");
scanf("%d",&n);
move(n,1,3);
return 0;
}

Comments

[Zuishin]

https://teratail.com/questions/300164
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q12189577012

コードの入手先は必ず書きましょう。

[choya]

すみません。あまり規約を読んでいませんでした。以後気をつけます。

Answer 1

Wikipedia「ハノイの塔」によりますと

• いちばん小さい円盤とそれ以外の円盤を交互に動かす。
• いちばん小さい円盤は常にB→C→A→B(nが偶数の場合)またはC→B→A→C(nが奇数の場合)の順に動かす。
• いちばん小さな円盤以外の円盤を動かす場面では、動かせる方法は1通りしかない。

Answer 2

Wikipedia の「ハノイの塔」の2進数による解析 をコード化してみました。

#include <stdio.h>

void move(int no)
{
	for (int k = 1 << no, n = 1; n < k; n++) {
		int a = (n-1 & n) % 3 + 1, b = ((n-1 | n) + 1) % 3 + 1;
		if (!(no & 1)) a > 1 && (a = 5 - a), b > 1 && (b = 5 - b);
		int i = 0;
		while ((n>>i & 1) == 0) i++;
		printf("[%d] %d -> %d\n", i+1, a, b);
	}
}

int main()
{
	int n;
	printf("ハノイの塔\n円盤の枚数:");
	scanf("%d", &n);
	move(n);
	return 0;
}

もっと簡単に書けるかもしれません。

Comments

[angel_p_57]

分かり易さを採るならこれでしょうか。ctzは「2進数での末尾の0の数」で、gccなら __builtin_ctz() が使えます。

int ctz(int x) {
return __builtin_ctz(x);
}

void move(int no, int x,int y){
int atab[2][3] = {
{ x,y,6-x-y },
{ x,6-x-y,y }
};
for ( int i=1; i<(1<<no); i++ ) {
int t=ctz(i)+1;
int j=i>>t;
int k=(no-t)%2;
printf("[%d] %d -> %d\n",t,atab[k][j%3],atab[k][(j+1)%3]);
}
}

Answer 3

「プログラムを非再帰に直した場合」の目的がよく分からないのですが、一般に再帰で書かれたものを非再帰に直すのは単純ではないです。
※例外は「末尾再帰」、階乗 n!=n×(n-1)! のような再帰であればループに置き換えることができる。

コンパイラがこの手のプログラムから機械語を生成して、それで意図通り動くのは、スタックのようなデータ構造を絡めた処理に置き換えているからで、新しく関数を呼ぶ時は、一旦今の計算内容を脇に置いておいて ( スタックに積んで )、呼んだ関数が終わったら続きから再開する、そんな感じのことを自前でやれば見た目は非再帰になります。…それに意味があるのかどうか分かりませんが。

もし「『ハノイの塔』に限った非再帰版」というお話であれば、その出力結果を良く見て規則性をなぞれば、単なる 2^n-1 回のループになることが分かります。
例えば円盤 1 を動かすのはループの奇数回目に限る、とか。円盤 2 を動かすのはループの偶数回目 ( かつ4の倍数回目じゃない ) とか。円盤 3 を動かすのはループの4の倍数回目 ( かつ8の倍数回目じゃない ) とか。