ハノイの塔を実行するプログラム

Question

実現したいこと

• ハノイの塔を実行するプログラムをコーディングしたい。

前提

C言語でハノイの塔を実行するプログラムを書いています。
動作が目に見える形で出力されるインタラクティブなものを創っています。

発生している問題・エラーメッセージ

### start
0|6]5]4]3]2]1]
1|
2|
### move 0 to 1
0|6]5]4]3]2]
1|1]
2|
### verify: OK
### move 0 to 2
0|6]5]4]3]
1|1]
2|2]
### move 1 to 2
0|6]5]4]3]
1|
2|2]1]
### verify: OK
### verify: OK
### move 0 to 1
0|6]5]4]
1|3]
2|2]1]
### move 2 to 0
0|6]5]4]1]
1|3]
2|2]
### verify: FAILED
0|6]5]4]1]
1|3]
2|2]

該当のソースコード

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

#define N_TOWER 3

unsigned* tower[N_TOWER];
unsigned* top[N_TOWER];
unsigned n_input;
unsigned n_steps = 0;

void print_tower(unsigned i) {
    assert(0 <= i && i < N_TOWER);
    unsigned* p = tower[i];

    printf("%d|", i);
    while (p != top[i]) {
        printf("%d]", *p);
        p++;
    }
    printf("\n");
}

void print_towers() {
    int i;
    for (i = 0; i < N_TOWER; i++) {
        print_tower(i);
    }
}

void move(unsigned from, unsigned to) {
    printf("### move %d to %d\n", from, to);
    unsigned disk = *(--top[from]);
    *(top[to]++) = disk;
    n_steps++;
    print_towers();
}

int verify_towers(unsigned* t0, unsigned* t1, unsigned* t2) {
    int j;
    for (j = 0; j < n_input - 1; j++) { //最大の高さのインデックス=(n_input-1)
        if (t0[j] < t0[j + 1] || t1[j] < t1[j + 1] || t2[j] < t2[j + 1]) {
            return 0; //ルールを無視している
        }
    }
    return 1; 
}

void hanoi(unsigned n, unsigned cur_pos, unsigned dest_pos) { //current,destination
    assert(0 < n);
    assert(0 <= cur_pos && cur_pos < N_TOWER);
    assert(0 <= dest_pos && dest_pos < N_TOWER);

    if (n == 1) {
        move(cur_pos, dest_pos);
    }
    else {
        unsigned tmp_pos = 3 - cur_pos - dest_pos; //temporary、仮の保管場所
        hanoi(n - 1, cur_pos, tmp_pos);
        move(cur_pos, dest_pos);
        hanoi(n - 1, tmp_pos, dest_pos);
    }

    if (verify_towers(tower[0], tower[1], tower[2]) &&
        verify_towers(tower[0], tower[1], tower[2]) &&
        verify_towers(tower[0], tower[1], tower[2])) {
        puts("### verify: OK");
    }
    else {
        puts("### verify: FAILED");
        print_towers();
        exit(EXIT_FAILURE);
    }
}


int main(int argc, char** argv) {
    int i;

    assert(argc == 2);
    n_input = atoi(argv[1]);
    assert(n_input > 0);

    for (i = 0; i < N_TOWER; i++) {
        tower[i] = malloc(n_input * sizeof(unsigned));
        if (tower[i] == NULL) exit(EXIT_FAILURE);
        top[i] = tower[i];
    }
    for (i = 0; i < n_input; i++) {
        *top[0] = n_input - i;
        top[0]++;
    }

    puts("### start");
    print_towers();
    hanoi(n_input, 0, 2);
    printf("### %d steps to complete\n", n_steps);

    return 0;
}

試したこと

verify_towers関数を確認してみましたが、エラーとなる原因を見つけることができませんでした。

補足情報（FW/ツールのバージョンなど）

Linuxの端末

Comments

[YAmaGNZ]

C#とC言語は別の言語となりますので、C#のタグは外してください。

Answer 1

verify_towers関数を確認してみましたが、エラーとなる原因を見つけることができませんでした

「エラー」というのは，「単に "FAILED" という結果になる」という意味でしょうか．
（プログラミング関係の文脈で「エラー」というと，普通はコンパイルエラーとかランタイムエラーを指すと思うので，この状況を示す言葉として相応しくないと思う）

で，「とりあえずデバッグすればわかるんじゃないの？」という話だと見えますが，
コードをぱっと見した限り，verify_towers 関数内で top を用いていないのはロジックとして変なのではないかと見えます．
（あと，この関数を無意味に３連続で呼んでいる点もどうかと思う）

verify_towers が top を用いて有効な範囲のみをチェックすべきなのか，
それとも move の側で現状の verify_towers の処理と辻褄が合う形にデータをいじくるべきなのか，
どちらの形が想定されているのかはわかりませんが，いずれかの然るべき方向で修正すれば良いのではないでしょうか．

Comments

[yasutin]

回答ありがとうございます。
おっしゃるとおり、エラーではなく望まない結果を出力してしまうということでした🙇

確認すべき事項としては
・それぞれの塔にあるｊ番目の円盤がj+1番目の円盤よりも大きい
ということだけだと思うのですが、他に何かありますか？

また、この関数を再帰的に表したいのですが、引数は（int j, unsigned *t0, unsigned *t1, unsigned *t2）でできるでしょうか？

[fana]

せっかく

> 動作が目に見える形で出力

とかいうのをやってるんだから，
動作が怪しいときには「ディスクが積まれてない範囲まで全てを」表示してやれば良いのではあるまいか．

[fana]

回答で　変　だと言っているのは

> それぞれの塔にあるｊ番目の円盤がj+1番目の円盤よりも大きい

この j の値はいくつまで見ればいいんですかね？　っていう点．
その時点で円盤が存在する範囲だけをチェックすべきであろう．

[fana]

> この関数を再帰的に表したい

意味がわからない．
順繰りにループで見ていけばよいだけの処理を，あえてわざわざ再帰でやるとか言ってる？
そんなの再帰関数の実装抜きに引数だけについて尋ねられても「知らんがな」あるいは「やればできるんじゃね？」としか言えない．

それ以前に，現状のコードで既に　引数で渡すやつ　と　外部変数を直にさわるやつ　とがあって，そこをどう分けているのか？っていう基準も他者にはわからないわけで．
そしたら，「この引数でよいか？」とか聞かれても，「不足なやつは外部変数を直に触る」という可能性がある以上は，十分とか不足とか言えないのではあるまいか．

[fana]

どうしても再帰にしたいのだとしても，まずは現状の形でまともに動く形を目指してからトライするのが良かろうと思う．
で，再帰にする話に関して質問がしたくなった場合には，本件とは別の質問とすれば良いものと思う．

[yasutin]

丁寧にありがとうございます。

その時点で円盤が存在する範囲だけをチェックしたいですが、pythonのように配列の長さを取得することのできる関数がありません。どのようにすれば配列の長さを取得できるでしょうか？

[yasutin]

再帰に関しましては、再帰的に記述しろという指定があるのを忘れていました。
失礼しました。

[yasutin]

int verify_towers(int j, unsigned* t0, unsigned* t1, unsigned* t2) {
if(j >= n_input-1){
return 1;
}

if(j==0){
int size = n_input * 2;

t0 = (int*)malloc(size * sizeof(int));
t1 = (int*)malloc(size * sizeof(int));
t2 = (int*)malloc(size * sizeof(int));
//for(int i = 0; i < size; i++){
//t0[i+(n_input-1)]
}

if ((t0[j] >= t0[j + 1] && t1[j] >= t1[j + 1] && t2[j] >= t2[j + 1]) && (verify_towers(j+1, t0, t1, t2))) {
return 1; // ルールに従っている
}

else{
return 0;
}
}

これでどうでしょうか。。。

[yasutin]

fanaさん！！！できました！
Ｃ言語まったくの初心者の私に丁寧に教えてくださってありがとうございました。
なにかほかにあればご教授願います。

[fana]

> なにか

と言われても特段ないですが…
私なら
verify_towers （←全タワーに関するチェックをする）関数の実装としては
verify_tower （←タワー１本分だけのチェックをする）という関数でも用意してそれを３本のタワーについて呼ぶ形にでもするかなぁ，とか思ったりしますが，まぁどうでもいい話かと．

---

とりあえず本件が解決したならば適切に処置してください．
この回答が解決に役に立ったと思われるならばこれをベストアンサーとしても良いですが，
ご自身で行われた再帰化の側の比重が大きいようであれば自己解決の形を採ってください．