「素数の足し算で」の解き方(スタックによる深さ優先探索)を教えてください

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 940

kuma_dansyaku

score 16

 はじめに

いつもお世話になっています。
先日同様の件名について質問をさせて頂きました。

「素数の足し算で」の解き方を教えてください
https://teratail.com/questions/77349

木やグラフをしらみつぶしに探索する深さ優先探索(再帰あり)のアルゴリズムを教えて頂きました。
教えていただいたので実際に実装して確認してみました。

幅優先探索は特に問題なく実装出来ました。
しかし深さ優先探索(再帰なしでスタックを使用する方法)が上手くいきません。

ソースコードを添付しますので、指摘をお願いいたします。

/*
    ある範囲内の素数の足し算で、ある数Xを表現するパターンがいくつ存在するかを表示するプログラム(ある範囲は100以下とする)

    2-19 までの素数で38を表現するパターンは以下の6通りなので答えは6
    [2+17+19]
    [3+7+11+17]
    [3+5+13+17]
    [3+5+11+19]
    [2+5+7+11+13]
    [2+3+5+11+17]
*/
#include <stdio.h>

#define TRUE  (1)   /* 成功 */
#define FASLE (0)   /* 失敗 */

#define STACK_SIZE (100)     /* スタックの数 */

    int _stack_data[STACK_SIZE];    /* スタック格納バッファ */
    int _stack_num;

    int push(int push_data) {
        if (_stack_num < STACK_SIZE) {
            _stack_data[_stack_num] = push_data;
            _stack_num++;   /* next elements */
            return TRUE;
        }
        else {
            return FASLE;
        }
    }

    int pop(int *pop_data) {
        if (0 < _stack_num) {
            _stack_num--;
            *pop_data = _stack_data[_stack_num];
            return TRUE;
        }
        else {
            return FASLE;
        }
    }

#define N (25)    /* elements number */
    int prime[N] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };  /* 1-100 までの素数たち */

    int main() {
        int i, match_cnt;
        int imin, imax, ival, sum;

        // "6 19 38" を入力
        printf("input [MIN] [MAX] [TTL]\n");
        scanf_s("%d%d%d", &imin, &imax, &ival);
        printf("input no %d %d %d\n", imin, imax, ival);

        for (i = 0; imin > prime[i]; i++);
        push(prime[i++]);    // 加算した値
        push(0);             // 加算しない値
        match_cnt = 0;

        while (_stack_num ) {    // スタックが空っぽになるか
            pop(&sum);

            if (sum == ival || (sum + prime[i]) == ival) {
                match_cnt++;   // 一致した値
                continue;
            }
            if (sum > ival || (sum + prime[i]) > ival) {
                continue;
            }
            if (prime[i] > imax) {
                continue;
            }

            push(sum + prime[i++]);   // 加算した値
            push(sum);             // 加算しない値
        }
        printf("match=%d\n", match_cnt);    // 6が出力されて欲しい

        return 0;
    }
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • t_obara

    2017/05/26 16:25

    そもそもの疑問ですが、貴殿はこの問題をなぜ解決したいのですか?学校などの課題解決のため?プログラム学習のため?などなどあると思いますが、

    キャンセル

回答 1

checkベストアンサー

+1

深さ優先探索は再帰を使うと分かりやすいですが、再帰を使わずにやりたいなら「あたかも再帰をしているかのように」スタックの使い方を工夫すればよいと思います。

wikipedia:深さ優先探索に再帰を使う例とスタックを使う例の考え方が疑似コードで示されています。疑似コードを参考に論理を把握し、それを参考に考えてみると訓練になると思います。

こうした問題は自分で考えることに価値があると思います。答えがでることそのものが目的の場合(例えば仕事とか)だと違うでしょうが、勉強が目的なら自分で考えるべきです。

ちなみに自分が実装した例を挙げてみます。残念ながらwikiの疑似コードによく対応しているようには見えないかも知れませんが、自分なりに再帰の代わりにスタックを使うとしたら・・・と考えたものです。

push, popにデバッグプリントの後が残ってますがあえて残してみました。つまり以下のコードは一発で動かせてません。動かなかったのでデバッグしたのです。自分が書いたコードが動かない場合、大抵のプログラマーはデバッグします。

#include <stdio.h>

#define N (sizeof(primes)/sizeof(primes[0]))

int primes[] = {
  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
};

int stack[N];
int sp = 0;

void push(int d) {
  stack[sp++] = d;
  //printf("push: %d sp=%d\n", d, sp);
}

int pop() {
  //printf("pop: %d sp=%d\n", stack[sp - 1], sp);
  return stack[--sp];
}

int isEmpty() {
  return sp == 0;
}

void printAnswer() {
  printf("[");
  for (int i = 0; i < sp; i++) {
    printf("%s%d", (i > 0) ? " " : "", primes[stack[i]]);
  }
  printf("]\n");
}

void solve(int d) {
  int rest = d;
  int candidateIndex = 0;
  int answerCount = 0;
  print("target = %d\n", d);
  do {
    if (rest == 0) {
      printAnswer();
      answerCount++;
    }
    if (rest > 0 && candidateIndex < N && primes[candidateIndex] <= rest) {
      push(candidateIndex);
      rest -= primes[candidateIndex];
      candidateIndex++;
    } else if (!isEmpty()) {
      candidateIndex = pop();
      rest += primes[candidateIndex];
      candidateIndex++;
    }
  } while (!isEmpty() || (candidateIndex < N && primes[candidateIndex] <= d));
  printf("number of answers = %d\n", answerCount);
}

int main() {
  solve(38);
  return 0;
}

==> 結果
target = 38
[2 3 5 11 17]
[2 5 7 11 13]
[2 5 31]
[2 7 29]
[2 13 23]
[2 17 19]
[3 5 7 23]
[3 5 11 19]
[3 5 13 17]
[3 7 11 17]
[7 31]
number of answers = 11

ちなみに、識別子をキャメルケースで書いてしまっていますがご容赦を。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/26 23:54

    回答ありがとうございます。
    もう少しデバッグに対する粘りが足りなかったかなと反省しています。
    頂いたソースコードはもう少し頑張ってみてから参考にさせていただきます。

    自分はスタックを使った実装の方が再帰を使うよりは分かりやすくて簡単だと思っていたのですが、頂いた内容から察すると、実は全くの逆でスタックで実装する方が物凄く分かりづらかったりするのでは?と自分の読み取りの甘さを感じています。

    キャンセル

  • 2017/05/27 07:31

    アルゴリズムに対する慣れにより違うかもですが・・・
    スタックだとバックトラック(一つ前の時点に状態を戻して次の探索を継続する制御)が少々「ややこしい」あるいは「トリッキー」に見えますが、再帰では単に関数からリターンするだけで済むため「制御論理が単純になりやすい」と思います。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.22%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる