ハノイの塔 途中経過の記載

Question

ハノイの塔の問題についてです。１～１０までの数字でそれぞれ出力されるプログラムを作ります。
５のときの例です。
01234 ..... .....
.1234 ..... ....0
..234 ....1 ....0
..234 ...01 .....
...34 ...01 ....2
..034 ....1 ....2
..034 ..... ...12
...34 ..... ..012
一部ですが，表示が上記のようになるようにしたいです。
２の時ですが
01 .. ..
.1 0. ..
.. 0. .1
.. .. 01
と表示されてしまいます。
01 .. ..
.1 .0 ..
.. .0 .1
.. .. 01
これが正しい結果です。
途中過程の出力が上手くいきません。何か回答いただけると嬉しいです。コードは貼っています。よろしくお願いします。

コード#include <stdio.h>

char col[3][10];

void Hanoi(int n, int a, int b, int c){
    if(n>1){
        Hanoi(n-1, a, c, b);
    }
    int f;
    f=col[a][n-1];
    int d;
    for(d=0;d<n;d++){
        col[a][d]='.';
    }
    int e;
    for(e=0;e<n;e++){
        col[c][e]='.';
    }
    col[c][n-1]=f;
    printf("%s %s %s\n", col[0], col[1], col[2]);
    if(n>1){
        Hanoi(n-1, b, a, c);
    }
}

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

Comments

[Bull]

このプログラムでは円盤の移動ができないような気がします。
移動するのは一番上の円盤です。そのためには、一番上の円盤の位置を別途記録しておくか、その都度検索する必要があります。
移動するときに、検索しているようにはみえないのですが。

[YuhiKUROIWA]

ご指摘ありがとうございます。
コードを上記のように変更した結果、一番上の円盤が動くようになったのですが出力が上手くいきませんでした。どうすればよいか意見いただけると嬉しいです。

[Bull]

多分このままのやり方ではダメです。
えっと、どうしましょうか？
そのものズバリの回答が欲しければ、つい最近同じような質問がありました。
私も回答していますが、私の方法はちょっと違うので、余り参考にならないと思います。
別の回答者の方 (shiracamus さん) の回答が参考になるのでは無いかと思います。

もし、自分で考えたいというのであれば、ヒントだけにします。
現状では、円盤の位置が変わってないです（中に浮いている）。
'.' は円盤がない状態ですので、それを検索していけば、一番上の円盤が見付かります。また、移動する先も '.' を検索していくことで、移動すべき位置がわかります。

[YuhiKUROIWA]

自分で考えてみたいのですが、全く何をすればいいかわかりません。もう少しヒントをいただけると嬉しいです。

[kazuma-s]

> １～１０までの数字でそれぞれ出力されるプログラムを作ります。
0～9 ではないのですか？

Answer 1

ヒントだけと言うことなので、コードは最小限にします。
col[a][]からcol[c][]に円盤を移動するというのは間違っていないです。すでにコメントしていますが、col[][]には円盤が上から記録されていますが、円盤が無いところは '.' です。
col[a][]の一番上の円盤を探して、col[c][]の一番上に移動します。

最初に移動すべき円盤を探します。

for (d = 0; d < 10; d++) {
	if (col[a][d] != '.') {
		//一番上の円盤が見付かった
		break;
	}
}

次の移動先の位置を決めます。

for (e = 0; d < 10; e++) {
	if (col[c][e + 1] != '.') {		//e+1 で一番上の円盤を見つける
		//col[c][e] に移動する
		break;
	}
}

こんな感じでできるかと思います。

Comments

[YuhiKUROIWA]

詳しいヒントありがとうございます。
あとは自分で考えられそうなのでやってみます。

Answer 2

文字列の最後には '\0' が必要なので
char col[3][10]; では円盤を 9枚までしか置けません。
円盤の最上段の位置を憶えておくと、関数 Hanoi の中でループは不要になります。

#include <stdio.h>

char col[3][11], top[3];

void Hanoi(int n, int a, int b, int c)
{
    if (n > 1) Hanoi(n-1, a, c, b);
	col[c][--top[c]] = col[a][top[a]];
	col[a][top[a]++] = '.';
	printf("%s %s %s\n", col[0], col[1], col[2]);
    if (n > 1) Hanoi(n-1, b, a, c);
}

int main(void)
{
    int n;
    if (scanf("%d", &n) != 1 || n < 1 || n > 10) return 1;
    for (int i = 0; i < n; i++)
		col[0][i] = '0' + i, col[1][i] = col[2][i] = '.';
	top[1] = top[2] = n;
	printf("%s %s %s\n", col[0], col[1], col[2]);
    Hanoi(n, 0, 1, 2);
    return 0;
}

Comments

[YuhiKUROIWA]

なるほど、コードまで本当にありがとうございます。理解したうえでまた自分でも考えてみたいと思います。

Answer 3

単純に 1の場合を考えるとどうなるでしょうか。

col[c][e]=col[a][d]; その前の for() で、 d, e は、 n になってますが、よいですか? 多分、どちらも n-1。
でも、col[a][n-1]は、直前の for()で更新されてるので、そのまま、使えません。 for() の前に、一旦、保存すべきでしょう。
また、col[c][e+1]='.';も e+1は最後に nとなるので、適切でないですね。

なんて考えると以下のようになりました。(変数の宣言、その他省略)

    f = col[a][n-1];
    for(d=0;d<n;d++)	col[a][d]='.';
    for(e=0;e<n;e++)	col[c][e]='.';
    col[c][n-1]=f;

深く考えてなく、申し訳ないですが、、動くみたいです。

Comments

[YuhiKUROIWA]

ありがとうございます。
1のとき上手くいきました。

Answer 4

    int d;
    for(d=0;d<n;d++){
        col[a][d]='.';
    }
    /* 中略 */
    col[c][e]=col[a][d];

このような形なので、下の行でdはnになっています。おそらく、意図しないところを指しているのではないかと思います。

Comments

[YuhiKUROIWA]

ご意見ありがとうございます。
上記の様にコードを修正しました。出力が上手くいかなかったのですが、どこがどううまくいっていないのか具体的に教えていただけると助かります。よろしくお願いします。