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

第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=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迭代法：方程求根（牛顿迭代法）,#includemath.h#includestdio.hfloatfun(floata,floatb,floatc,floatd)floatx=0.5,y;doy=x;x=x-(a*x+b)*x+c)*x+d)/(3*a*x+2*b)*x+c);while(fabs(x-y)=0.0000001);returnx;,8.1迭代法：方程求根（牛顿迭代法）,main()floata,b,c,d;printf(npleaseinputa,b,c,d:);scanf(%f%f%f%f,8.1迭代法：方程求根（牛顿迭代法）,8.2递推法：斐波那契数列,递推法是利用问题本身所具有的一种递推关系求解问题的方法。斐波那契（Fibonacci）数列：数列1、1、2、3、5，是著名的斐波那契数列，其递推通项公式为：f(0)0;f(1)=1;f(n)=f(n-2)+f(n-1)(n1)，请编写程序输出斐波那契数列的前20项。,8.2递推法：斐波那契数列,#defineN20main()longfN=0,1;inti;for(i=2;iN;i+)fi=fi-2+fi-1;printf(“Fibonacci%d=%ldn”,i,fi);,8.2递推法：斐波那契数列,一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？我们不妨拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对;两个月后，生下一对小兔民数共有两对;三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对;,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递归法：斐波那契数列,一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。,8.3递归法：斐波那契数列,注意：任何一个递归都包含两部分的内容：递归体：递归所进行的操作。递归出口：为了防止递归调用无终止地进行，必须在函数内有终止递归调用的手段。常用的办法是加条件判断，满足某种条件后就不再作递归调用，然后逐层返回。,8.3递归法：斐波那契数列,#defineN20main()inti;for(i=0;i1)returnfib(n-1)+fib(n-2);,8.4穷举法：水仙花数,穷举法是对可能是解的所有候选解进行逐一检验，从中找出满足要求的解。main()inti,j,k,n;printf(waterflowernumberis:);for(n=100;n1000;n+)i=n/100;/*分解出百位*/j=n/10%10;/*分解出十位*/k=n%10;/*分解出个位*/if(i*100+j*10+k=i*i*i+j*j*j+k*k*k)printf(%-5d,n);,回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。1、问题描述从出发点（入口）开始，在给定的空间中，沿可行的路径进行探索，直到达到目标（出口）。在资源勘探中，在战争或游戏中，都会有类似的情景，在给定的空间中，如森林、山洞、沙漠等，搜索特定目标，如出路、人或物等。这类问题都可以归结为迷宫问题。,8.5回朔法：迷宫问题,2、需要解决的问题如何表示给定的空间和可行的路径？如何表示入口和出口？当有多条可行的路径时如何选择？当某条路径在某一点再没有可行之路时如何处理？前两个问题属于数据结构选择和设计，后两个问题涉及算法设计。,8.5回朔法：迷宫问题,3、迷宫表示可以用一个m行n列的二维数组mazemn来表示迷宫空间（或称迷宫地图），并约定：当数组元素mazeij=0，表示通路，mazeij=1，表示不通；入口为左上角maze11，出口为右下角mazemn；,8.5回朔法：迷宫问题,迷宫地图简化为了使探索方向个数一致，可在原来的迷宫地图四周都扩展一个点，即增加两行和两列，并将迷宫四周增加点的值全部置为1，表示是墙，不能通行。这样做使得原迷宫地图中的所有点都成为了中间点，不用再判断当前点是角点、边点、还是中间点，每个点的探索方向均为8个。,8.5回朔法：迷宫问题,1111111111,1111111111,111111,111111,4、增量数组DeltaXY,在某一点（x，y），有8个可以探索的方向：,假设：从正东方向开始，沿顺时针方向依次进行探索，则增量数组DeltaXY为：,8.5回朔法：迷宫问题,5、已解决问题和还未解决的问题（1）二维数组mazem+2n+2来表示迷宫，解决了迷宫地图的存储；（2）一维数组DeltaXY8来记载了8个探索方向的坐标增量，将8个探索方向数字化为0到7，并将向下一点前进的操作统一为当前点的坐标+沿该探索方向的增量，即可得到下一点的坐标；（3）当某点无路可通行时，需要从该点返回到前一点，再从前一点选择下一个方向继续进行探索，即需要知道前一点和前一点当前探索的方向。因此，我们需要保留依次到达的各点的坐标和到达该点的方向；,8.5回朔法：迷宫问题,（4）如何保留到达各点的坐标和到达时的探索方向？1）还需要防止重复到达某点，避免在迷宫中兜死圈子，需要记载已到达过的点。2）可以选用一个数据结构-栈，该栈中元素是由行号x、列号y和到达该点的探索方向d组成的三元组（x，y，d），其中x为到达点的横坐标或行号，y为到达点的纵坐标或列号，d为07中的一个数字，表示到达坐标为（x，y）的点的方向。例如从（2，2）点沿东南方向到达（3，3）点时，在栈中要记录一个三元组（3，3，1）。,8.5回朔法：迷宫问题,（5）如何避免在迷宫中兜死圈子？可以用以下两种方法解决该问题：1）设置一个标志数组markmn，所有元素初始化为0；在探索中，当所探索的点(i，j)对应的markij=0时，才进入该点，并将markij置为1；当所探索的点(i，j)对应的markij=1时，表明已探索过，不需要再进入。2）当到达某点（i，j）后，在迷宫地图的该点坐标上标记特殊值，例如将mazeij置-1，以便区别未到达过的点。,8.5回朔法：迷宫问题,迷宫算法实现intpath(intmazemn,itemDeltaXY8)SeqStacks;datetypetemp;intx,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1;Stack_Push(s，temp);while(!Stack_Empty(s)Stack_Pop(s,temp);x=temp.x;y=temp.y;d=temp.d+1;while(d8)i=x+DeltaXYd.x;j=y+DeltaXYd.y;if(mazeij=0)temp=x,y,d;Stack_Push(s,temp);x=i;y=j;mazexy=-1;/*标记该点已到过*/if(x=m/迷宫无路,数据结构有两大用途：一是用于存放要处理的数据，如迷宫地图；二是用于实现算法策略，如迷宫例子中探索方向增量数组、回溯的栈、避免重复走的标志数组或特殊标记）,6、迷宫问题小结使用了哪些数据结构？他们的作用？存放迷宫的地图maze及边角点的处理方向数组DeltaXY：8个方向回溯的栈s：三元组（x，y，d）避免重复走：走过的点计为特殊值-1,8.5回朔法：迷宫问题,8.6贪心法：装箱问题,贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。,8.6贪心法：装箱问题,设有编号为0，1，n-1的n种物品，体积分别为V0，V1，Vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V，即对于0in，有0ViV。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。设有6种物品，它们的体积分别为：60，45，35，20，20，20单位体积，箱子的容量为100个单位体积。按照贪心法的思想，需要3只箱子，各箱子所装物品分别为：第1只箱子装物品1，3；第2只箱子装物品2，4，5；第3只箱子装物品6。而最优解为2只箱子，分别装物品1，4，5和2，3，6。,8.7分治法：,在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础。,8.8动态规划：最优路径,动态规划法是20世纪50年代由贝尔曼（R.Bellman）等人提出，用来解决多阶段决策过程问题的一种最优化方法。所谓多阶段决策过程，就是把研究问题分成若干个相互联系的阶段，由每个阶段都作出决策，从而使整个过程达到最优化。实际上，动态规划法就是分多阶段进行决策，其基本思路是：按时空特点将复杂问题划分为相互联系的若干个阶段，在选定系统行进方向之后，逆着这个行进方向，从终点向始点计算，逐次对每个阶段寻找某种决策，使整个过程达到最优，故又称为逆序决策过程。,8.8动态规划：最优路径,如下图所示，从结点1要铺设一条管道到结点16，中间必须经过5个中间站，第一站可以在2和3两个结点中任选一个，类似地，第二、三、四、五可供选择的结点分别是：4，5，6，7，8，9，10，11，12，13，14，15。连接结点间管道的距离（或造价）用连线上的数字表示，要求选一条从1到16的铺管线路，使总距离最短（或总造价最小）。,8.8动态规划：最优路径,8.8动态规划：最优路径,设f(x)表示由x（x=1，2，315）到16的最短距离，则f(14)=4，f(15)=3。f(11)=mind(11,14)+f(14),d(11,15)+f(15)=7f(12)=mind(12,14)+f(14),d(12,15)+f(15)=5f(13)=mind(13,14)+f(14),d(13,15)+f(15)=9f(8)=mind(8,11)+f(11),d(8,12)+f(12)=7f(9)=mind(9,12)+f(12),d(9,13)+f(13)=6f(10)=mind(10,12)+f(12),d(10,13)+f(13)=8,8.8动态规划：最优路径,前面求得f(8)=7,f(9)=6,f(10)=8,则:f(4)=mind(4,8)+f(8),d