Метод Герона в Python

Question

Метод Герона генерирует последовательность чисел, которые представляют лучшие и лучшие приближения для √n. Первое число в последовательности является произвольным предположением; любое другое число в последовательности получается из предыдущего числа prev по формуле:

    (1/2)*(prev+n/prev)

Я должен написать функцию heron() в качестве входных данных используются два числа: n и error. Функция должна начинаться с начального предположения 1,0 для √n, а затем многократно генерировать лучшие приближения, пока разница (точнее, абсолютная величина разницы) между последовательными приближениями не станет большей ошибкой.

    usage:
    >>> heron(4.0, 0.5)
    2.05
    >>> heron(4.0, 0.1)
    2.000609756097561

это немного сложно, но мне нужно будет отслеживать четыре переменные:

    # n, error, prev and current

Мне также понадобится цикл while с условием:

    ((current - prev) > error):

Общее правило для цикла while:

    # old current goes into new prev

Так что это то, что я получил до сих пор, это не так много, потому что для начала я не знаю, как включить оператор if в цикл while.

def heron(n, error):
    guess = 1
    current = 1
    prev = 0
    while (current - prev) > error:
        previous==1/2*(guess+n/guess):
           print (previous) # just a simple print statement
                            # in order to see what i have so far

Может кто-нибудь дать мне несколько указателей в правильном направлении, пожалуйста?

благодарю вас

Answer 1

Если вы не хотите использовать генераторы, то самым простым будет:

def heron(n, error):
    prev, new = 1.0, 0.5 * (1 + n)
    while abs(new - prev) > error:
        prev, new = new, 0.5 * (new + n/new)
    return new

Вы также можете создать "бесконечную" последовательность чисел цапли:

def heron(n):
    prev = 1.0
    yield prev, float('inf')
    while True:
        new = 0.5 * (prev + n/prev)
        error = new - prev
        yield new, error
        prev = new

Теперь вы можете напечатать столько чисел, сколько захотите, например:

list(islice(heron(2), 3))     # First 3 numbers and associated errors

Генерируйте, пока ошибка больше 0,01:

list(takewhile(lambda x:x[1] > 0.01, heron(2)))

Answer 2

Просто, основываясь на ответе @ elyase, вот как можно получить квадратный корень произвольной точности из предоставленного ими генератора чисел цапли. (генератор просто дает следующий номер в последовательности цапли)

def heron(n): ### posted by elyase
    a = 1.0
    yield a
    while True:
        a = 0.5 * (a + n/a)
        yield a

def sqrt_heron(n, err):
    g = heron(n)
    prev = g.next()
    current = g.next()
    while( (prev - current) > err):
        prev = current
        current = g.next()
        print current, prev
    return current

print sqrt_heron(169.0,0.1)

Помимо синтаксиса Python, вещь, которая может сбить вас с толку, заключается в том, что вам нужно две догадки, рассчитанные из вашего начального предположения, чтобы начать, и вы сравниваете, насколько далеко друг от друга эти догадки. В то время как условие должно быть (prev - current) > err не (current - prev) > err поскольку мы ожидаем, что предыдущее предположение будет ближе к квадрату (и, следовательно, больше), чем текущее предположение, которое должно быть ближе к квадратному корню. Поскольку начальное предположение может быть любым положительным числом, нам нужно рассчитать две итерации из него, чтобы убедиться, что current будет меньше чем prev,

Answer 3

Я имел дело с той же проблемой, и у меня было не так много инструментов для ее решения, поскольку мои знания в Python очень ограничены.
Я придумал это решение, которое не очень элегантно и не продвинуто, но оно решает проблему с использованием алгоритма Герона. Просто хочу, чтобы он поделился этим здесь:

print("Please enter a positive integer 'x' to find its square root.")
x = int(input("x ="))
g = int(input("What's your best guess: "))
results = [g]
if g * g == x:
    print("Good guess! The square root of", x, "is", g)
else:
    g = (g + (x / g)) / 2
    results.append(g)
    while results[-1] != results[-2]:
        g = (g + (x / g)) / 2
        results.append(g)
    else:
        print(results)
        print("Not quite. The square root of", x, "is", results[-1])

Answer 4

Я думаю, что это соответствует вашим требованиям (примечание: я написал это с python 2.7.10): он не предполагает предположения 1, и принимает аргументы 'num' и 'допуск' в качестве аргументов для 'n' и 'error'. Кроме того, он не использует переменные "prev" и "current" или цикл while - это часть ваших требований или ваши мысли относительно решения?

def heron(num, guess, tolerance):
    if guess**2 != num:
        ##print "guess =", guess
        if abs(float(num) - float(guess)**2) > float(tolerance):
            avg_guess = 0.5 * (float(guess) + (float(num) / float(guess)))
            return heron(num, avg_guess, tolerance)
        print "Given your tolerance, this is Heron's best guess:", guess
    else:
        print guess, "is correct!"

Раскомментируйте print cmd, если вы хотите увидеть ход догадок.

Answer 5

Другие ответы, когда я пишу это, используют функцию генератора Python. Я люблю генераторы, но они излишни для этой простой проблемы. Ниже приведены простые решения while петли.

Комментарии под кодом. heron0() это то, что вы просили; heron() моя предложенная версия

def heron0(n, error):
    guess = 1.0
    prev = 0.0
    while (guess - prev) > error:
        prev = guess
        guess = 0.5*(guess+n/guess)
        print("DEBUG: New guess: %f" % guess)
    return guess

def _close_enough(guess, n, allowed_error):
    low = n - allowed_error
    high = n + allowed_error
    return low <= guess**2 <= high

def heron(n, allowed_error):
    guess = 1.0
    while not _close_enough(guess, n, allowed_error):
        guess = 0.5*(guess+n/guess)
        print("DEBUG: New guess: %f" % guess)
    return guess

print("Result: %f" % heron0(4, 1e-6))
print("Result: %f" % heron(4, 1e-6))

Комментарии:

• Вам не нужны оба guess а также current, Ты можешь использовать guess провести текущее предположение.

• Я не знаю, почему вы спрашивали о if заявление в while петля. Во-первых, это легко: вы просто вставляете его и делаете отступы для операторов, которые находятся под if, Во-вторых, эта проблема не нужна.

• Это легко и быстро обнаружить, guess близко к prev, Но я думаю, что для численной точности было бы лучше напрямую проверить, насколько хорошо квадратный корень guess на самом деле Итак, возведите в квадрат значение guess и посмотреть, если это близко к n, Посмотрите, как в Python разрешено проверять, является ли значение одновременно большим или равным меньшему значению, а также меньшим или равным большому значению. (Альтернативный способ проверки: abs(n - guess**2) <= allowed_error)

• В Python 2.x, если вы разделите целое число на целое, вы, вероятно, получите целочисленный результат. таким образом 1/2 может очень возможно иметь результат 0, Есть несколько способов исправить это, или вы можете запустить вашу программу в Python 3.x, которая гарантирует, что 1/2 возвращается 0.5, но это просто сделать ваше начальное значение для guess быть числом с плавающей точкой.