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

Question

はじめに

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

「素数の足し算で」の解き方を教えてください
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;
	}

Comments

[t_obara]

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

Answer 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

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

Comments

[kuma_dansyaku]

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

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

[KSwordOfHaste]

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