代码之家 › 专栏 › 技术社区 › Yanick Rochon

当n>167时,如何在JavaScript中实现nCr算法(组合)?

linear-programming math javascript

0

Yanick Rochon · 技术社区 · 3 年前

我刚接受这个挑战,就被难住了,一片茫然。问题有点像这样:

有些棋手将参加决斗。例如,4名棋手(A、B、C、D),由2人配对,共产生6个棋局:AB、AC、AD、BC、BD、CD。编写一个函数,取一个整数值,并返回可能的组合数。

测验:
gameCount(4);     // 6
gameCount(10000); // 49995000

我记得,很多年前,我上的数学课是关于线性问题的,这就是其中之一。谷歌搜索很快就得出了nCr公式。所以我很快写下了代码:

const r = 2;
const factorial = n => {
  let f = 1;
  for (let i = 2; i <= n; ++i) {
    f = f * i;
  }
  return f;
}
const gameCount = n => factorial(n) / (factorial(r) * factorial(n - r));

console.log( gameCount(4) );     // 6
console.log( gameCount(10000) ); // NaN

这个 NaN 起初我很困惑,但后来我意识到 10000! 是一个相当大的数字!

如何优化 gameCount 通过保持线性来接受大的数字?

注: 我知道 factorial 函数不是线性的,但这是我当时写的。理想的解决方案是让所有东西都是线性的,也许可以完全去掉阶乘。

1 回复 | 直到 3 年前

1

3

Siguza 3 年前

你现在要做的是计算两个非常大的数字,它们共享一个非常大公约数,然后将一个除以另一个。你就是无法计算除数( factorial(n - r) )首先。

更改您的 factorial 函数以获取最小参数。

const r = 2;
const factorial = (n, m) => {
  let f = 1;
  for (let i = n; i > m; --i) {
    f = f * i;
  }
  return f;
}
const gameCount = n => factorial(n, n - r) / factorial(r, 0);

console.log( gameCount(4) );     // 6
console.log( gameCount(10000) ); // 49995000

不过请注意,这只会避免 NaN 只要 r 相当小。如果你需要它来处理两种情况 n 和 r 很大,您不能使用本机JavaScript数字类型。我建议调查一下 BigInt 对于这种情况。

为了完整起见,如果 r = 2 是你所关心的,那么你的整个公式可以简化为:

const gameCount = n => (n * (n - 1)) / 2;