C
1 * 配列arrayに特定の数値numberがいくつあるか数える再帰関数とテストプログラム 2---*/ 3 4#include <stdio.h> 5 6int count(int number, int *array, int length); 7 8int main(){ 9 int array[16] = {1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4}; // 数値を格納した配列 10 int number = 4; // サーチする数値 11 12 printf("配列に含まれる %d の数は %d です\n", number, count(number, array, 16)); 13 14 return(0); 15} 16 17/* 再帰関数 */ 18 int count(int number, int *array, int length){ 19 if(length == -1) return(0); // 終了条件 20 21 if(array[length] == number) 22 return(1 + count(number, array, length-1)); 23 else 24 return(count(number, array, length-1)); 25} 26 27 /*--- 28出力結果 29% ./9-3 30配列に含まれる 4 の数は 2 です 31% ./9-3 32配列に含まれる 2 の数は 1 です 33---*/
int
1 if(length == -1) return(0); // 終了条件 2 if(array[length] == number) 3 return(1 + count(number, array, length-1)); 4 else 5 return(count(number, array, length-1)); 6}
配列にいくつ指定した数字が入っているか求めるプログラムなのですが
上にあるプログラムから抜き出された文の流れがつかめなくて、どのような流れをしているかを教えてほしいです。
流れをつかめる方いましたら回答よろしくお願いします。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答6件
0
投稿2018/08/13 09:46
編集2018/08/13 09:54総合スコア2663
0
こんにちは。
再帰定義に慣れないうちは、終了条件に近い方からシミュレーションしてみるとよいです。
コメントにもあるように if(length == -1) return(0);
が終了条件です。
length | count(略, length)の値 |
---|---|
-1 | 0 |
0 | array[0]とnumberが一致なら1+count(略, -1) =1。不一致ならcount(略, -1) =0 |
1 | array[1]とnumberが一致なら1+count(略, 0) 。 不一致ならcount(略, 0) |
2 | array[2]とnumberが一致なら1+count(略, 1) 。 不一致ならcount(略, 1) |
以下略 |
つまり、count(略, length)
は、値が一致したらcount(略, length-1)
に1
を足したもの、そうでなければcount(略, length-1)
そのままを返却します。最後まで計算すると値が一致した回数だけ1
が足されますから、値が一致した数が返ってきます。
投稿2018/08/11 14:37
総合スコア23272
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
再帰処理です。数学の漸化式に似ています。
末尾を判定してカウントアップし、範囲を狭めて反復します。配列長がゼロになるまで繰り返します。
投稿2018/08/11 08:18
総合スコア4830
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
ベストアンサー
以前、よく似た再帰関数を解説したことがあり、BAを頂戴しました。まず一度、ざっと目を通していただきたい。
リターンの仕組み
これに倣うと count() の呼出しは、こんな風にネストします。
count(4, array, 16) … array[16] == 4 ? (←なんとバッファオーバーラン!!)
↓
count(4, array, 15) … array[15] == 4 ? YES
↓
count(4, array, 14) … array[14] == 4 ? NO
:(途中、省略)
count(4, array, 1) … array[1] == 4 ? NO
↓
count(4, array, 0) … array[0] == 4 ? NO
↓
count(4, array, -1) ... ここまで来て、終了条件により return 0; する
念の為:終了条件とは count() 関数の if (length == -1)
です。
さて、ここで return した値 0 は、どうなるか。いきなり count(4, array, 16) のリターン値になるのではなく、
- count(4, array, 0)が呼び出した count(4, array, -1) の値として返り、それはさらに
- count(4, array, 1)が呼び出した count(4, array, 0) の値として返り、それはさらに
- count(4, array, 2)が呼び出した count(4, array, 1) の値として(以下、省略)
という具合いに、関数呼出しを逆向きに・さかのぼるようにリターンしていきます。
この、リターンしながらさかのぼる過程で、count(4, array, 3) と count(4, array, 15) の時、array[length] == 4 なので +1 します。
こんな具合い。
count(4, array, 16) ・・・そのまま2をリターン(多分 array[16] != 4 )
↑
count(4, array, 15) ・・・array[15] == 4 なので +1 し、2 をリターン
↑
count(4, array, 14) ・・・そのまま1をリターン
:
count(4, array, 3) ・・・array[3] == 4 なので +1 し、1 をリターン
↑
count(4, array, 2) ・・・そのまま0をリターン
count(4, array, 1) ・・・そのまま0をリターン
count(4, array, 0) ・・・そのまま0をリターン
↑
count(4, array, -1) ・・・ここで 0 をリターンする
最終的に count(4, array, 16) は 2 を返す、という動作になります。
int count(int number, int array[], int length) 関数は、array[0]からarray[length]にある number の個数を返す関数です。それは、こう考えることもできます。
**「length までの範囲にある個数は、(length - 1)までの範囲にある個数に、length の位置にある個数(0または1)を足したものである」**と。これが漸化式の考え方であり、再帰関数を作る時の考え方でもあります。例えばこんな感じ
- count(4, array, 16) == count(4, array, 15) + array[16]が4に等しいか否か
提示されたcount()は、中にcount()呼出しが2箇所ありますが、一箇所にすることもできます。
C
1int count(int number, int array[], int length) 2{ 3 if (length == -1) return 0; // これ以上掘っても number は無い(終了条件) 4 5 // length - 1、即ちひとつ下までの個数を得るため、ここで再帰する 6 int result = count(number, array, length - 1); 7 8 // 自分の担当箇所を検査、+1するか否か 9 if (array[length] == number) 10 ++result; 11 return result; // length 位置までの結果を返す 12}
蛇足の感想1.バッファオーバーランするコードが「サンプルコード」とは、いかがなものか。
蛇足の感想2.そもそも、この程度の処理で再帰するのは、いかがなものか。これだけで18段もネストし、スタックを消費する...。再帰を学ぶのに階乗の例と大差なく、再帰の有り難みが感じられない。だってループで数えるほうが素直でしょう(Lispじゃあるまいし笑)。
C
1 int result = 0; 2 for (int i = 0; i < length; i++) { 3 if (array[i] == number) 4 ++result; 5 } 6 return result;
階乗の例を学んだら、次はハノイの塔かクイックソート辺りに進むのが良いのでは、と思います。こういう問題はループで書くのが大変面倒です。
投稿2018/08/12 09:25
編集2018/08/13 09:33総合スコア1380
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/08/13 00:18
2018/08/13 00:20
2018/08/13 00:37
2018/08/13 01:00 編集
2018/08/13 01:03
2018/08/13 01:08
退会済みユーザー
2018/08/13 07:51
2018/08/13 08:25
退会済みユーザー
2018/08/13 08:28
2018/08/13 08:45 編集
2018/08/13 08:54
退会済みユーザー
2018/08/13 08:55
2018/08/13 09:00
2018/08/13 09:03
退会済みユーザー
2018/08/13 09:07 編集
2018/08/13 09:12
2018/08/13 09:15
2018/08/13 09:34
退会済みユーザー
2018/08/13 09:40
2018/08/13 09:42
0
分からなかったら、途中経過を出力してみるとか。
count()関数の中です。
C
1 if(array[length] == number) { 2 //return(1 + count(number, array, length-1)); 3 int result = (1 + count(number, array, length-1)); 4 printf("true: result = %d, length = %d\n", result, length); 5 return result; 6 } else { 7 //return(count(number, array, length-1)); 8 int result = (count(number, array, length-1)); 9 printf("false: result = %d, length = %d\n", result, length); 10 return result; 11 } 12
一つの参考として。
投稿2018/08/11 08:46
総合スコア6383
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2018/08/12 03:13
退会済みユーザー
2018/08/12 04:00
2018/08/12 04:04
退会済みユーザー
2018/08/12 05:43 編集
2018/08/12 05:52 編集
退会済みユーザー
2018/08/12 06:21 編集
2018/08/12 06:42
退会済みユーザー
2018/08/12 07:38
2018/08/12 08:08
退会済みユーザー
2018/08/12 08:25
2018/08/12 08:30 編集
0
そもそも質問文にあるコードは、正しく 4 の数をカウントできません。
array[16] = {1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4}
array[17] = {1,2,3,4,5,6,7,8,9,10,9,8,7,6,5,4,4}
と最後に 配列の最後に 4 と加えてから、 count(array, 16) お呼び出しのままにすると、
結果は 3 となります。
count(array, 16) は、
array 0 .. 15 のなかの 4 の数のカウントでなく、 array 0 .. 16 のなかの 4 の数のカウントをしているからです。
array[16] に戻して、さらに count() をつぎのようにしてから実行してみます。
c
1 int count(int number, int *array, int length){ 2 if(length == -1) return(0); // 終了条件 3 4 printf("%d, %d\n", array[length], length); // <-- この行を追加 5 if(array[length] == number) 6 return(1 + count(number, array, length-1)); 7 else 8 return(count(number, array, length-1)); 9}
プログラムをすこし書き換えてみました。
c
1#include <stdio.h> 2 3int count(int number, int *array, int length); 4 5int main() { 6 int array[16] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 7 9, 8, 7, 6, 5, 4}; // 数値を格納した配列 8 int number = 4; // サーチする数値 9 10 printf("配列の先頭 %d 個に含まれる %d の数は %d です\n", 16, number, count(number, array, 16)); 11 printf("配列の先頭 %d 個に含まれる %d の数は %d です\n", 15, number, count(number, array, 15)); 12 printf("配列の先頭 %d 個に含まれる %d の数は %d です\n", 0, number, count(number, array, 0)); 13 return(0); 14} 15 16/* 再帰関数 */ 17int count(int number, int *array, int length) { 18 if (length == 0) return(0); // 終了条件 19 20 int c = (array[length - 1] == number) ? 1 : 0; 21 return(c + count(number, array, length - 1)); 22} 23
投稿2018/08/14 01:55
総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2018/08/14 05:20
退会済みユーザー
2018/08/14 05:22
2018/08/14 08:21
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2018/08/13 09:48 編集
退会済みユーザー
2018/08/13 10:00
2018/08/13 10:48
2018/08/13 10:53
退会済みユーザー
2018/08/13 10:55
2018/08/13 11:54