資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：計算使用樓梯到達下一層樓的方法數
假設有一個N階樓梯。一個人可以一步一步地走，或者在每一步中最多跳N步。我們必須找到到達頂層樓的方法數。N值可能很大，我們只對方法數的前K位和後K位數字感興趣。
因此，如果輸入類似於N = 10，k = 2，則輸出將為63，因為有10個臺階，如果有S種方法可以到達頂部，則將S視為wxyz形式。因此，wx + yz的和為63。
為了解決這個問題，我們將遵循以下步驟：
- N := N - 1
- c := 2 * ceil(k + log₁₀(N))
- e := N, b := 2, s := 1
- 當 e > 0 時，執行以下操作：
- 如果 e 是奇數，則
- s := (s*b) 的前 p-c 位數字，其中 p 是 s*b 的位數
- e := floor(e/2)
- b := (b*b) 的前 p-c 位數字，其中 p 是 b*b 的位數
- 如果 e 是奇數，則
- s := s 的前 p - k 位數字，其中 p 是 s 的位數
- r := s + (2^N) mod 10^k
- 返回 r
示例
讓我們看下面的實現以更好地理解：
from math import log10,ceil
def solve(N,k):
N -= 1
c = 2*ceil(k + log10(N))
e = N
b = 2
s = 1
while e > 0:
if e % 2 == 1:
s = int(str(s*b)[:c])
e //=2
b = int(str(b*b)[:c])
s = str(s)[:k]
r = int(s) + pow(2, N, 10**k)
return r
N = 10
k = 2
print(solve(N,k))輸入
10, 2
輸出
63
更新於：2021年10月25日
148 次檢視
廣告