使用Python找到min和max之间的常见分数并使用给定约束条件

使用Python找到min和max之间的常见分数并使用给定约束条件

假设我们有两个长整数值maximum和minimum。我们必须找到一个公共分数n/d,使得min <= d <= max。并且|n/d – pi|是最小的。这里的pi = 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
    • 将(e,f)对插入到farey的末尾
    • 如果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,则
      • 从循环中出来
      • 如果abs((p_min + a)/(minimum + b) – P) < abs(p_min / minimum – P),则
      • c := a,d := b
      • 从循环中出来
    • 如果d与0相同,则
      • 从循环中出来
    • p_min := p_min + c
    • o minimum := minimum + d
    • o return fraction (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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程