資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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 次瀏覽
廣告