第8章 程序设计基本算法和应用

《第8章 程序设计基本算法和应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第8章程序设计基本算法与应用8.1迭代法8.2递推法8.3递归法8.4穷举法8.5回朔法8.6贪心法8.7分治法8.8动态规划8.1迭代法：方程求根（牛顿迭代法）迭代法是一种不断用变量的旧值递推新值的过程。运用迭代法的基本步骤：（1）确定迭代的变量（2）建立迭代关系（3）对迭代过程进行控制设r是f(x)=0的根，选取x0作为r初始近似值，过点（x0,f(x0)）做曲线y=f(x)的切线L，L的方程为y=f(x0)+f'(x0)(x-x0)，求出L与x轴交点的横坐标x1=x0-f(x0)/f'(x0)，称x1为r的一次近似值。过点（x1,f(x1)）做曲线y

2、=f(x)的切线，并求该切线与x轴交点的横坐标x2=x1-f(x1)/f'(x1)，称x2为r的二次近似值。重复以上过程，得r的近似值序列，其中x(n+1)=x(n)－f(x(n))/f'(x(n))，称为r的n+1次近似值，上式称为牛顿迭代公式。8.1迭代法：方程求根（牛顿迭代法）#include"math.h"#include"stdio.h"floatfun(floata,floatb,floatc,floatd){floatx=0.5,y;do{y=x;x=x-(((a*x+b)*x+c)*x+d)/((3*a*x+2*b)*x+c);}while

3、(fabs(x-y)>=0.0000001);returnx;}8.1迭代法：方程求根（牛顿迭代法）main(){floata,b,c,d;printf("pleaseinputa,b,c,d:");scanf("%f%f%f%f",&a,&b,&c,&d);printf("x=%10.7f",fun(a,b,c,d));}8.1迭代法：方程求根（牛顿迭代法）8.2递推法：斐波那契数列递推法是利用问题本身所具有的一种递推关系求解问题的方法。斐波那契（Fibonacci）数列：数列1、1、2、3、5……，是著名的斐波那契数列，其递推通项公式为：f(0

4、)＝0;f(1)=1;f(n)=f(n-2)+f(n-1)(n>1)，请编写程序输出斐波那契数列的前20项。8.2递推法：斐波那契数列#defineN20main(){longf[N]={0,1};inti;for(i=2;i

5、子没有繁殖能力，所以还是一对;两个月后，生下一对小兔民数共有两对;三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对;8.2递推法：斐波那契数列依次类推可以列出下表：所经过月数：0、1、2、3、4、5、6、7、8、9、10、11、12兔子对数：1、1、2、3、5、8、13、21、34、55、89、144、233表中数字1，1，2，3，5，8－－－构成了一个序列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。8.3递归法：斐波那契数列一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问

6、题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。8.3递归法：斐波那契数列注意：任何一个递归都包含两部分的内容：★递归体：递归所进行的操作。★递归出口：为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。8.3递归法：斐波那契数列#defineN20main(){inti;f

7、or(i=0;i1)returnfib(n-1)+fib(n-2);}8.4穷举法：水仙花数穷举法是对可能是解的所有候选解进行逐一检验，从中找出满足要求的解。main(){inti,j,k,n;printf("'waterflower'numberis:");for(n=100;n<1000;n++){i=n/100;/*分解出百位*/j=n/10%10;/*分解出十位*/k

8、=n%10;/*分解出个位*/if(i*100+j*10+k==i