pascal递归算法.doc

信息学竞赛递归算法一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).递归程序包含递归和递推两个过程，这两个过程又都是根据一个递推公式进行的。一般来说，能够用递归解决的问题应该满足以下三个条件需要解决的问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的问题完全相同，只是在数量规模上不同；递归调用的次数必须是有限的；必须有结束递归的条件（边界条件）来终止递归。例1、楼梯共有N阶台阶，上楼可以以一步上一个台阶，也可以一步上二个台阶。编一个程序计算上N阶台阶，共有多少种走法？ program stair(input,output);var s,n:integer;function f(n:integer):integer; begin if n3 then f:=n else f:=f(n-1)+f(n-2); end;begin readln(n); s:=f(n); writeln(s=,s);end.例2、骨牌铺法有1*n的一个长方形，用一个11、12、13的骨牌铺满方格。例如当n=3时为13的方格。此时用11，12，13的骨牌铺满方格，共有四种铺法。图4.4.3列出了四种铺法。 输入n(0=n=30) 输出 铺法总数分析:这道题可以采用猜测法，从具体的n=1,2,3,.开始，列举出结果，根据列举的部分结果进行猜测，推导出公式。这个猜测推导过程留给读者完成。问题是：这种方法中“猜”和“凑”的成分比较多，容易出错。我们不妨采用组合数学常用的待定系数进行归纳和推导。设推导公式如下：f(n)=a*f(n-1)+b*f(n-2)+c*f(n-3)+d*f(n-4)+.(a,b,c,d.是常系数)即1n的长方形的铺法由全部（a种）1（n-1）的长方形铺法总数加上全部（b种）1*(n-2)的长方形的铺法总数加上全部（c种）1*(n-3)的长方形的铺法总数.注意排除重复情况。（1）将n格分成1格和n-1格，计算f(n-1)的系数a。右端1格的铺法有一种（a）。显然，在一格中只有一种铺法，即f(n-1)的系数a=1。(2)将n格分成2格和n-2格，计算f(n-2)的系数b。右端2格的铺法有两种（b）。由图可见，（b）的铺法包含在(a)的铺法中，而（c）的铺法不同于（a），因此f(n-2)的系数b=1。(3)将n格分成3格和n-3格，计算f(n-3)的系数c。右端3格的铺法有两种（图4.4.5）。由图可见，（d）(e)(f)的铺法都可以归结到1格或2格中去，只有1*3的铺法（g）属于新的，因此f(n-3)的系数c=1。将n格分成n-x格和x格（4=x=5)程序：var n:integer;function f(i:integer):longint;begin if i in1.2then f:=ielse if i=3then f:=4else f:=f(I-1)+f(I-2)+f(I-3);end;begin readln(n); writeln(f(n);end.“铺砖问题”有推广价值。例如某人走n级的楼梯，每步可以走1级、2级或3级，走完n级楼梯共有多少种走法。这个问题的数学意义和解法与“铺砖问题”相同。例3: 划分问题 设s是一个具有n个元素的集合s=a1,a2,an,现将s集合划分成k个满足下列条件的子集合s1,s2，s3。； 1、si空； 2、sisj=空； 3、s1s2s3. sn=s (1=i,j=k,ij)则称s1,s2sn是集合s的一个划分，它相当于把集合s中的n个元素放入k个无标号的盒子中，使得没有一个盒子为空，试确定n个元素的集合放入k个无标号盒的划分数s(n,k)【算法分析】: 例如S1，2，3，4，k3。细心的读者稍加分析后，不难得出S有6 种不同的划分方案，即划分数为6。其方案为 1，234 1，324 1，423 2，314 2，413 3，412 如果对于任意的S集合和k值，就不能凭籍直觉和经验计算划分数和枚举划分方案了。必须总结出一个数学规律:设n个元素a1an放入k个无标号盒的划分数为S(n，k)。在配置过程中， 有两种情况:1.设an是k个子集中的一个子集，于是把a1an-1划分为k1子集有S(n1，k1)个划分数;2.如果an不是k个子集中的一个，即an必与其它的元素构成一个子集。首先把a1，an-1划分成k个子集，这共有S(n1，k)种划分方式。然后 再把an加入到k个子集中的一个子集中去，这有k种加入方式。对于每一种加入方式，都使集合划分为k个子集，因此由乘法原理知，划分数共有 k(n1，k)。 从上面的两种情况分析得出 S(n，k)S(n1，k1)+kS(n1，k) (n1，k1)下面，我们来确定s(n,k)的边界条件: 1.我们不可能把n个元素不放进任何一个集合中去，即(n，0)0;也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即kn时S(n，k)0。 2.把n个元素放进一个集合或把n个元素放进n个集合，方式数显然是1。即 S(n,1)=1 S(n,n)=1显然，通过上述分析可得出划分数S(n，k)的递归关系式: S(n，k)S(n1，k1)+kS(n1，k) (nk，k1) S(n，k)0 (nn)then s:=0 else if(k=1)or(k=n)then s:=1 else s:=s(n-1,k-1)+k*s(n-1,k); end; 相似题：m个相同的球放进n个相同的盒子(可以一个盒子放多个)有多少种不同的放法？ m个相同的球放进n个不相同的盒子(可以一个盒子放多个)有多少种不同的放法？例4、简单的背包问题。设有一个背包，可以放入的重量为s。现有n件物品，重量分别为t1 , t2 , t3 ti tn ，ti (1 in)，均为正整数。从n件物品中挑选若干件，使得放入背包的重量之和正好为s【输入样例】 【输出样例】the number of object:5 number:1 weight:1total weight=10 number:3 weight: 21 6 2 7 5 number:4 weight:7【分析】 尝试构造函数snap(s,n)解决本题，分析情况如下： 、先取最后一个物品tn放入背包中，若tn=s，刚好放入包中， 问题得到解决并输出(n,tn). 、若tns，则不能放入包中，还得继续挑选；若还剩物品(即n1)，问题即为从剩余的n-1件物品中选取若干个，使得他们的重量和等于s，即snap(s,n)snap(s,n-1). 、若tn1）,那么问题即可转换为从剩下的n-1件物品中选取若干件，使得他们的重量和等于包里剩下的可放入重量(s-tn),即：snap(s,n)snap(s,n-1)；而选中的tn还要看snap(s-tn,n-1)是否有解，无解的话说明先取tn不合适，就要放弃tn，在剩余的物品中开始挑选，即有snap(s,n)snap(s,n-1).【参考程序】Const m=10;var t:array1.m of integer; x,y,i:integer; f:boolean;function sng(x:integer):integer; 判断s-tn的三种情况 begin if x0 then sng:=1 else if x=0 then sng:=0 else sng:=-1; end;function snap(s,n:integer):boolean; 判断是否有解begin case sng(s-tn) of 0:begin writeln(number:n:4, weight:,tn:4); snap:=true; end; 1:begin if n1 then if snap(s-tn,n-1)=true then begin writeln(number:n:4, weight:,tn:4); snap:=true; end else snap:=snap(s,n-1) else snap:=false end; -1:if n1 then snap:=snap(s,n-1) else snap:=false end;end;begin writeln(the number of object:);readln（y）； writeln(total weight=); readln(x); for i:=1 to y do read(ti);readln；数据输入 f:=snap(x,y); x:weight, y:number if not(f) then writeln(not found);end.例5、输出n个元素的无重复的全排列。N个元素有n！种不同排列。分析：1个元素直接输出；2个元素有两种排列，如（a b）(b a);3个元素以（a b c）为例，有： a b ca c bb a cb c ac b ac a b分析这些排列，一个简单的算法是：（1）a后随（b c）的所有排列（2）b后随（a c）的所有排列（3）c后随（b a）的所有排列上面（2）是将（1）中的a、b互换位置；上面（3）是将（1）中的a、c互换位置。这里意味着可以用循环的方法来重复执行“交换位置，后随剩余序列的所有的排列”；而对剩余序列可以再使用这个方法，这就成了递归调用，后随的元素没有时，就到了递归的边界。对于n个元素a=(a1a2akan),设过程prem(a,k,n)是求a的第k到n个元素的全排列，设swap(a,k,I)是将a的第k个元素和第i个元素对换，i=k,n。program exp1_7;var a:string;k,n:integer;procedure swap(var a:string;k,i:integer);var t:char;begin t:=ak;ak:=ai;ai:=t;end;procedure perm(a:string;k,n:integer);var i:integer;beginif k=n then writeln(a)else for i:=k to n do begin swap(a,k,i);perm(a,k+1,n); endend;beginreadln(a);n:=length(a);perm(a,1,n);end.例6、 2的幂次方表示任何一个正整数都可以用2的幂次方表示.例如：137=27+23+20。同时约定次方用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)，进一步：7=22+2+20 (21用2表示)；3=2+20；所以最后137可表示为：2(2(2)+2+2(0)+2(2+2(0)+2(0)。又如：1315=210+28+25+2+1；所以1315最后可表示：2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2(0)+2+2(0)输入：正整数(n20000)输出：符合约定的n的0，2表示(在表示中不能有空格)【分析】：递归法2的幂次方由高幂向低幂分解1. 计算最接近n（小于n）的2的次幂e2en0(非第一项)，则输出+；分析次幂ii=0，输出2（0）； 递归边界i=1，输出2；i1，输出2（i的2幂次方表示） 递归准备分解下一项x1x1+1；nn-x；xx div 2；（无论n是否大于等于n）由此得出算法：procedure solve(n：word)； var e，i，x1：byte； x：word；beginx16384；e14； 21420000n do 计算最接近n（小于n）的x=2e begin xx div 2； ee-1 end；while x10； for ie downto 0 do 逐位分解2的幂次i begin if nx then begin 若能分解x=2i if x10 then write(+)； 若当前是中间项 case i of 根据次幂i分解x的2幂次方表示 0： write(2(0)； 1： write(2)； else begin write(2()； solve(i)； write() endelse end；case x1x1+1； nn-x 准备分解下一项x=2i-1 end；then xx div 2 endforend；solve例7、求数字的乘积根。一个正整数的数字的乘积的定义是：这个整数中非零数字的乘积。例如，整数999的数字乘积为9*9*9，即729。729的数字乘积为7*2*9，即126。126的数字乘积为1*2*6，即12。12的数字乘积为1*2，即2。一个正整数的数字乘积根是这样得到的：反复取该整数的数字乘积，直到得到一位数字为止。例如，在上面的例子中数字的乘积根是2。编写一个程序，输入一个正整数（长度不超过200位数字），输出计算其数字乘积根的每一步结果。【分析】：每一步得到的乘积根比它的上一步的位数要小，显然存在递归过程，递归结束的条件是乘积根的位数等于。具体程序编码如下：program ex5_17;var st:string;procedure init;begin writeln(please input:);readln(st);end;procedure make(ss:string);var a,b:array1.200 of integer;i,j,x,code:integer; w:string;begin fillchar(a,sizeof(a),0); for i:=1 to length(ss) do 取每一位数val(ssi,ai,code); fillchar(b,sizeof(b),0); x:=1;b1:=1; for i:=1 to length(ss) do 每一位非0的数相乘 beginfor j:=1 to x do if ai0 then bj:=bj*ai;for j:=1 to x do 处理进位 begin bj+1:=bj+1+bj div 10; bj:=bj mod 10;end;if bx+10 then x:=x+1; end; ss:=; for i:=x downto 1 dobegin str(bi,w);ss:=ss+w;end; writeln(ss); if length(ss)1 then make(ss);end;begin init;输入数据writeln(st);make(st); 递归处理readln;end.例8、输入N个字符，然后以倒序输出（用递归实现）。Program digui (input,output);Const n=8;Type mat=array1.n of char;Var i:integer;a:mat;Procedure print(i:integer);begin If i=n then write(ai) else begin print(i+1);write(ai); end;end;Beginfor i:=1 to n do readln(ai);i:=1; print(i); readln;End.例9、猴子选大王：有n只猴子选大王，先从头到尾至报数，报到的猴子退出，报至尾后，再从尾到头至报数，报到的猴子退出依次类推，当剩下两只猴子时，报的为大王。问若想当大王，应站在什么位置。【分析】：十只猴子编号，则出圈的次序为猴子编号：出圈次序：剩下和时，号猴子报为大王程序如下：program houzi(input,output);type arr=array1.100 of integer;var h:arr;I,j,m,n:integer;procedure num(var a:arr;var n,i:integer;m:integer);var f,k,s:integer;beginif n=3 then begin s:=0;k:=i mod 2;k 为表示从头到尾，k为表示从尾到头 case k of 1: for f:=1 to m do 正向报数if af0 then begin s:=s+1; if s=3 then begin s:=0;n:=n-1;af:=0; end;end; 0: for f:=m downto 1 do反向报数if af0 then begin s:=s+1;if s=3 then begin s:=0;n:=n-1;af:=0;end;end;end; i:=i+1;num(a,n,i,m);递归调用End;End;Begin 主程序Write(input n:);readln(n);For i:=1 to n do hi:=1; 报数前赋初值J:=1;m:=n; num(h,n,j,m); 调用过程numif j mod 2=1 then Begin i:=1;while hI=0 do I:=I+1; Writeln(the leader is:,I); End Else begin I:=m;while hI=0 do I:=I-1; Writeln(the leader is:,I); End;End.例10、计算交点数问题描述： 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数 输入：n（n=20）输出：若干行，列出所有相交方案，其中每一行为一个可能的交点数样例输入 样例输出4 03456(表示在4条直线的情况下，可能有0，3，4，5，6个交点)【问题分析】我们将n条直线排成一个序列，直线2和直线1最多只有一个交点，直线3与直线1和直线2最多有两个交点.，直线n和其他n-1条直线最多有n-1个交点，由此得出n条直线互不平行且无三线共点的最多交点数max=1+2+(n-1)=n(n-1)/2,但本题不这么简单，因为问题问的是：这些直线有多少种不同的交点数？设数组g1.max,gi=0表示交点数i不存在，gi=1表示交点数i存在(0=i=max)容易列举出i=1,2,3的情况如下图所示，我们来分析n=4的情况、四条直线全部平行，无交点，g0=1；、其中三条平行，交点数为(n-1)*1+0=3,g3=1;、其中两条平行，这两条直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线的交点数既可能平行也可能相交，因此交点数据分别为：（n-2）*2+0=4 g4=1 (n-2) *2+1=5 g5=1、四条直线互不平行，交点数为（n-1）*1+3条直线的相交情况： (n-1)*1+0=3 g3=1 (n-1)*1+2=5 g5=1 (n-1)*1+3=6 g6=1即n=4时，有0个，3个，4个，5个，6个不同交点数，所以有5种可能。从上述n=4的分析过程中，我们发现： m条直线的交点方案数=（m-r）条平行线与r条直线交叉的交点数+r条直线本身的交点方案=（m-r）*r+r条之间本身的交点方案数（1=r0 若直线存在，则递归计算所有的交叉情况 then for r:=m downto 1 to try(r,j+r*(m-r) else gj:=1; 否则确定n条直线存在j个交点 end;有了上述递归程序后，我们便可以通过下述方式计算和输出n条直线的交点方案 （1）、计算max=n(n-1)/2 计算最多交点数 （2）、初始化，fillchar(g,size(g),0); (3)、递归求gi:tryn,0; (4)、统计方案数并输出 total:=0; for i:=0 to max do if gi=1 then begin total:=total+1; 输出第total个方案为交点数i； end;例11、 设有2n个运动员要进行网球比赛。现要设计一个满足以下要求的比赛日程表：（1）、每个选手必须与其他n-1个选手各赛一次； （2）、每个选手每天只能参赛一次； （3）、循环赛在n-1天内结束。procedure arrange(k,n:integer); begin if n=2 then begin ak,1:=k;ak,2:=k+1; ak+1,1:=k+1;ak+1,2:=k; end else begin arrange(k,n div 2); arrange(k+n div 2,n div 2); for i:=k to k+(n div 2)-1 do for j:=(n div 2)+1 to n do ai,j:=ai+(n div 2),j-(n div 2); for i:=k+(n div 2) to k+n-1 do for j:=(n div 2+1) to n do ai,j:=ai-(n div 2),j-(n div 2); end; end;例12、计算函数值g(x)= f(x)= 【输入样列】 【输出样列】4 1 2。 f(4)g(3)f(2)g(1)f(0)=0g(1)f(2)g(3)f(4)=6;g(4)f(3)g(2)f(1)g(0)=0f(1)g(2)f(3)g(4)=6.var x,k1,k2:integer;a:longint;function f(x:integer):longint;forward;function g(x:integer):longint;begin if x0 then begin write(g(,x,);g:=f(x-1)+k2;write(g(,x,); end else begin g:=0;write(g(,x,)=,0, );end;end;function f(x:integer):longint;beginif x0 then begin write(f(,x,);f:=g(x-1)+k1;write(f(,x,); end else begin f:=0;write(f(,x,)=,0, );end;end;beginreadln(x,k1,k2);a:=f(x);writeln(=,a);a:=g(x);writeln(=,a);end.树的遍历问题：1已知前序中序求后序procedure Solve(pre,mid:string); var i:integer; begin if (pre=) or (mid=) then exit; i:=pos(pre1,mid); solve(copy(pre,2,i),copy(mid,1,i-1); solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i); post:=post+pre1; 加上根，递归结束后post即为后序遍历 end;2已知中序后序求前序procedure Solve(mid,post:string); var i:integer; begin if (mid=) or (post=) then exit; i:=pos(postlength(post),mid); pre:=pre+postlength(post); 加上根，递归结束后pre即为前序遍历 solve(copy(mid,1,I-1),copy(post,1,I-1); solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i); end;3已知前序后序求中序的一种function ok(s1,s2:string):boolean; var i,l:integer; p:boolean; begin ok:=true; l:=length(s1); for i:=1 to l do begin p:=false; for j:=1 to l do if s1i=s2j then p:=true; if not p then begin ok:=false;exit;end; end; end;procedure solve(pre,post:string); var i:integer; begin if (pre=) or (post=) then exit; i:=0; repeat inc(i); until ok(copy(pre,2,i),copy(post,1,i); solve(copy(pre,2,i),copy(post,1,i); midstr:=midstr+pre1; solve(copy(pre,i+2,length(pre)-i-1),copy(post,i+1,length(post)-i-1); end;递归算法效率分析：举例：fibonacciF(1)=1 f(2)=1F(n)=f(n-1)+f(n-2) (n=3)求解f(n).Function f(n:integer):longint; begin if (n=1)or (n=2) then f:=1 else f:=f(n-1)+f(n-2); end;分析F(5)=f(4)+f(3)求f(4):f(4)=f(3)+f(2)求f(3):f(3)=f(2)+f(1)求f(2):f(2)=1求f(3):f(3)=f(2)+f(1)=1+1=2在这个过程中，在求f(5)时求了一次f(3),而求f(4)时又求了一次f(3),也就是说，f(3)这个子问题在整个求解过程中求了两次。这里同一个子问题在算法中多次遇到，而每次遇到时都要求解一次，这也就是效率低下的原因。尽管采用递归算法的效率比较低，费时和费内存空间，但递归也其长处，它能使一个蕴含递归关系且结构复杂的程序精炼，增加程序的可读性，特别是在难于找到从边界到解的全过程的情况下，如果能把问题推进一步其结构仍维持与原问题的关系，则采用递归算法编程比较合适。练习1、program lx1(input,output);var s,n:integer;function f(n:integer):integer;begin if n=1 then f:=1 else f:=n*n+f(n-1)end;beginwrite(input n:);readln(n);s:=f(n);writeln(f(,n,)=,s)end.该程序的功能是：。当n的值为时，程序的运行结果是：练习2、用递归的方法求Hermite多项式的值hn(x)= 对给定的x和正整数n，求多项式的值。练习3、递归的方法求12+22+32+n2。练习4、用辗转相除法求两个正整数的最大公约数，用递归和非递归的形式编程。练习5、约瑟夫问题：有N个猴子，按顺时针方向围成一圈选大王，从第1号开始报数，按顺序1、2、,数到M号时该猴子退出到圈外，如此报数直到圈内只剩下一个猴子时，则此猴子便是大王。用递归算法完成猴子选大王的程序。练习6、在2*n的一个长方形方格中，用一个12的骨牌铺满方格，例如当n=3时，为23方格，骨牌的铺放方案有三种（图1）。输入n5；输出铺放总数。练习7、已知函数ack的计算公式如下：ack(m,n)= 计算ack(1,2)和ack(2,2)的值。 写出计算Ack(m，n)的递归算法程序。program ackermann;var m,n:longint;function ack(m,n:longint):longint;begin if m=0 then ack:=n+1 else if n=0 then ack:=ack(m-1,1) else ack:=ack(m-1,ack(m,n-1)end;Begin主程序 write(Input m,n:); readln(m,n); writeln(ack(m,n)end. 写出计算Ack(m，n)的非递归算法程序。program ackermann;type stack=array 1.8000,1.2 of longint;var m,n,top:longint; s:stack;begin write(Input m,n:); readln(m,n); s1,1:=m; s1,2:=n; top:=1; while top0 do begin m:=stop,1; n:=stop,2; top:=top-1; if (top=0) and (m=0) then begin writeln(n+1); exit end; if m=0 then stop,2:=n+1 else if n=0 then begin top:=top+1; stop,1:=m-1; stop,2:=1 end else begin top:=top+1; stop,1:=m-1; top:=top+1; stop,1:=m; stop,2:=n-1 end endend.24点：80年代全世界流行一种数字游戏，在中国我们把这种游戏称为“24点”。您作为游戏者将得到4个19之间的自然数作为操作数，而您的任务是对这4个操作数进行适当的算术运算，要求运算结果等于24。您可以使用的运算只有：+，-，*，/，您还可以使用（）来改变运算顺序。注意：所有的中间结果必须是整数，所以一些除法运算是不允许的（例如，（2*2）/4是合法的，2*（2/4）是不合法的）下面我们给出一个游戏的具体例子：若给出的4个操作数是：1、2、3、7，则1+2+3*7=24program work3(input,output);type arr=array 1.4 of integer;var i,result,n,len:integer; d:arr; r:array 1.3,1.4 of integer;procedure print;var i,j:integer;begin for i:=1 to 3 do begin for j:=1 to 3 do if j2 then write(ri,j) else case ri,j of 1:write(