資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會研究
時尚研究
法律研究在 Python 中應用俄羅斯農民乘法原理的程式
假設我們得到了四個整數 p、q、r 和 k。我們將使用一種稱為俄羅斯農民乘法的方法，並確定 (p + q.i)^r = r + s.i 的值。我們必須返回 r mod k 和 s mod k 的值。
因此，如果輸入為 p = 3，q = 0，r = 8，k = 10000，則輸出將為 (6561, 0) 3^8 = 6561，因為 q = 0，r mod k 的值為 6561。
為了解決這個問題，我們將按照以下步驟操作 −
- 如果 r 與 0 相同，那麼
- 返回 1
- 否則當 r 與 1 相同時，那麼
- 返回包含 (p mod k, q mod k) 的一對
- 否則當 r mod 2 是 0 時，那麼
- 返回 solve((p*p - q*q) mod k, 2*p*q mod k, r/2, k)
- 否則，
- 一對 (pr, qr) = solve(p, q, r-1, k)
- 返回包含 ((p * pr - q * qr) mod k, (p * qr + q * pr) mod k) 的一對
示例
讓我們看看以下實現以獲得更好的理解 −
def solve(p, q, r, k):
if r == 0:
return 1
elif r == 1:
return (p % k, q % k)
elif r % 2 == 0:
return solve((p*p - q*q) % k, 2*p*q % k, r/2, k)
else:
(pr, qr) = solve(p, q, r-1, k)
return ((p * pr - q * qr) % k, (p * qr + q * pr) % k)
print(solve(3, 0, 8, 10000))輸入
3, 0, 8, 10000
輸出
(6561, 0)
更新於： 23-Oct-2021
420 次瀏覽
Advertisement