ハノイの塔の経過の表示

Question

質問内容

典型的なハノイの塔で左端のモノを右端に移すのですが，その途中経過の表示のアイデアがでません．
例えば，円盤が五枚のとき，次のようにする必要があります．
0が一番小さい円盤です．
01234 ..... .....
.1234 ..... ....0
..234 ....1 ....0
..234 ...01 .....　　　　＊一部です

私の考えとしては配列を
box[3][n]
みたいなかんじで作って，ないところには-1，あるところには円盤の番号を入れようと思ったのですが，再帰の理解が甘いせいもあって全然書き方が分からなくて進まないのですが，この方法を実現するための工夫や，他のアイデアなどを教えてほしいです．
コードは以下のようなところで止まっています．

コード

#include<stdio.h>
#include<stdlib.h>
void hanoi(int N,int d);
int box[3][10];
int main(void){
    int N;
    scanf("%d",&N);
    hanoi(N,1);
    int i,j;
    for(i=0;i<3;i++){
        for(j=0;j<N;j++){
            if(i==0) box[i][j]=i;
            else box[i][j]=-1;
        }
    }

    return 0;
}

void hanoi(int N,int d){
    if(N==0) return;
    hanoi(N-,-d);

    int i.j;
    for(i=0;i<3;i++){
        for(j=0;j<N;j++){
            if()
        }
    }

    hanoi(N-1,-d);
}

Answer 1

以前作ったプログラムですが、同じように柱にある円盤を配列で管理しています。
0が円盤なしで、1が一番小さな円盤です。
プログラムとしては特段説明するほどのものでも無く、良くあるハノイの塔を再帰で解くアルゴリズムです。円盤を移動するごとに配列を更新して、表示しています。
表示はお好みに合わせてどうぞ。

工夫というほどのものでは無いですが、円盤の管理がし易いように、一番上に載っている円盤の位置を記憶する配列を用意しています。-1が円盤なし、0が円盤一枚です。

#include <stdio.h>
#include <stdlib.h>

#define N   10          //円盤の枚数（デフォルト）
#define M    3          //柱の本数（固定）
#define MAX 32          //円盤の上限

int peg[M][MAX];        //柱の状態
int top[M];             //柱の一番上

//柱の状態を表示
void disp(void)
{
	for (int i = 0; i < M; i++) {
		printf("%c:", 'A' + i);
		for (int j = 0; j < MAX ; j++) {
			if (peg[i][j] > 0)
				printf("%3d", peg[i][j]);
		}
		printf("\n");
	}
}

//円盤を移動
void move(int s, int d)
{
	int n = peg[s][top[s]];					//sの柱の一番上
	peg[s][top[s]] = 0;						//円盤を削除
	peg[d][top[d]+1] = n;					//dの柱に移動

	top[s]--;								//sの柱を一枚減らす
	top[d]++;								//dの柱を一枚増やす
}

//ハノイの塔を解く
void hanoi(int no, int x, int y)
{
	if (no < 1) return;

	hanoi(no - 1, x, 6 - x - y);

	move(x - 1, y - 1);						//円盤を移動
	printf("円盤[%d]を%d軸から%d軸へ移動\n", no, x, y);	
	disp();									//柱の状態を表示

	hanoi(no - 1, 6 - x - y, y);
}

int main(void)
{
	int n;

	printf("ハノイの塔\n円盤の枚数：");
	scanf("%d", &n);

	//柱の状態を初期化する
	for (int i = 0; i < M; i++)
		for (int j = 0; j < MAX; j++)
			peg[i][j] = 0;					//各柱には何もない
	for (int i = 0; i < n; i++)
		peg[0][i] = n - i;					//Aの柱に円盤をセット
	top[0] = n - 1;							//Aの柱の最上位
	top[1] = -1;							//Bの柱は円盤無し
	top[2] = -1;							//Cの柱は円盤無し

	disp();									//柱の状態を表示

	hanoi(n, 1, 3);							//ハノイの塔を解く
}

---

配列を一つで、円盤がどの柱にあるか管理する方法もあります。
この方がプログラムはシンプルになりますが、表示がちょっと面倒です。

#include    <stdio.h>

#define N 6											//円盤の枚数（デフォルト）
#define MAX 32

char disk[MAX];										//円盤を記録
 
//塔の状態を表示
void Disp(int n)
{
	if (n > 0) printf("%d回目\n", n);
	for (int p = 'A'; p < 'C' + 1; ++p) {			//柱の'A'から'C'まで
		printf("%c:", p);							//柱を表示
		for (int j = N; j >= 0; --j) {				//大きな円盤から表示
			if (disk[j] == p) {						//円盤がその柱にあれば
				printf("%2d", j + 1);				//円盤を表示
			}
		}
		printf("\n");
	}
	printf("//-----\n");
}

//ハノイの塔を解く
void Hanoi(int n, char X,char Y,char Z)
{
	static int k = 0;
	if (n > 0) {
		Hanoi(n - 1, X, Z, Y);
		disk[n - 1] = Z;							//移動先を記録
		Disp(++k);
		Hanoi(n - 1, Y, X, Z);
	}
}

int main(void)
{
	int n;

	printf("ハノイの塔\n円盤の枚数：");
	if (scanf("%d", &n) < 1) return 1;
	if (n < 1 && MAX < n) n = N;

	for (int i = 0; i < n; ++i) {
		disk[i] = 'A';								//'A'の柱に全ての円盤がある
	}
	Disp(0);										//初期状態を表示
	Hanoi(n, 'A', 'B', 'C');
}

Comments

[grape_ll]

ご丁寧に二つも教えてくださりありがとうございます．
参考にしつつ自分でも考えてみようと思います．

Answer 2

私なら、文字配列にして終端に '\0' を置いて "%s" で文字列出力しちゃいます。

char tower[3][10];  // '\0' で初期化される

(中略)

  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    tower[0][i] = '0' + i;
    tower[1][i] = '.';
    tower[2][i] = '.';
  }
  printf("%s %s %s\n", tower[0], tower[1], tower[2]);

動作プログラムを書いておきます。

#include <stdio.h>

char tower[3][10];

void hanoi(int n, int from, int buffer, int to) {
  if (n > 1) hanoi(n - 1, from, to, buffer);

  int f = 0; while (tower[from][f] == '.') f++;
  int t = 0; while (tower[to][t + 1] == '.') t++;
  tower[to][t] = tower[from][f];
  tower[from][f] = '.';
  printf("%s %s %s\n", tower[0], tower[1], tower[2]);

  if (n > 1) hanoi(n - 1, buffer, from, to);
}

int main(void) {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    tower[0][i] = '0' + i;
    tower[1][i] = '.';
    tower[2][i] = '.';
  }
  printf("%s %s %s\n", tower[0], tower[1], tower[2]);
  hanoi(N, 0, 1, 2);
  return 0;
}

Comments

[grape_ll]

実際のコードまで書いてくださりありがとうございます．
参考にして自分でも考えてみたいと思います．