[再帰]ハノイの塔のプログラム 図として表現したい

Question

#include    <stdio.h>
int k=0;
void Hanoi(int n,char *X,char *Y,char *Z){
    if(n>=2)
    Hanoi(n-1,X,Z,Y);
    k++;
    printf("Step %d;move %d from %s to %s \n",k,n,X,Z);
    if(n>=2)
    Hanoi(n-1,Y,X,Z);
}

int main(void){
    Hanoi(3,"A","B","C");
    return 0;
    }



```### このハノイの塔のプログラムから改良して以下のように図にしたいです。

//A: 3 2 1
//B:
//C:
//-----
//A: 3 2
//B:
//C: 1
//-----

### 補足情報

プログラミング初心者です。
よろしくお願いします。

Comments

[Zuishin]

Step 1 ;move 1 from A to C
Step 2 ;move 2 from A to B
Step 3 ;move 1 from B to A
Step 4 ;move 3 from A to C
Step 5 ;move 1 from C to B
Step 6 ;move 2 from C to A
Step 7 ;move 1 from A to C

実行すると上記のようになりましたが、間違っていませんか？
Step 3 で C にあるはずの 1 が B から移動しています。
そして 1 の下にある 3 が Step 4 で移動しています。

[riiiiii__ru]

#include <stdio.h>
void Hanoi(int n,char *X,char *Y,char *Z){
if(n>=2)
Hanoi(n-1,X,Z,Y);
printf("Step ;move %d from %s to %s \n",n,X,Z);
if(n>=2)
Hanoi(n-1,Y,X,Z);
}

int main(void){
Hanoi(3,"A","B","C");
return 0;
}

このプログラムなら正常に実行できますが、step数の出し方がわからないです。

[Zuishin]

ステップ数は Hanoi 関数が呼び出されるたびに 1 増えているだけです。

[Zuishin]

新しい方のコードも終了条件が無いので正常に実行できません。
実際にコンパイルして動かしていますか？

[riiiiii__ru]

#include <stdio.h>

int k;
void Hanoi(int n,char *X,char *Y,char *Z){
if(n>=2)
Hanoi(n-1,X,Z,Y);
printf("Step %d;move %d from %s to %s \n",k,n,X,Z);
if(n>=2)
Hanoi(n-1,Y,X,Z);
k++;
}

int main(void){
Hanoi(3,"A","B","C");
return 0;
}
実行するとこうなっています。どこを修正すればいいのでしょうか、、。
Step 0;move 1 from A to C
Step 1;move 2 from A to B
Step 1;move 1 from C to B
Step 3;move 3 from A to C
Step 3;move 1 from B to A
Step 4;move 2 from B to C
Step 4;move 1 from A to C

[Zuishin]

今度は動きましたが、ステップが違います。
初期化されていないので、まず int k; を int k = 0; に変えてください。それから k++; を printf の直前の行に持ってきてください。

[riiiiii__ru]

出来ました。
本当にありがとうございます。

[Zuishin]

質問を編集してコードを書き換えてください。その際は

```C
int main(void) {
...
...
```

のように、```C と ``` の間にコードを入れてください。` はバッククォートです。<code> ボタンを押すと出てきます。
このようにすると、＃include の前の / は要りませんし、インデントも正しく表示されます。

[riiiiii__ru]

これでよろしいでしょうか、、？

[Zuishin]

main の最後の } の位置がおかしいですが、あとは OK です。

Answer 1

きったねぇけど、動くっちゃ動く。

#include    <stdio.h>
#include    <string.h>

char disk[3][10];

void Hanoi(int n,char* X, char* Y, char* Z) {
    char tmp;
    if(n>=2)
        Hanoi(n-1,X,Z,Y);

    /* Xの円盤をZに移動する */
    tmp = X[strlen(X)-1];
    X[strlen(X)-1] = '\0';
    Z[strlen(Z)] = tmp;
    printf("//A:%s\n//B:%s\n//C:%s\n//----------\n", disk[0], disk[1], disk[2]);

    if(n>=2)
        Hanoi(n-1,Y,X,Z);
}

int main(void){
    strcpy(disk[0],"321");
    strcpy(disk[1],"");
    strcpy(disk[2],"");
    Hanoi(3,disk[0],disk[1],disk[2]);
    return 0;
}

Comments

[episteme]

念のため、main()のアタマでdisk[3][10]を全部'\0'で埋めたほうがいいかなー...

[riiiiii__ru]

分かりました。
わざわざご丁寧にありがとうございます。
参考にさせていただきます。

[rubato6809]

> 全部'\0'で埋めたほうがいいかな

現状のdisk配列はグローバル変数ですから、既にオール０に初期化されていて問題起こしません。
０クリアされない場合は、ディスクを移動する箇所に一行追加するのがインパクト少なくて済みそうです、もちろんstrlen()を４度も呼ぶのはどうかと思いますが。

tmp = X[strlen(X)-1];
X[strlen(X)-1] = '\0';
Z[strlen(Z)+1] = '\0'; // この行を追加
Z[strlen(Z)] = tmp;

[kazuma-s]

strlen の結果を憶えておけば、呼び出しは 2回で済みます。
int lenX = strlen(X)-1, lenZ = strlen(Z);
Z[lenZ] = X[lenX];
Z[lenZ+1] = X[lenX] = '\0';

[Zuishin]

釈迦に説法……

[rubato6809]

釈迦です。

この程度の処理であればstrlen()を何度呼んでも大した負荷ではないと思いますが、、、初心者は工夫できることをいろいろ試すと良いですよ。

例えば、（strlen()する代りに）disk[0]～disk[2]、それぞれの枚数を記録するというアイディアが考えられると思います。"321" ならスタート時点は3枚、0枚、0枚ですね。
質問者さんは、枚数をどこにどう持てば良いか、ディスクを移動するところをどう書けば良いか、考えてみると良いと思います。やり方はひとつではないので、急がなくて結構。

[episteme]

C++ならstd::stringで楽できるんだけどねー...
Z.push_back(X.back());
X.pop_back();
こんだけやし。

Answer 2

#include    <stdio.h>
#include    <string.h>

char a[3][10]; //多次元配列//

void Hanoi(int n,char* X, char* Y, char* Z) {
    char tmp;
    if(n>=2)
        Hanoi(n-1,X,Z,Y);

    tmp = X[strlen(X)-1];     // Xの円盤をZに移動 //
    X[strlen(X)-1] = '\0';   //Xについての文字数//
    Z[strlen(Z)+1] ='\0';
    Z[strlen(Z)] = tmp;       //Zについての文字数//
    printf("A:%s\nB:%s\nC:%s\n-----\n", a[0], a[1], a[2]);

    if(n>=2)
        Hanoi(n-1,Y,X,Z);
}

int main(void){
    strcpy(a[0],"321"); //文字列のコピー//
    strcpy(a[1],"");
    strcpy(a[2],"");
    Hanoi(3,a[0],a[1],a[2]);
    return 0;
}

文字列や単語の意味を理解しながら自分なりに変えてみました。

Comments

[Zuishin]

次のような状態だとします。

X = "21";
Z = "3";

文字列の最後には必ずそこで終わりということを示す終端文字 '\0' が入っています。
よって次のように表すことができます。(疑似コード)

X = '2' + '1' + '\0' + (不明な文字) + (不明な文字)...
Z = '3' + '\0' + (不明な文字) + (不明な文字)...

この時

tmp = X[strlen(X)-1]; // X の最後の文字を tmp に退避
// tmp == '1' になる

X[strlen(X)-1] = '\0'; // X の最後の文字を削除
// '1' のあった場所に '\0' を書き込むので、そこで文字列が終わる
// X は '2' + '\0' + '\0' + (不明な文字) + (不明な文字)... になる

Z[strlen(Z)+1] ='\0'; // Z の文字数を増やすのであらかじめ終端文字を置いておく
// Z は '3' + '\0' + '\0' + (不明な文字)... になる

Z[strlen(Z)] = tmp; // Z の最後に tmp を付け加える
// Z は '3' + '1' + '\0' + (不明な文字)... になる

[rubato6809]

実際に動きを描いてみるというのは良い発想です。
そこで釈迦から追加課題を授けましょう（笑）。
a[3][10] としたのは、ディスクを最大9枚まで重ねられるため、ですよね？
"321" 固定じゃつまらない。では "54321" にするなら、どうしますか？
プログラムを実行する時にディスクの枚数を指定するには、どうしますか？

strlen()する代りに、３ヵ所のディスクの枚数を記録しながら動かす件も、今は工夫し甲斐あると思うので考えてみてください。いずれも急がなくて結構。

[Zuishin]

なんとなく私が質問者だと思われているように感じるので、一応否定しておきます。

Answer 3

これ、分かりますか？

#include <stdio.h>

int k;
int a[3][32]; // A,B,C の 3個所。a[i][0] は円盤の枚数。残りの 1～31 は円盤の番号

void print(void)
{
	for (int i = 0; i < 3; i++) {
		printf("//%c:", 'A' + i);
		for (int j = 1; j <= a[i][0]; j++)
			printf(" %d", a[i][j]);
		putchar('\n');
	}
	printf("//---- [%d]\n", ++k);
}

void init(int n)
{
	k = 0;
	a[0][0] = n, a[1][0] = 0, a[2][0] = 0; // A は n枚、B, C は 0枚
	for (int i = 0; i < n; i++)
		a[0][i + 1] = n - i;  // A に円盤を n, ... 2, 1 と置く
	print();
}

void Hanoi(int n, int x, int y, int z)
{
	if (n > 1) Hanoi(n - 1, x, z, y);
	a[z][++a[z][0]] = a[x][a[x][0]--];
	print();
	if (n > 1) Hanoi(n - 1, y, x, z);
}

int main(void)
{
	int n = 3;
	init(n);
	Hanoi(n, 0, 1, 2);
	return 0;
}

Comments

[riiiiii__ru]

ご回答ありがとうございます。
説明されていることは何となく分かるのですが、for文の部分でエラーが出てしまって実装できないです、、。

[kazuma-s]

とても古い規格の Cコンパイラを使っていますね。int i, j; を先に書いて、for文の中に int を書かないように修正してください。

Answer 4

こんな感じでは如何でしょう.
初心者に見せられるコードとは言い難いですが...。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void print(char** t,int n,char **o){
  int i,j;
  for(j=0;j<3;j++){
    printf("%s:",o[j]);
    for(i=n-1;i>=0;i--) if(t[i]==o[j]) printf(" %d",i+1);
    printf("\n");
  }
  printf("-----\n");
}
void move(int r,char *x,char *y,char *z,char **t,int n,char **o){
  if(r>=2) move(r-1,x,z,y,t,n,o);
  t[r-1]=z; //r番をzに移動
  print(t,n,o);
  if(r>=2) move(r-1,y,x,z,t,n,o);
}
void hanoi(int n,char *x,char *y,char *z){
  int i;
  char *o[3]; o[0]=x; o[1]=y; o[2]=z; //表示用
  char **t=(char **)malloc(sizeof(char*)*n); //各円盤の位置
  for(i=0;i<n;i++) t[i]=x;
  print(t,n,o);
  move(n,x,y,z,t,n,o);
  free(t);
}
int main(void){
  hanoi(3,"A","B","C");
  return 0;
}

A: 3 2 1
B:
C:
-----
A: 3 2
B:
C: 1
-----
A: 3
B: 2
C: 1
-----
A: 3
B: 2 1
C:
-----
A:
B: 2 1
C: 3
-----
A: 1
B: 2
C: 3
-----
A: 1
B:
C: 3 2
-----
A:
B:
C: 3 2 1
-----

Comments

[riiiiii__ru]

ご回答ありがとうございます。
初心者の私には少し難しいです、、。
時間をかけて理解します。