資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：在給定約束條件下查詢min和max之間的公分母
假設我們有兩個長整型值maximum和minimum。我們必須找到一個公分母n/d，使得min <= d <= max。並且|n/d - π|最小。這裡π = 3.14159265...如果有多個分數滿足這個條件，則返回分母最小的分數。
因此，如果輸入類似於minimum = 1 maximum = 10，則輸出將為22/7。
為了解決這個問題，我們將遵循以下步驟：
- P := 分數 (5706674932067741 / 1816491048114374) - 3
- a := 0, b := 1, c := 1, d := 1
- farey := 一組對的陣列，它最初有兩對 (a, b) 和 (c, d)
- 無條件迴圈執行以下操作：
- f := b + d
- 如果 f > maximum - minimum，則
- 退出迴圈
- e := a + c
- 在farey的末尾插入對 (e, f)
- 如果 P < (e/f) 的值，則
- c := e 且 d := f
- 否則，
- a := e 且 b := f
- p_min := P * minimum 的下限
- 當 minimum <= maximum 時，執行以下操作：
- c := 0, d := 0
- 對於farey中的每一對 (a, b)，執行以下操作：
- 如果 minimum + b > maximum，則
- 退出迴圈
- 如果 |(p_min + a)/ (minimum + b) - P| < |p_min / minimum - P|，則
- c := a, d := b
- 退出迴圈
- 如果 minimum + b > maximum，則
- 如果 d 等於 0，則
- 退出迴圈
- p_min := p_min + c
- minimum := minimum + d
- 返回分數 (p_min + 3 * minimum) / minimum
示例
讓我們看下面的實現以更好地理解：
from fractions import Fraction
def solve(minimum, maximum):
P = Fraction(5706674932067741, 1816491048114374) - 3
a, b, c, d = 0, 1, 1, 1
farey = [(a,b),(c,d)]
while True:
f = b + d
if f > maximum - minimum:
break
e = a + c
farey.append((e, f))
if P < Fraction(e, f):
c, d = e, f
else:
a, b = e, f
p_min = int(P * minimum)
while minimum <= maximum:
c, d = 0, 0
for a, b in farey:
if minimum + b > maximum:
break
if abs(Fraction(p_min + a, minimum + b).real - P) < abs(Fraction(p_min, minimum).real - P):
c, d = a, b
break
if d == 0:
break
p_min += c
minimum += d
return ("{}/{}".format(p_min + 3 * minimum, minimum))
minimum = 1
maximum = 10
print(solve(minimum, maximum))輸入
4, 27
輸出
22/7
更新於：2021年10月25日
298 次瀏覽
廣告