codeなにがし::再帰的関数で組み合わせを計算する。

再帰的関数で組み合わせを計算する。: ゲスト (G-u-m)

コード求むＩＤ：　175
登録日時：　 2007/11/06 22:23
最終更新日時：　2007/11/08 12:13
アクセス数：　2053
タグ：　 c言語

0 users

はじめまして。こんばんは。

C言語のプログラムで、質問したいことがあります。

組み合わせの計算nCrについて（http://ja.wikipedia.org/wiki/%E7%B5%84%E5%90%88%E3%81%9B_(%E6%95%B0%E5%AD%A6)）再帰的関数で計算するプログラムを書いているのですが、いまいちうまく動いてくれません。

悪いところを、ご指摘頂けると助かります。よろしくお願いします。

以下ソース
--------------------------------------------
#include <stdio.h>

int recursive_combination( int , int );

int main(void){

    int n,r;
    double ans;

    printf(" nCrを計算します\n");
    printf("input n->");
    scanf("%d",&n);
    printf("input r->");
    scanf("%d",&r);

    ans =  (double)recursive_combination( n, r);

    printf(" %d C %d = %f \n",n,r,ans);

return 0;
}

int recursive_combination( int n, int r){

    printf("%f\n",(double)n/r);
    if(r==1) return n-r+1;
    return ((dobule)(n/r))*recursive_combination( n-1 , r-1);

}

------------------ここまで--------------------------

<出力結果>

nCrを計算します
input n->5
input r->3
1.666667
2.000000
3.000000
5 C 3 = 6.000000

nCrを計算します
input n->5input r->1
5.000000
5 C 1 = 5.000000

nCrを計算します
input n->10
input r->3
3.333333
4.500000
8.000000
10 C 3 = 96.000000

nCrを計算します
input n->9
input r->3
3.000000
4.000000
7.000000
9 C 3 = 84.000000

------------------ここまで--------------------------

自分なりの分析：
n/rの部分が整数になる場合はうまく計算がおこなわれるようですが、ここが小数点を含む計算になるとその値が無視されてしまうようです。キャストも行っていて、その部分は自分なりに正しく処理されていると考えているのですが…。

よろしくお願いいたします。

1：mmike
2007/11/07 01:10

デバッグはしていないのと現状手元にCのコンパイラがないので、予想のみになります。

まず２つ指摘します。
------
//main
ans = (double)recursive_combination( n, r);
//中略
int recursive_combination( int n, int r){
    printf("%f\n",(double)n/r);
    if(r==1) return n-r+1;
    return ((dobule)(n/r))*recursive_combination( n-1 , r-1);
}
------
１つ目
recursive_combination関数の2つ目のreturnのキャストしている部分が誤字です。
dobuleではなくdoubleです。

２つ目
intを返す関数をdoubleにキャストしてもint型の内容をdoubleにするだけなので、
例え計算結果が1.6･･･となったとしても、切り捨てられた1が返るはずです。
したがって[ans=(double)]のくだりは意味のないキャストになります。

・本題
recursive_combinationが返却する型はintなので、printf文で少数が出力されていても関数は必ず整数を返却します。
計算の途中で、
[1.666667]のように出力されているにも関わらず、計算結果が整数になっているのはそのためです。
つまりrecursive_combinationのシグネチャを
int recursive_combination( int n, int r)
ではなく
double recursive_combination( int n, int r)
すればいい・・・とはいかないはずです。
近似値にはなりますが、四捨五入による丸め誤差が発生するためです。
#出力値を見ると[1.666667]のように最後が四捨五入されてますよね？

なので式を構成しなおしてロジックを変更された方が良いです。
組み合わせの結果は必ず整数になることから、分母と分子の計算をそれぞれ別に行い最後に除算してintで返却するような再帰構成にすると再帰の利用価値がでそうな気がします。

2：ゲスト
2007/11/07 14:57

そもそも小数点以下の数値が出てくることに問題があるように思います。
この数式は連続したn個の自然数の中には必ずnで割り切れる数がある事から小数点以下の数字が出ませんから、doubleを使う必要はないですね。
また、再帰的関数にする必要性もあまり感じないのですが？

例えば、

int recursive_combination( int n, int r)
{
    int i, nResult;

    for ( nResult = i = 1; i <= r; i++, n-- )
    {
        nResult = nResult * n / i;
        printf("%d", nResult);
    }

    return nResult;
}

3：ゲスト (xiyi)
2007/11/07 21:42

わしもmmikeさんと同じかと思ったけど、試してみたら違った。
問題は(dobule)(n/r)ここどす。
(double)n/rと()を落とすと、ある程度うまくいきます。
ただ、やっぱり、recursive_combination自体もdoubleにしないと
結局はそこでも落ちてしまいます。

(double)にキャストするまえに、(n/r)を計算する時点で、nもrも
intなので、その結果がすでにintに切り落とされている。
それを(double)にキャストしても意味がない。

ということで、２箇所問題ありってことです。
・(double)n/r
・double recursive_combination()
と修正すればたぶん大丈夫です。

ほな。

5：mmike
2007/11/07 23:24

xiyiさんへ
間違いの指摘ありがとうございます。

割と自信ありありで書いた割りに間違えてしまいました･･･orz
はずかしいですね。。。

6：ゲスト
2007/11/08 12:13

2です

質問内容をよく理解していなかったようです。
申し訳ないです。

整数の演算で小数点以下の切捨てによる数値の劣化は、積を求めてから商を求めることで防げますので、問題の関数の最終行を次のように直せば解が求められるのではないでしょうか？

return recursive_combination( n - 1 , r - 1 ) * n / r;

doubleを使って繰り返し計算すると有効桁の下位の方で計算誤差が発生して最終的にintにキャストしたときに数値が切り捨てられることがあります。
これが原因不明の演算エラーにつながることがあるので、小数点以下の計算する場合以外でdoubleを使用するのはお勧めしません。