c - 組み合わせの計算の最適化とオーバーフローの回避

Question

nCr効率的に計算すると同時にオーバーフローを回避することで立ち往生しているプログラミングの問題を解決しています。私は次の簡単な単純化を行いましたが、もっと洗練された単純化が利用できるかどうかに興味があります.

(n)!/(n-k)!*k! = n*(n-1)*.....*(max(n-k+1, k))/(min(n-k, k-1))

kのさまざまなケースを偶数または奇数と見なして、方法を提案するだけで、これ以上単純化できる可能性があります。

どんなコメントでも大歓迎です。

Answer 1

ここで興味深い解決策を見つけました: http://blog.plover.com/math/choose.html

    unsigned choose(unsigned n, unsigned k) {
      unsigned r = 1;
      unsigned d;
      if (k > n) return 0;
      for (d=1; d <= k; d++) {
        r *= n--;
        r /= d;
      }
      return r;
    }

これにより、乗算と除算を交互に実行することにより、オーバーフローが回避されます (または、少なくとも問題が制限されます)。

n = 8の例k = 4:

result = 1;
result *= 8;
result /= 1;
result *= 7;
result /= 2;
result *= 6;
result /= 3;
result *= 5;
result /= 4;
done

Answer 2

この問題も解決しなければなりませんでした。私がやったことは、乗算と除算が同じ数あるという事実を利用して、それらをまとめて、一度に1つの乗算と1つの除算を行うことでした。最後に整数として出力されますが、中間項に double を使用し、最後に最も近い整数に丸めます。

// Return the number of combinations of 'n choose k'
unsigned int binomial(unsigned int n, unsigned int k) {
unsigned int higher_idx;
unsigned int lower_idx;
if(k > n-k) {
    higher_idx = k;
    lower_idx = n - k;
} else {
    higher_idx = n - k;
    lower_idx = k;
}
double product = 1.0;
double factor;
unsigned int idx;
for(idx=n; idx>higher_idx; idx--) {
    factor = (double)idx / double(lower_idx - (n - idx));
    product *= factor;
}
return (unsigned int)(product + 0.5);
}