Python高效计算nCr值（r范围为0到n）的程序

假设我们需要多次计算nCr的值。我们可以用一种非常高效的方法解决这个问题。如果我们存储nCr的较小值，就可以很容易地找到较大的值。所以，如果我们有n，我们需要找到nC0到nCn的列表。如果答案过大，则返回其对10^9取模的结果。

因此，如果输入为n = 6，则输出将为[1, 6, 15, 20, 15, 6, 1]。

为了解决这个问题，我们将遵循以下步骤：

  • items := 一个包含单个元素1的列表
  • 对于r从1到n，执行以下操作：
    • 在items的末尾插入(items的最后一个元素 * (n-r+1) / r) 的向下取整结果
    • items[n-2] := items[n-2] mod 10^9，其中n是items的大小
  • 返回items

示例

让我们看下面的实现来更好地理解：

def solve(n):
   items = [1]
   for r in range(1,n+1):
      items.append(items[-1]*(n-r+1)//r)
      items[-2] %= 10**9
   return items

n = 6
print(solve(n))

输入

6

输出

[1, 6, 15, 20, 15, 6, 1]

更新于: 2021年10月23日

552 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告