当前位置:编程学习 > C/C++ >>

C++中下面这段代码什么意思

double sqrt(double n)
{
 double num=2;
 for(int i=1;i<=1000;++i)
 {
  num=(num+n/num)/2;
 }
 return n?num:0;
}
追问:说具体点。。
答案:下面是详细的算法描述:利用牛顿迭代法求平方根

求n的平方根,先假设一猜测值X0 = 1,然后根据以下公式求出X1,再将X1代入公式右边,继续求出X2…通过有效次迭代后即可求出n的平方根,Xk+1

先让我们来验证下这个巧妙的方法准确性,来算下2的平方根 (Computed by Mathomatic)

1-> x_new = ( x_old + y/x_old )/2y(x_old + -----)x_old#1: x_new = ---------------21-> calculate x_old 1Enter y: 2Enter initial x_old: 1 x_new = 1.51-> calculate x_old 2Enter y: 2Enter initial x_old: 1 x_new = 1.41666666666671-> calculate x_old 3Enter y: 2Enter initial x_old: 1 x_new = 1.41421568627451-> calculate x_old 10Enter y: 2Enter initial x_old: 1Convergence reached after 6 iterations. x_new = 1.4142135623731...

可见,随着迭代次数的增加,运算值会愈发接近真实值。很神奇的算法,可是怎么来的呢? 查了下易做图和wolfram,原来算法的名字叫Newton’s Iteration (牛顿迭代法)。

下面是极其つまらない(boring)的数理介绍,不喜欢数学的言下之意也就是绝大部分人可以略过了。

简单推导

假设f(x)是关于X的函数:

求出f(x)的一阶导,即斜率:

简化等式得到:

然后利用得到的最终式进行迭代运算直至求到一个比较精确的满意值,为什么可以用迭代法呢?理由是中值定理(Intermediate Value Theorem):

如果f函数在闭区间[a,b]内连续,必存在一点x使得f(x) = c,c是函数f在闭区间[a,b]内的一点

我们先猜测一X初始值,例如1,当然地球人都知道除了1本身之外任何数的平方根都不会是1。然后代入初始值,通过迭代运算不断推进,逐步靠近精确值,直到得到我们主观认为比较满意的值为止。例如要求768的平方根,因为252 = 625,而302= 900,我们可先代入一猜测值26,然后迭代运算,得到较精确值:27.7128。

回到我们最开始的那个”莫名其妙”的公式,我们要求的是N的平方根,令x2 = n,假设一关于X的函数f(x)为:

f(X) = X2 - n

求f(X)的一阶导为:

f'(X) = 2X

代入前面求到的最终式中:

Xk+1 = Xk - (Xk2 - n)/2Xk

化简即得到我们最初提到的那个求平方根的神奇公式了:

用泰勒公式推导

我之前介绍过在The Art and Science of C一书中有用到泰勒公式求平方根的算法,其实牛顿迭代法也可以看作是泰勒公式(Taylor Series)的简化,先回顾下泰勒公式:

仅保留等式右边前两项:

令f(X0+ε) = 0,得到:

再令X1 = X0 + ε0,得到ε1…依此类推可知:

转化为:

引申

从推导来看,其实牛顿迭代法不仅可以用来求平方根,还可以求立方根,甚至更复杂的运算。

同样,我们还可以利用C语言来实现下那个最简单的求平方根的公式(尽管我们可以直接用sqrt()完成)

#include <stdio.h>#include <math.h>#define N 768main() {float x=1;int i;for (i=1;i<=1000;i++) { // recursion times : 1000x = (x + N/x)/2;}printf("The square root of %d is %f\n",N,x);
求平方根

//仅仅是些预编译指令 #if!defined(AFX_STDAFX_H__BF370208_98B3_41DE_A8D0_EB2E64480E6D__INCLUDED_) #defineAFX_STDAFX_H__BF370208_98B3_41DE_A8D0_EB2E64480E6D__INCLUDED_ //保证头文件在编译时仅被编译一次 #if_MSC_VER>1000 #pragmaonce #endif //如果_MSC_VER>1000,只编译一次 #ifndef_AFX_NO_AFXCMN_SUPPORT #include<afxcmn.h> #endif //条件指示符#ifndef检查预编译常量_AFX_NO_AFXCMN_SUPPORT在前面是否已经被定义,没有定义的话,包含头文件include<afxcmn.h>,否则什么不包含该头文件 //这些指令可以嵌套的。


上一个:看下这C++的编辑错误啊
下一个:怎样用C++实现文件另存为功能

CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,