Нахождение квадратного корня числа методом деления пополам - PullRequest
Новая
       19

Нахождение квадратного корня числа методом деления пополам

0 голосов
/ 08 октября 2019

Я попытался найти квадратный корень числа, такого, что 

 abs(y**2-x) < epsilon

, используя метод деления пополам, однако, я не получаю ответ, который хочу, когда я запускаю его. Если я выберу x равным 4 и 0,01, я ожидаю получить 2, но вместо этого получаю 1,0. Может ли кто-нибудь помочь мне исправить это?

Контрольный пример: 

 > squareRoot(4, 0.01)
 > 1.0

def squareRoot(x, epsilon):
    low = 0
    high = max(1.0, x)
    y = (high+low) / 2.0
    while abs(y**2 - x)<epsilon:
        if y**2 < x:
            low = y
        else:
            high = y
        y = (high + low) / 2.0
    return y

1 Ответ

3 голосов
/ 08 октября 2019

Ваше условие while перевернуло неравенство. Вы изменяете y только в том случае, если вы уже нашли достаточно хороший ответ. В псевдокоде вы хотите сделать следующее. 

def squareRoot(x, epsilon):
  <set up the base case>
  while <you haven't found the answer yet>:
    <bisect to keep looking for the answer>
  return <the answer>

Сравните это с тем, что делает ваш код в настоящее время. 

def squareRoot(x, epsilon):
  <set up the base case>
  while <you have found the answer>:
    <bisect to keep looking for the answer>
  return <the answer>

Односимвольная модификация вашего кода, которая дает правильное решениетогда следующее. 

def squareRoot(x,epsilon):
    low = 0
    high = max(1.0,x)
    y = (high+low)/2.0
    while abs(y**2-x)>=epsilon:
        if y**2 < x:
            low = y
        else:
            high = y
        y = (high+low)/2.0
    return y
...