Получение бесконечного цикла в вавилонском алгоритме для квадратных корней в переполнении стека
Я тщательно искал эту тему по всему Интернету, и темы либо мертвы, либо используют другой метод, чем тот, который описан в моей книге.
Например, http://www.geeksforgeeks.org/square-root-of-a-perfect-square/ . Это не работает для меня, потому что мой алгоритм должен зацикливаться, пока не достигнет 1% от последнего «предположения».
Вот вопрос из текста.
Вавилонский алгоритм для вычисления квадратного корня числа n выглядит следующим образом:
- Сделайте предположение по числу (вы можете выбрать n / 2 в качестве первоначального предположения).
- Вычислить r = n / угадай
- Установить угадать = (угадать + г) / 2
- Вернитесь к шагу 2 столько раз, сколько необходимо. Чем больше повторяются шаги 2 и 3, тем ближе будет предположение к
квадратный корень из п.Напишите программу, которая вводит целое число для 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), который должен возвращать ложное условие, правильно? Почему цикл не заканчивается?
Решение
Если вы хотите добавить 1%, вам нужно умножить на 1,01, а не 0,01.
while( guess >= lastGuess * 1.01 );
Кстати, это повторяется, в то время как догадка растет более чем на 1%. Вы должны также учесть обратное, что оно могло уменьшиться более чем на 1%. Приближение может приближаться к ответу с любого направления. (Это приблизится к положительным корням справа и отрицательным корням слева.)
Другие решения
Во время печати вашего lastGuess ты используешь
lastGuess + ( lastGuess * 0.01 )
Но при проверке состояния цикла вы используете
lastGuess*0.01
Таким образом, в условии цикла используйте то же уравнение, которое вы используете для печати lastGuess значение.
Чтобы правильно выйти из цикла, используйте что-то похожее на это.
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);
}