有一种迭代方法叫牛顿迭代法，是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0，用某种数学方法导出等价的形式 x(n+1) = g(x(n)) =  x(n)–f(x(n))/f‘(x(n)).然后按以下步骤执行：
(1) 选一个方程的近似根，赋给变量x1;
(2) 将x0的值保存于变量x1，然后计算g(x1)，并将结果存于变量x0;
(3) 当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤(2)的计算。
若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就
认为是方程的根。
例1：已知f(x) = cos(x) - x。 x的初值为3.14159/4,用牛顿法求解方程f(x)=0的近似值，要求精确到10E－6。
算法分析：f(x)的Newton代法构造方程为：x(n+1) = xn - (cos(xn)-xn) / (-sin(xn)-1)。
#include<stdio.h>

double F1(double x); //要求解的函数
double F2(double x); //要求解的函数的一阶导数函数  
double Newton(double x0, double e);//通用Newton迭代子程序
int main()
{
    double x0 = 3.14159/4;
    double e = 10E-6;
    
    printf("x = %f\n", Newton(x0, e));
    getchar();
    return 0;       
}
double F1(double x) //要求解的函数   
{   
    return  cos(x) - x;   
}   
double F2(double x) //要求解的函数的一阶导数函数   
{   
    return  -sin(x) - 1;   
}   
double Newton(double x0, double e)//通用Newton迭代子程序   
{   
    double  x1;   

    do
    {   
        x1 = x0;    
        x0 = x1 - F1(x1) / F2(x1);   
    } while (fabs(x0 - x1) > e);   
          
    return x0;   //若返回x0和x1的平均值则更佳 
}   
例2：用牛顿迭代法求方程x^2 - 5x + 6 = 0，要求精确到10E－6。   
算法分析：取x0 = 100; 和 x0 = -100;    
f(x)的Newton代法构造方程为： x(n+1) = xn - (xn*xn – 5*xn + 6) / (2*xn - 5)  

#include<stdio.h>
double F1(double x); //要求解的函数
double F2(double x); //要求解的函数的一阶导数函数  
double Newton(double x0, double e);//通用Newton迭代子程序

int main()
{
    double x0;
    double e = 10E-6;
    x0 = 100;
    printf("x = %f\n", Newton(x0, e));
    x0 = -100;
    printf("x = %f\n", Newton(x0, e));
    getchar();
    return 0;       
}
double F1(double x) //要求解的函数   
{   
    return  x * x - 5 * x + 6;
}    
double F2(double x) //要求解的函数的一阶导数函数   
{   
    return  2 * x - 5;
}   
double Newton(double x0, double e)//通用Newton迭代子程序   
{   
    double  x1;   
    do {   
        x1 = x0;   
        x0 = x1 - F1(x1) / F2(x1);   
    } while (fabs(x0 - x1) > e);   
          
return (x0 + x1) * 0.5;   
}    
具体使用迭代法求根时应注意以下两种可能发生的情况：
　 (1) 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制;
　 (2) 方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导
致迭代失败。选初值时应使:|df(x)/dx|<1,|df(x)/dx|越小收敛速度越快!  

练习：
1．验证谷角猜想。日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：对于任意一个自然数 n ，若 n 为偶数，则将其除以 2; 若 n 为奇数，则将其乘以 3 ，然后再加 1 。如此经过有限次运算后，总可以得到自然数 1 。人们把谷角静夫的这一发现叫做“谷角猜想”。
要求：编写一个程序，由键盘输入一个自然数 n ，把 n 经过有限次运算后，最终变成自然数 1 的全过程打印出来。

2．阿米巴用简单分裂的方式繁殖，它每分裂一次要用 3 分钟。将若干个阿米巴放在一个盛满营养参液的容器内，45分钟后容器内充满了阿米巴。已知容器最多可以装阿米巴2^20个。试问，开始的时候往容器内放了多少个阿米巴？请编程序算出。

3．五只猴子一起摘了一堆桃子,因为太累了,它们商量决定,先睡一觉再分.一会其中的一只猴子来了,它见别的猴子没来,便将这堆桃子平均分成5份 ,结果多了一个,就将多的这个吃了,并拿走其中的一份.一会儿,第2只猴子来了,他不知道已经有一个同伴来过,还以为自己是第一个到的呢,于是将地上的桃子堆起来,再一次平均分成5份,发现也多了一个,同样吃了这1个,并拿走其中一份.接着来的第3,第4,第5只猴子都是这样做的.......,
根据上面的条件,问这5只猴子至少摘了多少个桃子?第5只猴子走后还剩下多少个桃子?

4. 用牛顿迭代法求方程x^2 = 45， 要求精确到10E－6。
提示：取x0 = -6; 和 x0 = 6;
f(x)的Newton代法构造方程为：   x(n+1) = xn - (xn*xn - 45) / (2*xn)  

参考答案：
1．#include<stdio.h>
#include<stdlib.h>

int main()
{
    int n;
 
    puts("input n: ");
    scanf("%d", &n);
    
    puts("过程:");
    printf("%d -> ", n);
    
    while (n != 1)
    {
        if (0 == (n&1))
            n = n / 2; //迭代关系式
        else
            n = n * 3 + 1; //迭代关系式

        printf("%d -> ", n);
    }
    printf("\b\b\b\b    \n");//去掉多余的“ -> ” 
    system("pause");
    return 0;       
}

2. 算法分析： 根据题意，阿米巴每3分钟分裂一次，那么从开始的时候将阿米巴放入容器里面，到45分钟后充满容器，需要分裂 45/3=15 次。而"容器最多可以装阿米巴2^20个"，
即阿米巴分裂15次以后得到的个数是2^20 。题目要求我们计算分裂之前的阿米巴数，不妨使用倒推的方法，从第15次分裂之后的2^20个，倒推出第15次分裂之前（即第14次分裂之后）的个数，再进一步倒推出第13次分裂之后、第12次分裂之后、……第1次分裂之前的个数。 设第1次分裂之前的个数为x0 、第1次分裂之后的个数为x1 、第2次分裂之后的个数为x2 、……
第15次分裂之后的个数为x(15)，则有x(14)=x(15)/2,x(13)=x(14)/2,……x(n-1)=x(n)/2 (n >= 1) 因为第15次分裂之后的个数x(15)是已知的，如果定义迭代变量为x ，则可以将上面的倒推公式转换成如下的迭代公式： x=x/2 (x的初值为第15次分裂之后的个数2^20)让这个迭代公式重复执行15次，就可以倒推出第1次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值，我们可以使用一个固定次数的循环来实现对迭代过程的控制。

#include<stdio.h>
#include<math.h>

int main()
{
    int max = pow(2, 20);
    int n = 15;
    int i;
    int s = max;
    
    for (i=1; i<=n; i++)
    {
        s /= 2;
    }
 
    printf("开始的时候往容器内放了%d个阿米巴\n", s);
    
    getchar();
    return 0;       
}

3. 算法分析：先要找一下第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式：
第N只猴   第N只猴前桃子数目
6          s6=x， 即最后剩下的桃子数 
5          s5=s6*5/4+1
4          s4=s5*5/4+1
3          s3=s4*5/4+1
2          s2=s3*5/4+1
1          s1=s2*5/4+1， 即最初的桃子数 
s1即为所求。上面的规律中只要将s1-s5的下标去掉：
s=x
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
很显然，这是一种迭代，所以可以用循环语句加以解决。
综观程序的整体结构，最外是一个循环，因为循环次数不定，可以使用While循环，其结束条件则是找到第一个符合条件的数。为了做出上面while循环的结束条件，还需进一步分析上述规律的特点，要符合题目中的要求，s2-s6五个数必须全部能被4整除，而s1不能被4整除，这个可作为条件。具体实现请参看源程序。

#include <stdio.h>

int main(void)
{
    int x, s;
    int i;
   
    for(x=0; ;x+=4)
    {
        s = x;
        for (i=0; i<5; i++)
        {
            s = s * 5 / 4 + 1;
            if (s % 4)
                break;
        }
        if (i == 4)
            break;
    }
    
    printf("摘了%d个桃子, 剩下%d个桃子\n", s, x);
   
   getchar();
   return 0;   
}   

4. #include<stdio.h>

double F1(double x); //要求解的函数
double F2(double x); //要求解的函数的一阶导数函数  
double Newton(double x0, double e);//通用Newton迭代子程序

int main()
{
    double x0;
    double e = 10E-6;
    
    x0 = -6;
    printf("x = %f\n", Newton(x0, e));
    x0 = 6;
    printf("x = %f\n", Newton(x0, e));
    
    getchar();
    return 0;       
}

double F1(double x) //要求解的函数   
{   
    return  x * x - 45;
}   
    
double F2(double x) //要求解的函数的一阶导数函数   
{   
    return  2 * x;
}   
    
double Newton(double x0, double e)//通用Newton迭代子程序   
{   
    double  x1;   

    do
    {   
        x1 = x0;   
        x0 = x1 - F1(x1) / F2(x1);   
    } while (fabs(x0 - x1) > e);   
          
    return (x0 + x1) * 0.5;  
}

顶...楼主辛苦了......

顶楼主

[em1]   [em1]    [em1]


       顶,楼主弄得很好,菜鸟现在正在学数据结构-----迭代,递归

先顶后看