C语言递归练习附答案.docx

1、C语言递归练习附答案dic递归基础练习题：1.求1+2+3+n的值int sum(int a,int b) if(b=a) return a; return a+sum(a+1,b); 2.求1*2*3*n的值cheng(int begin,int end) if(begin=end) return begin; return begin * cheng(begin+1,end);3.数的全排列问题。将n个数字1，2，n的所有排列按字典顺序枚举出猴2312133123214.数的组合问题。从1,2,n中取出m个数，将所有组合按照字典顺序列出。如n=3,m=2时，输出：1213235.小猴子第一

2、天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？fruit(int begin,int times) if(times=10) return begin; return fruit(begin+1)*2,times+1);6.有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？7.一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？

3、经过每个村子卖出多少只鸭子？duck(int begin,int times) if(times=7) return begin; return duck(begin+1)*2,times+1);8.著名的菲波拉契(Fibonacci)数列，其第一项为0，第二项为1，从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。int fbi(int i) if(i2) if(i = 0) return 0; else return 1; return fbi(i-1) +fbi(i-2);9.求两个数的最大公约数。fgongyue(int m,int n)/m要大于n，前面可以交换让它实现

4、 if(n = 0) return m; fgongyue(n,m%n);10.求两个数的最小公倍数。最小公倍数等于个数之积乘最好公约数m*n/fgongyue(m,n)11.输入一个数，求这个数的各位数字之和。add_every_num(int num) if(num10) return num; return num%10+add_every_num(num/10);12.角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。如：输入22，输出22113417522613402010516842

5、1STEP=16#include stdafx.h#include stdio.hint i = 1;int fc(int n) if(n = 1) printf(%d,n); return i; else if(n%2 = 0) printf(%dt,n); fc(n/2); i+; else printf(%dt,n); fc(n*3+1); i+; int main(int argc, char* argv) int n,step; printf(Please input the num:); scanf(%d,&n); step = fc(n); printf(nStep = %dn,

6、step); return 0;13.将十进制转换为二进制。#include stdafx.h#include stdio.hint fc(int num) if(num = 1) printf(%d,num); return 0; fc(num/2); printf(%d,num%2); int main(int argc, char* argv) int num; printf(please input the num:); scanf(%d,&num); fc(num); printf(n); return 0;14.计算Mmax(a,b,c)/max(a+b,b,c)*max(a,b,

7、b+c),其中a，b，c由键盘输入。skip15.梯有N阶，上楼可以一步上一阶，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。return 1+(fc(n-1)+fc(n-2)16.某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况?17.给出一棵二叉树的中序与后序排列。求出它的先序排列。18.求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。19.已知一个一维数组A1.N。N50又已知一整数M。如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。20.要求找出具有下列性质的数的个数(包含输入的自然数n)：先输入一个自然

8、数n(n=500),然后对此自然数按照如下方法进行处理:.不作任何处理;.在它的左边加上一个自然数,但该自然数不能超过原数首位数字的一半;.加上数后,继续按此规则进行处理,直到不能再加自然数为止.样例:输入:6满足条件的数为6162612636136输出:621.自然数的拆分问题。给定自然数n,将其拆分成若干自然数的和。输出所有解，每组解中数字按从小到大排列。相同数字的不同排列算一组解。如：3=1+1+13=1+23=322.用递归的方法求N个数中最大的数及其位置。23.写出折半查找的递归算法。24.快速排序法。思考题:1、数学宝塔，从最顶上走到最底层，每次只能走到下一层的左边或右边的数字，求

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

10、ramlx4;Constn=30;Vara:array1.nofinteger;F,r,x,k:integer;Programsearch(x,top,bot:integer);Varmid:integer;Beginiftop=botthenBeginMid=(top+bot)div2;Ifx=amidthenwriteln(x:5,mid:5,yes)elseIfxamidthensearch(x,top,mid-1)Elsesearch(x,mid+1,r);EndelseWriteln(x:5,no);End;BeginWriteln(inputngeshu);Fork:=1tondo

11、read(ak);Read(x);F:=1;r:=n;Search(x,f,r);End.2.hanoi塔问题。递归：procedureHanoi(n:integer;x,y,z:char);BeginIfn=1thenwriteln(x,-n,-,z)ElsebeginHanoi(n-1,x,z,y);Writeln(x,-,n,-,z);Hanoi(n-1,y,x,z)End;End;BeginWrite(inputn:);Read(n);Hanoi(n,A,B,C)End.3.有n个硬币（n为偶数）正面朝上排成一排，每次将n-1个硬币翻成朝上为止。编程让计算机把翻硬币的最简过程及翻币次数

12、打印出来（用*代表正面，用0代表反面）。基本形式：D1=0;d2=1递归式：dn=(n-1)*(dn-1+dn-2)varn:integer;functiond(n:integer):longint;begincasenof1:d:=0;2:d:=1;elsed:=(n-1)*(d(n-1)+d(n-2);end;end;beginrepeatwrite(n=);readln(n);ifn0;writeln(d=,d(n);readln;end.4.有一对雌雄兔子，假定两个月便可以繁殖雌雄各一对兔子。问n各月后共有多少对兔子？递归的三要素：递归的形式：Tn=Tn-1+Tn-2基本：T1=1，T

13、2=1结束条件：n个月programrabbit;varn:integer;functionfa(n:integer):integer;beginifn0;writeln(s=,s(n);readln;end.6.斐波那切数列递归：varm,p:integer;Functionfib(n:integer):integer;BeginIfn=0thenfib:=0Elseifn=1thenfib:=1Elsefib:=fib(n-1)+fib(n-2);End;BeginRead(m);P:=fib(m);Writeln(fib(,mm)=,p)End.7.设有2n个运动员要进行网球比赛。现要设

14、计一个满足以下要求的比赛日程表：（1）、每个选手必须与其他n-1个选手各赛一次；（2）、每个选手每天只能参赛一次；（3）、循环赛在n-1天内结束。programmatch;constk=3;n=8;vars:array1.n,1.nofinteger;i,j,p:integer;ju:boolean;procedurecopy1(be,en:integer;jug:boolean;q:integer);varm,t,ban:integer;beginifjugthenbeginifbe=1thenbeginifsen,en=0thenbegincopy1(be,endiv2,true,qdiv

15、2);copy1(endiv2)+1,en,false,qdiv2);end;form:=1toendofort:=1toendosm+q,t+q:=sm,tendelsebeginifsbe+q-1,q=0thenbegincopy1(be,be+(qdiv2)-1,true,qdiv2);copy1(be+(qdiv2),en,false,qdiv2)end;form:=betoendofort:=1toqdosm+q,t+q:=sm,tendendelsebeginifsbe,q=0thenbegincopy1(be,be+(qdiv2)-1,true,qdiv2);copy1(be+(

16、qdiv2),en,false,qdiv2)end;form:=betoendofort:=1toqdosm-q,t+q:=sm,tendend;beginp:=8;fori:=1tondoforj:=1tondosi,j:=0;fori:=1tondobeginsi,1:=i;ifodd(i)thensi+1,2:=si,1elsesi-1,2:=si,1;end;copy1(1,ndiv2,true,pdiv2);copy1(ndiv2)+1,n,false,pdiv2);fori:=1tondobeginforj:=1tondowrite(si,j,);writeln;end;end.以

17、下是USACOcontest上的题目，全是递归-*BRONZEPROBLEMS*三道题目，从11到13*Problem11:谷仓的安保Traditional,2005FarmerJohn给谷仓安装了一个新的安全系统，并且要给牛群中的每一个奶牛安排一个有效的密码。一个有效的密码由L(3=L=15)个小写字母(来自传统的拉丁字母集a.z)组成，至少有一个元音(a,e,i,o,或者u)，至少两个辅音(除去元音以外的音节)，并且有按字母表顺序出现的字母(例如，abc是有效的，而bac不是)。给定一个期望长度L和C个小写字母，写一个程序，打印出所有的长度为L、能由这些字母组成的有效密码。密码必须按字母表

18、顺序打印出来，一行一个。题目名称:passwd输入格式:*第一行:两个由空格分开的整数，L和C*第二行:C个空格分开的小写字母，密码是由这个字母集中的字母来构建的。输入样例(文件passwd.in):46atcisw输入详细说明:由从给定的六个字母中选择的、长度为4的密码。输出格式:*第一至?行:每一个输出行包括一个长度为L个字符的密码(没有空格)。输出行必须按照字母顺序排列。输出样例(文件passwd.out):acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistw*Problem12:跳房子HalBurch,2005奶牛们按不太传统

19、的方式玩起了小孩子们玩的跳房子游戏。奶牛们创造了一个5x5的、由与x,y轴平行的数字组成的直线型网格，而不是用来在里面跳的、线性排列的、带数字的方格。然后他们熟练地在网格中的数字中跳：向前跳、向后跳、向左跳、向右跳(从不斜过来跳)，跳到网格中的另一个数字上。他们再这样跳啊跳(按相同规则)，跳到另外一个数字上(可能是已经跳过的数字)。一共在网格内跳过五次后，他们的跳跃构建了一个六位整数(可能以0开头，例如000201)。求出所有能被这样创造出来的不同整数的总数。问题名称:numgrid输入格式:*第1到5行:这样的网格，一行5个整数输入样例(文件numgrid.in):1111111111111

20、111112111111输出格式:*第1行:能构建的不同整数的总数输出样例(文件numgrid.out):15输出详细说明:111111,111112,111121,111211,111212,112111,112121,121111,121112,121211,121212,211111,211121,212111和212121能够被构建。没有其它可能的数了。*Problem13:卫星照片RobKolstad,2005FarmerJohn给他的农场买了WxH像素的卫星照片(1=W=80,1=H=1000)，希望找出最大的连续的(互相连接的)牧场。任何一对像素，一个像素如果能横向的或纵向的与属

21、于这个牧场的另一个像素相连，这样的牧场称作是连续的(这句话太难翻了，大家将就着理解一下，看了后面的范例应该不会影响做题译者)。(很容易创建形状稀奇古怪的牧场，甚至是围着其它圆圈的圆圈。)每一张照片都数字化的抽象了，牧场区显示为*,非牧场区显示为.。下面是一个10x5的卫星照片样例:.*.*.*.*.*.*.*.*.*.*这张照片显示了大小分别为4、16、6个像素的连续牧场区。帮助FJ在他的每张卫星照片中找到最大的连续牧场。问题名称:satpix输入格式:*第1行:两个由空格分开的整数，H和W。*第2到H+1行:每一行包含W个*或者.，代表卫星照片的横向行。输出样例(文件satpix.in):105.*.*.*.*.*.*.*.*.*.*输出格式:*第1行:最大连续牧场的大小输出样例(文件satpix.out):16