首页 > 代码库 > 开平方问题

开平方问题

求一个数的开平方,方法有很多,最简单的方法就是二分法,再上一个档次是牛顿迭代法,还有更上档次的算法涉及到更高深的数学知识。

这里只是尝试这两种方法。

    1、二分法求平方根,直接上代码。

 1 /*************************************************************************
 2 **File Name            :mysqrt.c
 3 **Author            :
 4 **Contact            :
 5 **Created Time        :Tue 13 May 2014 09:58:54 AM CST
 6 **Brief                :
 7 **Development note    :
 8  ************************************************************************/
 9 #define E 0.001
10 #define ABS(a) (((a)>0)?(a):(-(a)))
11 /********************************include*********************************/
12 #include<stdio.h>
13 double sqrtby2(int N)
14 {
15     if(N == 0)
16         return 0;
17     if(N < 0)
18         return -1;
19     double mid;
20     double start = 0;
21     double end = N;
22     mid = (start + end)/2.0;
23     while(ABS(mid*mid - N) > E){
24         if(mid*mid > N)
25             end = mid;
26         else
27             start = mid;
28         mid = (start + end) / 2.0;
29     }
30     return mid;
31 }

---------------------编写代码中遇到的问题----------------------------

宏的使用,宏所做的是字符串和参数的替换,虽然知道这一点,但是没有较深的体会,编写ABS宏时,由于宏参数在定义中未使用括号,导致返回值错误。

    2、牛顿迭代法

    牛顿迭代法主要用来求方程的近似解,其最大有点事在方程的单根附近平方收敛。一下参考自百度百科:

    设r是的根,选取作为r的初始近似值,过点做曲线的切线L,L的方程为

,求出L与x轴交点的横坐标
,称x1为r的一次近似值。
 
过点
做曲线
的切线,并求该切线与x轴交点的横坐标
,称
为r的二次近似值。
 
重复以上过程,得r的近似值序列,其中,
称为r的
次近似值,上式称为牛顿迭代公式

用牛顿迭代法解非线性方程,是把非线性方程线性化的一种近似方法。把

在点
的某邻域内展开成泰勒级数
,取其线性部分(即泰勒展开的前两项),并令其等于0,即
,以作为非线性方程
的近似方程,若
,则其解为
, 这样,得到牛顿迭代法的一个迭代关系式:
已经证明,如果是连续的,并且待求的零点是孤立的,那么在零点周围存在一个区域,只要初始值位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。
 
 1 /*************************************************************************
 2 **File Name            :mysqrt.c
 3 **Author            :
 4 **Contact            :
 5 **Created Time        :Tue 13 May 2014 09:58:54 AM CST
 6 **Brief                :
 7 **Development note    :
 8  ************************************************************************/
 9 #define E 0.001
10 #define ABS(a) (((a)>0)?(a):(-(a)))
11 /********************************include*********************************/
12 #include<stdio.h>
13 double sqrtbynewton(int N)
14 {
15     if(N == 0)
16         return 0;
17     if(N < 0)
18         return -1;
19     double x0 = N/2.0;
20     double x1;
21     while(ABS(x0*x0 - N) > E){
22         x1 = (x0 + N/x0)/2.0;
23         x0 = x1;
24     }
25     return x0;
26 }