【例30.1】 平方根

解题思路

严格使用题给迭代，y 从 1 开始，每次赋值为 (y+x/y)/2，共迭代 n 次。

正确性说明

按上述推导执行：每次仅处理当前输入或当前步骤，并把它对答案的贡献计入对应状态。所有需要处理的情况均被覆盖，结束时保存的量就是题目所求。

易错点

不能直接用 sqrt 替代，因为题目要求给定次数下的近似值；三位小数。

复杂度

时间 O(n)，额外空间 O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    double x;
    int n;
    cin >> x >> n;
    double y = 1;
    for (int i = 0; i < n; i++)
        y = (y + x / y) / 2;
    cout << fixed << setprecision(3) << y << "\n";
    return 0;
}