0

いくつかの統計関連の関数を実行しようとしているので、いくつかの関連手順 (つまり、確率の統計計算、任意の深さのパスカルの三角形の生成など) を実行できます。

オーバーフローに対処している可能性が高い問題に遭遇しました。たとえば、(n=30,p=1) の nPr を計算したい場合、次のように減らすことができることがわかっています。

30P1 = 30! / (30 - 1)!
     = 30! / (29)!
     = 30! / 29!
     = 30

ただし、以下の関数を使用して計算すると、整数オーバーフローのために常に無効な値が得られるようです。任意に大きな数をサポートするためにライブラリを使用する必要のない回避策はありますか? ガンマ関数に関する他の投稿を少し読みましたが、具体的な例が見つかりませんでした。

int factorial(int n) {
   return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}


int nCr(int n, int r) {
   return (nPr(n,r) / factorial(r));
   //return factorial(n) / factorial(r) / factorial(n-r));
}


int nPr(int n, int r) {
   return (factorial(n) / factorial(n-r));
}
4

5 に答える 5

3

ガンマ関数を使わずに計算する方法を次に示します。n_C_r = (n/r) * ((n-1) C (r-1)) という事実と、正の値の場合は n_C_0 = 1 という事実に依存しているため、以下のような再帰関数を記述できます。

public long combination(long n, long r) {
    if(r==0)
        return 1;
    else {
        long num = n * combination(n - 1, r - 1);
        return num/r;
    }
}
于 2012-12-16T05:31:09.977 に答える
2

次の 2 つの選択肢があると思います。

  1. 大きな整数ライブラリを使用します。こうすれば、精度が失われることはありません (浮動小数点が機能する場合もありますが、代用としては不十分です)。

  2. 関数を再構築して、中間値が高くならないようにします。たとえば、 からまでfactorial(x)/factorial(y)のすべての数値の積です。したがって、ループを記述して乗算するだけです。このようにして、最終結果がオーバーフローした場合にのみオーバーフローが発生します。y+1x

于 2012-06-13T13:45:35.003 に答える
1

符号付きの値を処理する必要がない場合（そして処理しているように見えない場合）、より大きな整数型を使用してみることができますunsigned long long。それでも不十分な場合は、任意の長整数をサポートする非標準ライブラリを使用する必要があります。このlong long型を使用するには、C99コンパイラのサポートが必要であることに注意してください（GCCを使用する場合は、でコンパイルする必要がある場合があります-std=c99）。

long double編集：一部のシステムでは80ビットであるにもっと収まる可能性があります。

于 2012-06-13T13:48:10.123 に答える
1

私は密集しているかもしれませんが、doubleここで s とガンマ関数に行くのはやり過ぎのようです。

任意に大きな数をサポートするためにライブラリを使用する必要のない回避策はありますか?

確かにあります。常に何を扱っているか、つまり整数の範囲の積を正確に知っています。整数の範囲は、整数の有限リストの特殊なケースです。C でリストを表現する慣用的な方法が何であるかはわかりません。そのため、C っぽい疑似コードに固執します。

make_list(from, to)
    return a list containing from, from+1, ..., to

concatenate_lists(list1, list2)
    return a list with all the elements from list1 and list2

calculate_list_product(list)
    return list[0] * list[1] * ... * list[last]

calculate_list_quotient(numerator_list, denominator_list)
    /* 
    be a bit clever here: form the product of the elements of numerator_list, but
    any time the running product is divisible by an element of denominator_list,
    divide the running product by that element and remove it from consideration
    */

n_P_r(n, r)
   /* nPr is n! / (n-r)! 
      which simplifies to n * n-1 * ... * r+1
       so we can just: */
   return calculate_list_product(make_list(r+1, n)) 

n_C_r(n, r)
   /* nCr is n! / (r! (n-r)!) */
    return calculate_list_quotient(
        make_list(1, n), 
        concatenate_lists(make_list(1, r), make_list(1, n-r))
    )

実際に階乗を計算することはないことに注意してください!

于 2012-06-14T09:44:34.240 に答える
0

あなたは正しい軌道に乗っているように見えるので、ここに行きます：

#include <math.h>
#include <stdio.h>

int nCr(int n, int r) {
   if(r>n) {
      printf("FATAL ERROR"); return 0;
     }       
   if(n==0 || r==0 || n==r) {
      return 1;
   } else {
      return (int)lround( ((double)n/(double)(n-r)/(double)r) * exp(lgamma(n) - lgamma(n-r) - lgamma(r)));
   }
}


int nPr(int n, int r) {
   if(r>n) {printf("FATAL ERROR"; return 0;}
   if(n==0 || r==0) {
      return 1;
   } else {
      if (n==r) {
         r = n - 1;
      }
      return (int)lround( ((double)n/(double)(n-r)) * exp(lgamma(n) - lgamma(n-r)));
   }
}

コンパイルするには、次のようにします。gcc -lm myFile.c && ./a.out

double結果の精度は、データ型のビット深度によって制限されることに注意してください。これで良い結果が得られるはずですが、注意してください:int上記のすべての を に置き換えてもlong long unsigned、より大きな値の に対して必ずしも正確な結果が保証されるとは限りませんn,r。ある時点で、任意の大きな値を処理するために何らかの数学ライブラリが必要になりますが、これは小さな入力値の場合にそれを回避するのに役立ちます。

于 2012-06-13T13:55:33.577 に答える