はじめに
いつもお世話になっています。
先日同様の件名について質問をさせて頂きました。
「素数の足し算で」の解き方を教えてください
https://teratail.com/questions/77349
木やグラフをしらみつぶしに探索する深さ優先探索(再帰あり)のアルゴリズムを教えて頂きました。
教えていただいたので実際に実装して確認してみました。
幅優先探索は特に問題なく実装出来ました。
しかし深さ優先探索(再帰なしでスタックを使用する方法)が上手くいきません。
ソースコードを添付しますので、指摘をお願いいたします。
C
1/* 2 ある範囲内の素数の足し算で、ある数Xを表現するパターンがいくつ存在するかを表示するプログラム(ある範囲は100以下とする) 3 4 2-19 までの素数で38を表現するパターンは以下の6通りなので答えは6 5 [2+17+19] 6 [3+7+11+17] 7 [3+5+13+17] 8 [3+5+11+19] 9 [2+5+7+11+13] 10 [2+3+5+11+17] 11*/ 12#include <stdio.h> 13 14#define TRUE (1) /* 成功 */ 15#define FASLE (0) /* 失敗 */ 16 17#define STACK_SIZE (100) /* スタックの数 */ 18 19 int _stack_data[STACK_SIZE]; /* スタック格納バッファ */ 20 int _stack_num; 21 22 int push(int push_data) { 23 if (_stack_num < STACK_SIZE) { 24 _stack_data[_stack_num] = push_data; 25 _stack_num++; /* next elements */ 26 return TRUE; 27 } 28 else { 29 return FASLE; 30 } 31 } 32 33 int pop(int *pop_data) { 34 if (0 < _stack_num) { 35 _stack_num--; 36 *pop_data = _stack_data[_stack_num]; 37 return TRUE; 38 } 39 else { 40 return FASLE; 41 } 42 } 43 44#define N (25) /* elements number */ 45 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 までの素数たち */ 46 47 int main() { 48 int i, match_cnt; 49 int imin, imax, ival, sum; 50 51 // "6 19 38" を入力 52 printf("input [MIN] [MAX] [TTL]\n"); 53 scanf_s("%d%d%d", &imin, &imax, &ival); 54 printf("input no %d %d %d\n", imin, imax, ival); 55 56 for (i = 0; imin > prime[i]; i++); 57 push(prime[i++]); // 加算した値 58 push(0); // 加算しない値 59 match_cnt = 0; 60 61 while (_stack_num ) { // スタックが空っぽになるか 62 pop(&sum); 63 64 if (sum == ival || (sum + prime[i]) == ival) { 65 match_cnt++; // 一致した値 66 continue; 67 } 68 if (sum > ival || (sum + prime[i]) > ival) { 69 continue; 70 } 71 if (prime[i] > imax) { 72 continue; 73 } 74 75 push(sum + prime[i++]); // 加算した値 76 push(sum); // 加算しない値 77 } 78 printf("match=%d\n", match_cnt); // 6が出力されて欲しい 79 80 return 0; 81 }
そもそもの疑問ですが、貴殿はこの問題をなぜ解決したいのですか?学校などの課題解決のため?プログラム学習のため?などなどあると思いますが、
回答1件
あなたの回答
tips
プレビュー