用 Python 编写程序，以高效的方式在 0 到 n 范围内查找 r 的 nCr 值

pythonserver side programmingprogramming更新于 2026/1/31 14:36:17

假设我们必须多次计算 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))