数据结构
网络
关系数据库管理系统 (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 次浏览
广告