搜索
第六章程序设计与基本算法学习计算机语言不是学习的最终目的。语言是描述的工具，如何灵活地运用语言工具，设计和编写能解决实际问题的程序，算法是程序设计的基础。算法的作用是什么呢？著名数学家高斯（GAUSS）从小就勤于思索。1785年，刚上小学二年级的小高斯，对老师出的计算题S=1+2+3+…+99+100，第一个举手报告S的结果是5050。班上的同学都采用依次逐个相加的“算法”，要相加99次;而小高斯则采用首尾归并，得出S=（1+100）*50的“算法”，只需加一次和乘一次，大大提高了效率。可见，算法在处理问题中的重要性。学习计算机编程，离不开基本算法。刚开始学习程序设计时，就应注重学习基本算法。第一节递推与递归算法递推和递归是编程中常用的基本算法。在前面的解题中已经用到了这两种方法，下面对这两种算法基本应用进行详细研究讨论。一、递推递推算法是一种用若干步可重复的简单运算（规律）来描述复杂问题的方法。[例1]植树节那天，有五位参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10棵。到底第一位同学植了多少棵树？解：设第一位同学植树的棵数为a1，欲求a1，需从第五位同学植树的棵数a5入手，根据“多两棵”这个规律，按照一定顺序逐步进行推算：①a5=10;②a4=a5+2=12;③a3=a4+2=14;④a2=a3+2=16;⑤a1=a2+2=18;Pascal程序：ProgramExam1;Vari,a:byte;begina:=10;{以第五位同学的棵数为递推的起始值}fori:=1to4do{还有4人，递推计算4次}a:=a+2;{递推运算规律}writeln(’TheNumis’,a);readlnend.本程序的递推运算可用如下图示描述：递推算法以初始{起点}值为基础，用相同的运算规律，逐次重复运算，直至运算结束。这种从“起点”重复相同的方法直至到达一定“边界”，犹如单向运动，用循环可以实现。递推的本质是按规律逐次推出（计算）下一步的结果。二、递归递归算法是把处理问题的方法定义成与原问题处理方法相同的过程，在处理问题的过程中又调用自身定义的函数或过程。仍用上例的计算植树棵数问题来说明递归算法：解：把原问题求第一位同学在植树棵数a1，转化为a1=a2+2;即求a2；而求a2又转化为a2=a3+2;a3=a4+2;a4=a5+2;逐层转化为求a2,a3,a4,a5且都采用与求a1相同的方法；最后的a5为已知,则用a5=10返回到上一层并代入计算出a4；又用a4的值代入上一层去求a3;...,如此,直到求出a1。因此：其中求ax+1又采用求ax的方法。所以:①定义一个处理问题的过程Num(x)：如果X5就递归调用过程Num(x+1);②当递归调用到达一定条件(X=5)，就直接执行a:=10，再执行后继语句，遇End返回到调用本过程的地方，将带回的计算结果(值)参与此处的后继语句进行运算（a:=a+2）;③最后返回到开头的原问题，此时所得到的运算结果就是原问题Num(1)的答案。Pascal程序：ProgramExam1_1;Vara:byte;ProcedureNum(x:integer);{过程Num(x)求x的棵数｝beginifx=5thena:=10elsebeginNum(x+1);｛递归调用过程Num(x+1)｝a:=a+2{求(x+1)的棵数｝endend;beginNum(1);｛主程序调用Num(1)求第1个人的棵数｝writeln(’TheNumis’,a);readlnend.程序中的递归过程图解如下：参照图示，递归方法说明如下：①调用原问题的处理过程时，调用程序应给出具体的过程形参值（数据）;②在处理子问题中，如果又调用原问题的处理过程，但形参值应是不断改变的量(表达式）;③每递归调用一次自身过程，系统就打开一“层”与自身相同的程序系列;④由于调用参数不断改变，将使条件满足（达到一定边界），此时就是最后一“层”，不需再调用（打开新层），而是往下执行后继语句，给出边界值，遇到本过程的END，就返回到上“层”调用此过程的地方并继续往下执行;⑤整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。[例2]用递归算法求Xn。解：把Xn分解成:X0=1(n=0)X1=X*X0(n=1)X2=X*X1(n1)X3=X*X2(n1)……(n1)Xn=X*Xn-1(n1)因此将Xn转化为：其中求Xn-1又用求Xn的方法进行求解。①定义过程xn(x,n:integer)求Xn;如果n1则递归调用xn(x,n-1)求Xn—1;②当递归调用到达n=0，就执行tt:=1,然后执行本“层”的后继语句;③遇到过程的END就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后续语句tt:=tt*x;④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序，输出tt的值。Pascal程序：ProgramExam2;Vartt,a,b:integer;Procedurexn(x,n:integer);｛过程xn(x,n)求xn｝beginifn=0thentt:=1elsebeginxn(x,n-1);｛递归调用过xn(x,n-1)求xn-1｝tt:=tt*xend;end;beginwrite(’inputx,n:’);readln(a,b);｛输入a,b｝xn(a,b);｛主程序调用过程xn(a,b)求ab｝writeln(a,’^’,b,’=‘,tt);readlnend.递归算法，常常是把解决原问题按顺序逐次调用同一“子程序”(过程)去处理，最后一次调用得到已知数据，执行完该次调用过程的处理，将结果带回，按“先进后出”原则，依次计算返回。如果处理问题的结果只需返回一个确定的计算值，可定义成递归函数。[例3]用递归函数求x!解：根据数学中的定义把求x!定义为求x*(x-1)!,其中求(x-1)!仍采用求x!的方法，需要定义一个求a！的过程或函数，逐级调用此过程或函数，即：(x-1)!=(x-1)*(x-2)!;(x-2)!=(x-2)*(x-3)!;……直到x=0时给出0!=1，才开始逐级返回并计算各值。①定义递归函数：fac(a:integer):integer;如果a=0，则fac:=1;如果a0，则调用函数fac:=fac(a-1)*a;②返回主程序，打印fac(x)的结果。Pascal程序：ProgramExam3;Varx:integer;functionfac(a:integer):integer;｛函数fac(a)求a!｝beginifa=0thenfac:=1elsefac:=fac(a-1)*a｛函数fac(a-1)递归求(a-1)!｝end;beginwrite(’inputx’);readln(x);writeln(x,’!=’,fac(x));｛主程序调用fac(x)求x!｝readlnend.递归算法表现在处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。[例4]用递归算求自然数A，B的最大公约数。解：求最大公约数的方法有许多种，若用欧几里德发明的辗转相除方法如下：①定义求X除以Y的余数的过程;②如果余数不为0，则让X=Y，Y=余数，重复步骤①，即调用过程;③如果余数为0，则终止调用过程;④输出此时的Y值。Pascal程序：ProgramExam4;Vara,b,d:integer;ProcedureGdd(x,y:nteger);{过程}beginifxmody=0thend:=yelseGdd(y,xmody){递归调用过程}end;beginwrite(’inputa,b=’);readln(a,b);Gdd(a,b);writeln(’(’,a,’,’,b,’)=’,d);readlnend.简单地说，递归算法的本质就是自己调用自己，用调用自己的方法去处理问题，可使解决问题变得简洁明了。按正常情况有几次调用，就有几次返回。但有些程序可以只进行递归处理，不一定要返回时才进行所需要的处理。[例5]移梵塔。有三根柱A，B，C在柱A上有N块盘片，所有盘片都是大的在下面，小片能放在大片上面。现要将A上的N块片移到C柱上，每次只能移动一片，而且在同一根柱子上必须保持上面的盘片比下面的盘片小，请输出移动方法。解：先考虑简单情形。如果N=3，则具体移动步骤为：假设把第3步，第4步，第6步抽出来就相当于N=2的情况（把上面2片捆在一起，视为一片）：所以可按“N=2”的移动步骤设计：①如果N=0，则退出，即结束程序;否则继续往下执行;②用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程sub(n-1,a,b,c);③将A柱上剩下的一片直接移到C柱上;④用A柱作为协助过渡，将B柱上的（N-1）移到C柱上，调用过程sub(n-1,b,c,a)。Pascal程序：ProgramExam65;Varx,y,z:char;N,k:integer;Proceduresub(n:integer;a,c,b:char);beginifn=0thenexit;sub(n-1,a,b,c);inc(k);writeln(k,’:from’,a,’--＞’,c);sub(n-1,b,c,a);end;beginwrite(’n=’;readln(n);k:=0;x:=’A’;y:=’B’;Z:=’C’;sub(n,x,z,y);readlnend.程序定义了把n片从A柱移到C柱的过程sub(n,a,c,b)，这个过程把移动分为以下三步来进行：①先调用过程sub(n-1,a,b,c)，把(n-1)片从A柱移到B柱,C柱作为过渡柱;②直接执行writeln(a,’--＞’,c），把A柱上剩下的一片直接移到C柱上，;③调用sub(n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。对于B柱上的(n-1)片如何移到，仍然调用上述的三步。只是把(n-1)当成了n，每调用一次，要移到目标柱上的片数N就减少了一片，直至减少到n=0时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。习题6.11.过沙漠。希望一辆吉普车以最少的耗油跨越1000km的沙漠。已知该车总装油量500升，耗油率为1升/km，必须利用吉普车自己沿途建立临时加油站，逐步前进。问一共要多少油才能以最少的耗油越过沙漠？2.楼梯有N级台阶，上楼可以一步上一阶，也可以一步上二阶。编一递归程序，计算共有多少种不同走法？提示：如N级楼梯有S(N)种不同走法，则有：S(N)=S(N-2)+S(N-1)3.阿克曼(Ackmann)函数A(x,y)中，x,y定义域是非负整数，函数值定义为：A(x,y)=y+1(x=0)A(x,0)=A(x-1,1)(x0,y=0)A(x,y)=A(x-1,A(x,y-1))(x,y0)设计一个递归程序。4.某人写了N封信和N个信封，结果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。可用下面公式：Dn=(n—1)(Dn—１+Dn—２)写出递归程序。第二节回溯算法在一些问题求解进程中，有时发现所选用的试探性操作不是最佳选择，需退回一步，另选一种操作进行试探，这就是回溯算法。例[6.6]中国象棋半张棋盘如下，马自左下角往右上角跳。现规定只许往右跳，不许往左跳。比如下图所示为一种跳行路线。编程输出所有的跳行路线，打印格式如下：