M29917: 牛顿迭代法

implementation, http://cs101.openjudge.cn/practice/29917/

用牛顿法求一个数的平方根。

要求：初始取 1 为近似根，因此第一次迭代是过曲线上横坐标为 1 的点作切线。迭代终止条件为，上一次迭代求出的近似根，与这一次迭代求出的更精确的近似根的差，小于等于 1E-6。输出迭代终止时的迭代次数。

迭代公式：

输入

多行，每行可能是一个整数或一个小数。

输出

对输入的每行，输出一行，为对应的迭代次数和近似根，用空格分隔。

迭代次数为一个整数。根为一个浮点数，保留小数点后两位。

样例输入

12
25
144

样例输出

6 3.46
7 5.00
8 12.00

提示

implementation

来源

yan

✅ 牛顿法原理回顾

要求解 $ x = \sqrt{a} $，等价于求解方程：

f (x) = x^{2} - a = 0

牛顿迭代公式为：

x_{n + 1} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}

其中：

$ f(x) = x^2 - a $
$ f'(x) = 2x $

代入得迭代公式：

x_{n + 1} = x_{n} - \frac{x_{n}^{2} - a}{2 x_{n}} = \frac{1}{2} (x_{n} + \frac{a}{x_{n}})

python

import sys

for line in sys.stdin:
    line = line.strip()
    if not line:
        continue
    a = float(line)
    x = 1.0
    count = 0
    while True:
        next_x = 0.5 * (x + a / x)
        count += 1
        if abs(next_x - x) <= 1e-6:
            break
        x = next_x
    print(f"{count} {next_x:.2f}")

思路：很好玩的题！当时也是想了一阵子才看懂是何意味，但是牛顿迭代法很好玩把公式给出了以后就简单多了，然后理解题目意思模拟实现即可最难的点在保留两位小数...一直用的是round保留小数，这题连交10次WA交哭了，后来在带的cheat sheet格式化字符串方法里看到了其他的输出方法终于找到了"%.2f"

python

import math
while True:
    try:
        a=float(input())
        x=1
        y=1
        k=0
        while True:
            b=y
            y=float(x-(x**2-a)/(2*x))
            x=y
            k+=1
            if abs(y-b)<=10**(-6):
                print(k,end=' ')
                print("%.2f"%y)
                break
    except EOFError:
        break

M29917: 牛顿迭代法 ​

M29917: 牛顿迭代法