c++ - 在巴比伦算法中为 C++ 中的平方根获取无限循环

Question

我已经在整个 Internet 上彻底搜索了这个主题，线程要么死了，要么使用了与我书中描述的方法不同的方法。

例如，http://www.geeksforgeeks.org/square-root-of-a-perfect-square/ .这对我不起作用，因为我的算法需要循环直到达到最后“猜测”的 1%。

这是文本中的问题。

The Babylonian algorithm to compute the square root of a number n is as follows:

1. Make a guess at the number (you can pick n/2 as your initial guess).
2. Compute r = n / guess
3. Set guess = (guess + r) / 2
4. Go back to step 2 for as many iterations as necessary. The more that steps 2 and 3 are repeated, the closer guess will become to the square root of n.

Write a program that inputs an integer for n, iterates through the Babylonian algorithm until guess is within 1% of the previous guess, and outputs the answer as a double.

我写了下面的代码:

#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 的正确答案，但尽管添加到 lastGuess 的猜测大于 1%，循环并未终止。

此程序在输入 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)，后者应该返回 false，对吗？为什么循环没有结束？

Answer 1

如果你想增加 1%，你需要乘以 1.01，而不是 0.01。

while( guess >= lastGuess * 1.01 );

顺便说一下，这会在 guess 增长超过 1% 时进行迭代。您还应该考虑到相反的情况，即它可能缩小了 1% 以上。近似值可以从任一方向逼近答案。 (它会从右边接近正根，从左边接近负根。)