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

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

0 голосов
/ 05 сентября 2018

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

Например, 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, чтобы они работали? Можно ли каким-либо образом использовать алгоритм Ньютона-Рафсона ??

Ответы [ 2 ]

0 голосов
/ 05 сентября 2018

Считайте, что массив [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))

OUTPUT 

[22.0, 7]
0 голосов
/ 05 сентября 2018

В стандартной библиотеке 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))

1010 * выходы * 

(22, 7)

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

...