Рекурсивный метод Ньютона для решения проблемы квадратного корня в Python

Для a=13 и точности epsilon=10^-7. Сколько раз вы применяете формулу рекурсии Ньютона в newton_sqrt(13,10^-7)? Совет: используйте глобальные переменные.

Моя текущая функция newton_sqrt(a, epsilon) выглядит следующим образом:

def newton_sqrt(a, epsilon):
     global count  
     if a < 0:  
         print("Error: a < 0") 
         return -1  
     elif a == 0.0:  
         return 0  
     else:  
         x = abs(a)  
         newx = 0.5*(x + a/x)  
         if abs(x - newx) > epsilon:  
              newton_sqrt(newx, epsilon)  
              count = count + 1  
              if not abs(x-newx) > epsilon:  
                   print (count)  
                   return newx  
newton_sqrt(13, 0.000001)

По какой-то причине я получаю

918488688 None

как мой выход.

Пожалуйста помоги.


python recursion sqrt
person Megan Schmidt    schedule 11.09.2020    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Выхода нет, так как вы никогда не достигаете строки печати:

в основном, у вас есть:

if x:
    if not x:
        print(something)

что вы хотите, я предполагаю:

if x:
    #do something
else:
    #do somthing else

не зная математики вашей функции, я бы изменил ее на:

def newton_sqrt(a, epsilon, count):
     if a < 0:  
         print("Error: a < 0") 
         return -1  
     elif a == 0.0:  
         return 0  
     else:  
         x = abs(a)  
         newx = 0.5*(x + a/x) 
         if abs(x - newx) > epsilon:  
              count = count + 1  
              newton_sqrt(newx, epsilon, count)  
         else:
              print (count)  
              return newx

что даст вам:

newton_sqrt(13, 0.000001, 0)
23
person Jmark    schedule 11.09.2020

arrow_upward
0
arrow_downward

Во-первых, давайте проясним, что ваша функция newton_sqrt() не работает. Либо вы пытаетесь исправить глубину рекурсии, либо не знаете, что она не работает.

Рабочий newton_sqrt() будет выглядеть примерно так:

import sys

def newton_sqrt(a, epsilon, x=None):
    if a < 0:
        print("Error: a < 0", file=sys.stderr)
        return -1

    if a == 0:
        return 0

    if x is None:  # initial guess
        x = a

    new_x = (x + a / x) / 2  # refine guess

    if abs(new_x * new_x - a) < epsilon:  # test guess
        return new_x

    return newton_sqrt(a, epsilon, new_x)  # (better) guess again

print(newton_sqrt(13, 1e-06))

Как только это сработает, инструментирование глубины рекурсии с помощью глобальной переменной count будет простым:

import sys

count = 0

def newton_sqrt(a, epsilon, x=None):
    global count

    count += 1

    if a < 0:
        print("Error: a < 0", file=sys.stderr)
        return -1

    if a == 0:
        return 0

    if x is None:  # initial guess
        x = a

    new_x = (x + a / x) / 2  # refine guess

    if abs(new_x * new_x - a) < epsilon:  # test guess
        return new_x

    return newton_sqrt(a, epsilon, new_x)  # (better) guess again

print(newton_sqrt(13, 1e-06), count)

ВЫВОД

> python3 test.py
3.6055513629176015 5
>

Где 3.6055513629176015 — квадратный корень из 13, а 5 — глубина рекурсии, необходимая для его вычисления с ошибкой менее 1e-06.

person cdlane    schedule 11.09.2020