Метод Heron в Python

Question

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

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

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

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

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

# n, error, prev and current 

Я также нужен в то время как петля с условием:

((current - prev) > error): 

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

# old current goes into new prev 

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

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) 

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

Answer 3

Другой ответит, поскольку я пишу это, используя функцию генератора Питона. Мне нравятся генераторы, но это слишком сложно для этой простой проблемы. Ниже приведены решения с простыми петлями 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 как число с плавающей запятой.

Answer 4

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

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!" 

Раскройте распечатку cmd, если вы хотите увидеть прогрессию догадок.