Получение бесконечного цикла в вавилонском алгоритме для квадратных корней в C++

Question

Я тщательно искал эту тему по всему Интернету, и темы либо мертвы, либо используют другой метод, чем тот, который описан в моей книге.

Например, http://www.geeksforgeeks.org/square-root-of-a-perfect-square/. Это не работает для меня, потому что мой алгоритм должен зацикливаться, пока не достигнет 1% от последнего "предположения".

Вот вопрос из текста.

Вавилонский алгоритм для вычисления квадратного корня числа n выглядит следующим образом:

1. Сделайте предположение по числу (вы можете выбрать n/2 в качестве первоначального предположения).
2. Вычислить r = n / угадай
3. Установить угадать = (угадать + г) / 2
4. Вернитесь к шагу 2 столько раз, сколько необходимо. Чем больше повторяются шаги 2 и 3, тем ближе к квадратному корню из n становится предположение.

Напишите программу, которая вводит целое число для n, повторяет вавилонский алгоритм до тех пор, пока догадка не окажется в пределах 1% от предыдущей догадки, и выводит ответ в виде двойного числа.

Я написал следующий код:

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int main()
{
int  n;
double r, guess(4), lastGuess;

cout << "Enter a number to find the square root of: ";
cin >> n;

do
{

    r = n / guess;
    lastGuess = guess;
    guess = ( guess + r ) / 2;

//  cout <<"Guess: " << guess << endl;
//  cout <<"Last Guess: " << lastGuess << endl;

    cout << "Guess : " << guess  << endl;
    cout << "Last Guess 1% = " << lastGuess + ( lastGuess * 0.01 ) << endl;
    cout << "r = " << r << endl;

} while( guess >= lastGuess * 0.01 );
cout << r;

return 0;
}

Программа вычисляет правильный ответ для r, но цикл не прерывается, несмотря на то, что предположение составляет более 1%, добавленных в lastGuess.

Эта программа производит следующий вывод при вводе 144 как n.

....
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
r = 12
Guess : 12
Last Guess 1% = 12.12
....

Корень (r) правильный (12). Предположение меньше, чем lastGuess (12 < 12.12), что должно возвращать ложное условие, правильно? Почему цикл не заканчивается?

Answer 1

Если вы хотите добавить 1%, вам нужно умножить на 1,01, а не 0,01.

while( guess >= lastGuess * 1.01 );

Кстати, это повторяется, в то время как догадка растет более чем на 1%. Вы должны также учесть обратное, что оно могло уменьшиться более чем на 1%. Приближение может приближаться к ответу с любого направления. (Это приблизится к положительным корням справа и отрицательным корням слева.)

Answer 2

Во время печати вашего lastGuess вы используете

 lastGuess + ( lastGuess * 0.01 )

Но при проверке состояния цикла вы используете

lastGuess*0.01

Таким образом, в условии цикла используйте то же уравнение, которое вы используете для печати lastGuess значение.

Answer 3

Чтобы правильно выйти из цикла, используйте что-то похожее на это.

void f(int N)
{
    double x = N / 4;
    double prev = 0.0f;

    while(1)
    {
        x = 0.5 * (x + N / x);
        if (prev == x)
            break;

        prev = x;
        printf("val: %f\n", x);
    }

    printf("SQRT(%d) = %f\n", N, x);
}

Answer 4

У меня была такая же проблема в моей книге. Это то, что я написал, и он отлично работает.

#include <iostream>
using namespace std;
int main()
{
    double guess, root, previousGuess;
    int number;
    cout << "Enter a number to find the Babylonian square root.\n";
    cin >> number;
    cout << "You want to find the square root of " << number << ".\n";
    cout << "Enter a guess for the square root.\n";
    cin >> guess;

    do
    {
        root = number / guess;
        previousGuess = guess;
        guess = (guess + root ) / 2;

    } while(guess < 0.99*previousGuess || guess > 1.01*previousGuess);

    cout << "The answer is " << guess << ".\n";
    return 0;
}