优化计算组合,避免溢出

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