在书上看到一道题，看不懂啥意思，解释一下,

（1）先猜一个答案guess(可以将n/2作为第一个答案）
（2）计算r=n/guess
（3）令guess=(guess+r)/2
（4）如有必要返回第2步重复多次。步骤2和步骤3的重复次数越多， guess就越接近n的平方根。
写一个程序，输入整数作为n的值，重复执行巴比伦算法，直到guess与前一个guess的误差在1%范围内，将答案作为一个double输出

楼主
什么书

大概就是这样吧。
int main(int argc, char **argv)
{
    int n = 0;
    scanf("%d", &n);
    double guess = n / 2;
    double tmp = guess;
    while(true)
    {
        double r = n / guess;
        guess = (guess + r) / 2;
        if(abs(tmp - guess) / tmp < 0.001)
        {
            break;
        }
        tmp = guess;
    }
    printf("%lf", guess);
    system("pause");
}


[ 本帖最后由 zisefengye 于 2010-7-30 21:40 编辑 ]

楼主是想知道这个算法为什么对吧？那是个数学问题。


这题可以这么看，已知 a^2 ，求 a 的运算就是开方对吧？

现在把 (3) guess=(guess+r)/2 看成一系列迭代的过程，那么就是

xn+1 = (xn + r) / 2 = (xn + a^2 / xn) / 2

这里把 N 记成 a^2 是为了方便。你自己一推就会了，高中甚至初中的知识就足矣。

你把 2 乘过去，两边再同乘 xn (当然假设它不为0，否则 0 的平方根不用求)整理一下就会变成

xn^2 - 2xn+1 - a^2 = 0

如果 xn 在这个变化下趋一于一个定值 x 那么，x 代到上面也一定满足，即

x^2 - 2x - a^2 = 0   ==>  (x-a)^2 = 0  ==> x = a

就能做到反求 a 的目的。


但 xn 的变化趋一于一个定值吗？
因为 x + n / x 在 a 的两侧是单调的。所以每次算完了都会更接近 a 这个值。(我范点懒，不过确实相信应该)可以证明这个数列在给定任意非零初值之后，会收敛到 a 上。

c++面向对象程序设计