0

有人可以向我解释这个找到数字平方根的递归伪代码吗？我发现很难理解，因为我没有给出 n、p 和 e 输入代表什么。谢谢。

if abs(e^2 - n) < p
    SR(n,p,e) = e     
else
    SR(n,p,e) = SR(n,p,(e+n/e)/2)

(e begins at n)
4

2 回答 2

3

n 是您想要的平方根数，e 是平方根的估计值，p 是您想要的精度，即您愿意容忍的误差。算法说：如果 e 与答案“足够接近”，即 e^2 在 n 的 p 之内，那么 e 就是您要寻找的答案；否则，尝试更好的估计，(e+n/e)2。为什么这是一个更好的估计？如果 e 大于 sqrt(n)，则 n/e 将小于 sqrt(n)，因此 sqrt(n) 将介于 e 和 n/e 之间，因此请尝试 e 和 n/e 的平均值作为下一个估计。（如果 e 小于 sqrt(n)，反之亦然）。

希望这可以帮助，

布鲁斯

于 2013-11-04T01:09:58.150 回答
1

牛顿算法不仅仅是从一个估计到“更好的估计”。为什么更好的估计是它的背后有一些详细的数学。

这个想法是，要找到形式 的任何方程的解f(x) = 0，（除了一些特殊情况），如果您有 的近似值x，则可以通过查看 的变化率来获得更好的近似值，f(x)这通常是写f'(x)出来，然后用它来计算你需要调整多少，才能更好地估计真正的解决方案。

在平方根的情况下，也就是我们要求x=sqrt(n)，我们可以写出f(x)=x^2-n，f'(x)=2x然后用牛顿算法求出 的x权f(x)=0。这意味着如果我们有一个估计值e，那么为了计算出我们的下一个估计值，我们查看f(e)=e^2-n，并询问我们需要改变多少e才能消除这个错误。由于 是 的变化率，也就是f，我们应该除以计算出我们需要调整多少，以得到我们的下一个估计值。f'(x)2e(e,e^2-n)e^2-n2ee

也就是说，我们的下一个估计应该是

  e - (e^2-n) / 2e
= e - (e / 2)  + (n / 2e)
= (e + n / e) / 2

有关牛顿算法的更多信息，请访问 http://tutorial.math.lamar.edu/Classes/CalcI/NewtonsMethod.aspx（其中有一个解释其工作原理的可爱图表）和http://www.math。 brown.edu/UTRA/linapprox.html 介绍了一些更技术性的细节。

于 2013-11-04T21:42:26.403 回答