Как рационализировать дробь без использования стандартных функций?

Итак, как написать код на Python, который находит рациональное число, закрытое до дроби, скажем, f, без использования стандартных функциональных модулей?

E.g., 3.14=22/7

Также числитель и знаменатель имеют ограничения, например:

  • числитель не может быть больше p
  • знаменатель не может быть больше q.

Моя работа:

# calculates i/j upto a precision of 0.001 closer to f.
while( abs((i/j)-f)> 0.001 and i<p, j<q):
    j=j-1
    i =?,

Теперь я в замешательстве. Как мне изменить свои i и j, чтобы они работали? Могу ли я каким-либо образом использовать алгоритм Ньютона Рафсона??


python newtons-method
person Paranoid    schedule 05.09.2018    source источник
comment
ваш пример кода не кажется полным   -  person rocksportrocker    schedule 05.09.2018
comment
3,14 == 314/100. Теперь просто найдите наименьший общий знаменатель, чтобы упростить дробь, если хотите.   -  person zvone    schedule 05.09.2018

Ответы (2)


arrow_upward
0
arrow_downward

Рассмотрим этот массив [1,..q]

Затем умножьте каждый элемент на заданную дробь f, затем проверьте ближайший элемент к p . Я думаю, что этот алгоритм будет выполняться за O(q) . ну, вы можете улучшить алгоритм, чтобы проверить, что p или q меньше, а затем сделать то же самое.

import math
def foo(f,p,q):
    m=9999

    for i in range(1,q+1):
        reqp=round(f*i)

        if(  abs((float(reqp)/i) -f ) <m and reqp>0 and reqp <=p ):
            m=abs(float(reqp)/i-f)
            values = [reqp,i]
    return values

print(foo(3.14,30,30))

ВЫВОД

[22.0, 7]
person Albin Paul    schedule 05.09.2018

arrow_upward
0
arrow_downward

В стандартной библиотеке Pythons есть модуль для этого:

print(fractions.Fraction.from_float(math.pi).limit_denominator(30))

выходы

22/7

Подход грубой силы:

import math

def approx(number, p):
    best = None
    best_dist = number
    for d in range(1, p + 1):
        n0 = int(d / number)
        for n in (n0 -1, n0, n0 + 1):
            if n <= 0:
                continue
            dist = abs(number - d / n)
            if dist < best_dist:
                best_dist = dist
                best = (d, n)
    return best


print(approx(math.pi, 30))

выходы

(22, 7)

И тогда есть третий вариант: https://www.johndcook.com/blog/2010/10/20/best-rational-Approimation/

person rocksportrocker    schedule 05.09.2018