C语言递归练习

1、die递归基础练习题：求1+2+3+.+n的值mtsum(inta.iiitb)if(b=a)returna;retuina+sum(a+l,b);求1*2*3*n的值cheng(intbegin,intend)if(begin=end)retuinbegin;retuinbegm*cheng(begm+1,end);数的全排列问题。将n个数字1,2,n的所有排列按字典顺序枚举出猴2311312321数的组合问题。从1,2,.,n中取出m个数，将所有组合按照字典顺序列出。如n=3,m=2时，输出：21323小猴子第一天摘下若干桃子,当即吃掉一半，又多吃一个.第二天早上又将剩下的桃子吃一半，又多

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

3、etuinbegin;retuinduck(begiii-r1)*2.tmies+1);8著名的菲波拉契(Fibonacci)数列，其第一项为0,第二项为1,从第三项开始，其每一项都是前两项的和。编程求出该数列前N项数据。mtfbi(iiiti)if(i=0)return0;elseretuin1;returnfbi(i-l)+fbi(i2);求两个数的最大公约数。fgongyue(mtm,intn)/m要kJn,前面可以交换让它实现if(n=0)returnm;fgongyue(n,m%n);求两个数的最小公倍数。最小公倍数等于2个数之枳乘最好公约数m*iizfgoiigyue(m.n)输入

4、一个数，求这个数的各位数字之和。add_eveiy_nuni(mtnum)if(num10)returnnum;retiiinnum%10+add_every_num(nuni10);角谷定理。输入一个自然数，若为偶数，则把它除以2,若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。如：输入22,输出221134175226134020105168421STEP=16#includeHstdafx.hnincludeHstdio.hHiiiti=1;mtfc(intn)if(n=1)returni;elseif(n%2=0)elsefc(n*3

5、+l)；i+；mtaigc,char*argv)intn.step;printHPleasemputthenum:M);scanfC%dt&ii);step=fc(n);printf(MnStep=%d,n,step);return0;将十进制转换为二进制。#includeHstdafx.hnincludeHstdio.hMmtfc(intnum)prmtf(H%dH,nuni);return0;fc(nunV2);pmitf(”d=nun%2);mtaigc,char*argv)7intnum;printHpleasemputthenum:M);scanf(H%d,&num);fc(num)

6、;pmitffE);return0;计算M=niax(a,b,c)/max(a+b,b,c)*max(a,b,b+c),其中a,b,c由键盘输入。skip梯有N阶，上楼可以一步上一阶，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。returnl+(fc(n-l)+fc(n-2)某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况？给出一棵二叉树的中序与后序排列。求出它的先序排列。求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。已知一个一维数组Al.NoN50又已知一整数M。如能使数组A中任意几个元素之和等于M,则输出YES,反之则为N

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

8、走到最底层，每次只能走到卞一层的左边或右边的数字，求出使所走到的所有数字之和为60的途径。TOC o 1-5 h z6693637153289473241856397684152573578422、汉诺塔问题：设有三个塔座,编号为1、2、,1U开始时,依次命名为xyz。有z个直径不同的圆盘，由小到人依次它们全部按递减的次序插在塔座上。现要求按下列规则把n个圆盘按次序插放在z塔座上。（1）、每次只能移动一个圆盘；（2）、圆盘可以从任一个塔座上移到另一个塔座上;（3）、任何时刻都不能把一个较人的圆盘压在较小的圆盘上。典型例题：1设有n个数已经按从人到小的顺序排列，现在从键盘上输入n,判断它是否在这

9、n个数中,如果存在则输出“yes”否则输出“no”。Program1x4;Constn=30;Vaia:arrayl.nofinteger;Fj,x.k:integer;Programsearch(x.top,bot:integer);Varimd:mteger;Begmiftop=botthenBeginMid=(top+bot)div2;Ifx=anudthenTiteln(x:5.mid:5/yes)elseIfxanndtliensearch(x.top4iiid-1)Elsesearch(xjiiid+lj)；EndelseWriteln(x:5/no,);End;BeginWrit

10、elii(cinputngeshu，);Fork:=ltondoread(ak);Read(x);F:=l;r:=n;Search(x.fr);End.Hanoi塔问题。递iJH:procedureHanoi(n:integer;x,y,z:char);BegmIfn=lthenwritelii(x一5一z)ElsebeginHanoi(n-l?x,z,y);Wntelii(x；-n；z);Hanoi(n-l,y,x,z)End;End;BeginWriteCmputn/);Read(n);Haiioi(n；A,B,；C,)End.有n个硬币(n为偶数)正面朝上排成一排，每次将ml个硬币翻成朝

11、上为止。编程让计算机把翻硬币的最简过程及翻币次数打印出来(用*代表正面，用0代表反面)。基本形式：Dl=0;d2=l递归式：dn=(n-l)*(dn-l+dn-2)varn:integer;fiinctiond(n:integer):longint;begmcasenofl:d:=0;2:d:=l;elsed:=(n-1)*(d(n-l)+d(n-2);end;end;beginrepeatwrite(,n=,);readlii(n);ifn0;wntelii(rd=d(n);readhi;end.有一对雌雄兔子，假定两个月便可以繁殖雌雄各一对兔子。问n各月后共有多少对兔子？递归的三要素：递归

12、的形式：Tn=Tn-l+Tn-2基本：Tl=l,T2=l结束条件：n个月programrabbit;varn:integer;fiinctionfa(n:mtegei):integer;begmifn0;wntelii(rs=s(n);readlii;end斐波那切数列递归：vaim,p:integer;Functionfib(n:integer):integer;BegmIfn=0thenfib:=OElseifn=lthenfib:=lElsefib:=fib(n-1)+fib(n-2);End;BeginRead(m);P:=fib(m);WritelnCfib(niinJ)=p)End

13、.设有2-n个运动员要进行网球比赛。现要设计一个满足以卞要求的比赛口程表：、每个选手必须与其他ml个选手各赛一次；、每个选手每天只能参赛一次；、循坏赛在ml天内结束。programmatch;constk=3;n=8;vars:array1.n,l.nofinteger;ij,p:mteger;ju:boolean;procedurecopyl(be,en:mteger;jug:boolean;q:integer);varm.t,ban:integer;begmifjugthenbeginifbe=lthenbegmifsen,en=0thenbegincopvl(be,endiv2,true

14、.qdiv2);copyl(endiv2)+l,en,false,qdiv2);end;form:=ltoendofort:=ltoendosm+qj+q:=sm,tendelsebeginifsbe+q-l,q=0thenbegincopyl(be,be+(qdiv2)-1,true,qdiv2);copyl(be+(qdiv2),eiLfalse.qdiv2)form:=betoendofort:=ltoqdosm-rq.Hq：=smjendendelsebeginifsbe.q=0thenbegincopyl(be,be+(qdiv2)-lJiue,qdiv2);copyl(be+(qd

15、iv2),en,false,qdiv2)end;form:=betoendofort:=ltoqdosm-qj+q:=sm,tendend;begmfori:=ltondofbij:=ltondosij：=0；fori:=ltondobegmifodd(i)thensi+l,2:=sijelsesi-l,2:=si,l;end;copy1(Lndiv2jme,pdiv2);copyl(ndiv2)+l,n,false,pdiv2);fori:=ltondobeginfbij:=ltondownte(si,j；)；wiitelii;end;end.以下是USACOcontest上的题目,全是递归

16、*BRONZEPROBLEMS*三道题目，从11到13*Problem11:谷仓的安保Traditional,2005FarmerJolm给谷仓安装了一个新的安全系统，并且要给牛群中的每一个奶牛安排一个有效的密码。一个有效的密码由L（3=L=15）个小写字母（来自传统的拉丁字母集W.N）组成，至少有一个元音（h,e,T,O,或者W）,至少两个辅音（除去元音以外的音节），并且有按字母表顺序出现的字母（例如，是有效的，而Sc，不是）。给定一个期望长度L和C个小写字母，写一个程序，打印出所有的长度为L、能由这些字母组成的有效密码。密码必须按字母表顺序打印出来，一行一个。题目名称:passwd输入格式

17、：*第一行：两个由空格分开的整数，L和C*第二行:C个空格分开的小写字母，密码是由这个字母集中的字母来构建的。输入样例（文件passwd.m）:46atcisw输入详细说明：由从给定的六个字母中选择的、长度为4的密码。输出格式：*第一至?行:每一个输出行包括一个长度为L个字符的密码（没有空格）。输出行必须按照字母顺序排列。输出样例（文件passwd.out）:acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistw*Problem12:“跳房子HalBurch,2005奶牛们按不太传统的方式玩起了小孩子们玩的”跳房子”游戏。奶牛们创造了一

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