递归基础练习题

1、递归基础练习题1.  求1+2+3+n的值2.  求1*2*3*n的值3. 数的全排列问题。将n个数字1，2，n的所有排列按字典顺序枚举出来  2 3 1  2 1 3  3 1 2  3 2 14. 数的组合问题。从1,2,n中取出m个数，将所有组合按照字典顺序列出。如n=3,m=2时，输出：1 21 32 39.  求两个数

2、的最大公约数。10.  求两个数的最小公倍数。5. 小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？8.  著名的菲波拉契(Fibonacci)数列，其第一项为1，第二项为1，从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。15.  梯有N阶，上楼可以一步上一阶，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。6. 有雌雄一对兔子

3、，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？7.  一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？11.  输入一个数，求这个数的各位数字之和。12.  角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。如：输入22，输出 22  11  34

4、60; 17  52  26  13  40  20  10  5  16  8  4  2  1     STEP=1613.  将十进制转换为二进制。14.  计算Mmax(a,b,c)/max(a+b,b,c)*max(a,b,b+c),其中a，b，c由

5、键盘输入。16.  某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况?17.  给出一棵二叉树的中序与后序排列。求出它的先序排列。18.  求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。19.  已知一个一维数组A1.N。N<50 又已知一整数M。如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。20.  要求找出具有下列性质的数的个数(包含输入的自然数n)：先输入一个自然数n(n<=500),然后对此

6、自然数按照如下方法进行处理:. 不作任何处理;. 在它的左边加上一个自然数,但该自然数不能超过原数首位数字的一半;. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.样例:  输入:  6满足条件的数为   6                16       &

7、#160;        26               126                36         

8、      136输出:  621.  自然数的拆分问题。给定自然数n,将其拆分成若干自然数的和。输出所有解，每组解中数字按从小到大排列。相同数字的不同排列算一组解。如：3=1+1+13=1+23=322.  用递归的方法求N个数中最大的数及其位置。23.  写出折半查找的递归算法。24.  快速排序法。思考题 :1、数学宝塔，从最顶上走到最底层，每次只能走到下一层的左边或右边的数字，求出使所走到的所有数字之和为60的途径。7

9、466936371253285947 326418563397684152573578422、 汉诺塔问题：设有三个塔座，依次命名为x,y,z。有z个直径不同的圆盘，由小到大依次编号为1、2、，n。开始时，它们全部按递减的次序插在塔座上。现要求按下列规则把n个圆盘按次序插放在z塔座上。（1）、每次只能移动一个圆盘；（2）、圆盘可以从任一个塔座上移到另一个塔座上；（3）、任何时刻都不能把一个较大的圆盘压在较小的圆盘上。典型例题: 1.设有n个数已经按从大到小的顺序排列，现在从键盘上输入n，判断它是否在这n 个数中，如果存在则输出“yes”否则输出“no”。

10、   Program lx4;   Const n=30;   Var a:array1.nof integer;       F,r,x,k:integer;   Program search(x,top,bot:integer);     Var  mid:integer; 

11、         Begin             if top<=bot then               Begin      

12、60;          Mid=(top + bot) div 2;                 If x =amid then writeln(x:5,mid:5,yes)      

13、;            else  If x<amid then search(x,top,mid-1)                          

14、60;          Else search(x,mid+1,r);               End            else Writeln(x:5,no);   

15、       End;  Begin      Writeln(input n ge shu);     For k:=1 to n do read(ak);     Read(x);     F:=1;r:=n;

16、60;    Search(x,f,r);  End.2.hanoi塔问题。  递归：procedure Hanoi(n:integer;x,y,z:char);          Begin            If n=1 then writeln(x,

17、-n,-,z)                   Else  begin                          &#

18、160;Hanoi(n-1,x,z,y);                           Writeln(x,-,n,-,z);                &#

19、160;          Hanoi(n-1,y,x,z)                         End;          End;&#

20、160;       Begin           Write(input n:);           Read(n);           Hanoi(n,A,B,C) &#

21、160;      End.3.有n个硬币（n为偶数）正面朝上排成一排，每次将n-1个硬币翻成朝上为止。编程让计算机把翻硬币的最简过程及翻币次数打印出来（用*代表正面，用0代表反面）。基本形式：D1=0;d2=1递归式：dn= (n-1)*( dn-1 + dn-2)var n:integer;function d(n:integer):longint;begincase n of1:d:=0;2:d:=1;else d:=(n-1)*(d(n-

22、1)+d(n-2);end;end;beginrepeatwrite('n=');readln(n);if n<=0 then writeln('Once more!')until n>0;writeln('d=',d(n);readln;end.4.有一对雌雄兔子，假定两个月便可以繁殖雌雄各一对兔子。问n个月后共有多少对兔子？递归的三要素：递归的形式：Tn= Tn-1+ Tn-2基本：T1=1，T2=1结束条件：n个月program rabbit;var

23、 n:integer;function fa(n:integer):integer;beginif n<3 then fa:=1else fa:=fa(n-1)+fa(n-2);end;beginwrite('n=');readln(n);writeln('The number of the rabbits:',fa(n);end.5.梯有N阶，上楼可以一步上一价，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。递归的形式：sn=sn-1+sn-2基

24、本式子：s1=1;s2=2program upstairs;var n:integer;function s(n:integer):longint;beginif (n=1)or(n=2) then s:=nelse s:=s(n-1)+s(n-2);end;beginrepeatwrite('N=');readln(n);until n>0;writeln('s=',s(n);readln;end.6.斐波那切数列  递归：var m,p:int

25、eger;        Function fib(n:integer):integer;           Begin               If n=0 then fib:=0  

26、0;                  Else if n=1 then fib:=1                        

27、60;        Else fib:=fib(n-1)+fib(n-2);           End;        Begin           Read(m);   &

28、#160;       P:=fib(m);           Writeln(fib(,mm)=,p)         End.7.设有2n个运动员要进行网球比赛。现要设计一个满足以下要求的比赛日程表：（1）、每个选手必须与其他n-1个选手各赛一次；（2）、每个选手每天只能参赛一次；（3）、循环赛在n-1天内结束。progr

29、am match;const k=3;n=8;vars:array1.n,1.n of integer;i,j,p:integer;ju:boolean;procedure copy1(be,en:integer;jug:boolean;q:integer);var m,t,ban:integer;beginif jug thenbeginif be=1 thenbegin if sen,en=0 thenbegin copy1(be,en di

30、v 2,true,q div 2);copy1(en div 2)+1,en,false,q div 2);end;for m:=1 to en dofor t:=1 to en dosm+q,t+q:=sm,tendelse begin if sbe+q-1,q=0 thenbegin copy1(be,be+(q div 2)-1,true,q div 

31、2);copy1(be+(q div 2),en,false,q div 2)end;for m:=be to en dofor t:=1 to q dosm+q,t+q:=sm,tendendelse beginif sbe,q=0 thenbegin copy1(be,be+(q div 2)-1,true,q div 2);copy1(be+(q div 2),en,fa

32、lse,q div 2)end;for m:=be to en dofor t:=1 to q dosm-q,t+q:=sm,tendend;beginp:=8;for i:=1 to n dofor j:=1 to n dosi,j:=0;for i:=1 to n dobeginsi,1:=i;if odd(i) then si+1,2:=si

33、,1else si-1,2:=si,1;end;copy1(1,n div 2,true,p div 2);copy1(n div 2)+1,n,false,p div 2);for i:=1 to n dobeginfor j:=1 to n dowrite(si,j,' ');writeln;end;end.以下是USACO contest上的题目，全是递归-*  &

34、#160;                        BRONZE PROBLEMS*                     

35、0;    三道题目，从11到13*Problem 11: 谷仓的安保 Traditional, 2005Farmer John给谷仓安装了一个新的安全系统，并且要给牛群中的每一个奶牛安排一个有效的密码。一个有效的密码由L(3 <= L <= 15)个小写字母(来自传统的拉丁字母集'a'.'z')组成，至少有一个元音('a', 'e', 'i', 

36、;'o', 或者 'u')，至少两个辅音(除去元音以外的音节)，并且有按字母表顺序出现的字母(例如，'abc'是有效的，而'bac'不是) 。给定一个期望长度L和C个小写字母，写一个程序，打印出所有的长度为L、能由这些字母组成的有效密码。密码必须按字母表顺序打印出来，一行一个。题目名称: passwd输入格式:* 第一行: 两个由空格分开的整数，L和C* 第二行: C个空格分开的小写字母，密码是由这个字母集中的字母来构建的。输入样例 (文件&

37、#160;passwd.in):4 6a t c i s w输入详细说明:由从给定的六个字母中选择的、长度为4的密码。输出格式:* 第一至?行: 每一个输出行包括一个长度为L个字符的密码(没有空格)。输出行必须按照字母顺序排列。输出样例 (文件 passwd.out):acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistw*Problem 12: "跳房子" Hal Burch, 2005奶牛们按不太传统的方式玩起了小孩子们玩的"跳房子"游戏。奶牛们创造了一个5x5的、由与x,y轴平行的数字组成的直线型网格，而不是用来在里面跳的、线性排列的、带数字的方格。然后他们熟练地在网格中的数字中跳：向前跳、向后跳、向左跳、向右跳(从不斜过来跳)，跳到网格中的另一个数字上。他们再这样跳啊跳(按相同规则)，跳到另外一个数字上(可能是已经跳过的数字)。一共在网格内跳过五次后，他们的跳跃构建了一个六位整数(可能以0开头，例如000201)。求出所有能被这样创造出来的不同整