C语言递归练习附答案.docx
《C语言递归练习附答案.docx》由会员分享，可在线阅读，更多相关《C语言递归练习附答案.docx（15页珍藏版）》请在冰点文库上搜索。
C语言递归练习附答案
dic递归基础练习题：
1. 求1+2+3+……+n的值
intsum（inta,intb）
{
if（b==a）returna;
returna+sum（a+1,b）;
}
2. 求1*2*3*……*n的值
cheng（intbegin,intend）
{
if（begin==end）returnbegin;
returnbegin*cheng（begin+1,end）;
}
3. 数的全排列问题。
将n个数字1，2，…n的所有排列按字典顺序枚举出猴
2 3 1
2 1 3
3 1 2
3 2 1
4. 数的组合问题。
从1,2,…,n中取出m个数，将所有组合按照字典顺序列出。
如n=3,m=2时，输出：
1 2
1 3
2 3
5. 小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？
fruit（intbegin,inttimes）
{
if（times==10）returnbegin;
returnfruit（（begin+1）*2,times+1）;
}
6. 有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。
问过n个月后共有多少对兔子？
7. 一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。
这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？
经过每个村子卖出多少只鸭子？
duck（intbegin,inttimes）
{
if（times==7）returnbegin;
returnduck（（begin+1）*2,times+1）;
}
8. 著名的菲波拉契（Fibonacci）数列，其第一项为0，第二项为1，从第三项开始，其每一项都是前两项的和。
编程求出该数列前N项数据。
intfbi（inti）
{
if（i<2）
{
if（i==0）return0;
elsereturn1;
}
returnfbi（i-1）+fbi（i-2）;
}
9. 求两个数的最大公约数。
fgongyue（intm,intn）//m要大于n，前面可以交换让它实现
{
if（n==0）returnm;
fgongyue（n,m%n）;
}
10. 求两个数的最小公倍数。
最小公倍数等于２个数之积乘最好公约数
m*n/fgongyue（m,n）
11. 输入一个数，求这个数的各位数字之和。
add_every_num（intnum）
{
if（num<10）returnnum;
returnnum%10+add_every_num（num/10）;
}
12. 角谷定理。
输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。
经过如此有限次运算后，总可以得到自然数值1。
求经过多少次可得到自然数1。
如：
输入22，
输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
STEP=16
#include"stdafx.h"
#include"stdio.h"
inti=1;
intfc（intn）
{
if（n==1）
{
printf（"%d",n）;
returni;
}
elseif（n%2==0）
{
printf（"%d\t",n）;
fc（n/2）;
i++;
}
else
{
printf（"%d\t",n）;
fc（n*3+1）;
i++;
}
}
intmain（intargc,char*argv[]）
{
intn,step;
printf（"Pleaseinputthenum:
"）;
scanf（"%d",&n）;
step=fc（n）;
printf（"\nStep=%d\n",step）;
return0;
}
13. 将十进制转换为二进制。
#include"stdafx.h"
#include"stdio.h"
intfc（intnum）
{
if（num==1）
{
printf（"%d",num）;
return0;
}
fc（num/2）;
printf（"%d",num%2）;
}
intmain（intargc,char*argv[]）
{
intnum;
printf（"pleaseinputthenum:
"）;
scanf（"%d",&num）;
fc（num）;
printf（"\n"）;
return0;
}
14. 计算M＝max（a,b,c）/[max（a+b,b,c）*max（a,b,b+c）],其中a，b，c由键盘输入。
skip
15. 梯有N阶，上楼可以一步上一阶，也可以一次上二阶。
编一个程序，计算共有多少种不同的走法。
return1+（fc（n-1）+fc（n-2）
16. 某人写了n封信和n个信封，如果所有的信都装错了信封。
求所有的信都装错信封共有多少种不同情况?
17. 给出一棵二叉树的中序与后序排列。
求出它的先序排列。
18. 求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。
19. 已知一个一维数组A[1..N]。
{N<50} 又已知一整数M。
如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。
20. 要求找出具有下列性质的数的个数（包含输入的自然数n）：
先输入一个自然数n（n<=500）,然后对此自然数按照如下方法进行处理:
①. 不作任何处理;
②. 在它的左边加上一个自然数,但该自然数不能超过原数首位数字的一半;
③. 加上数后,继续按此规则进行处理,直到不能再加自然数为止.
样例:
输入:
6
满足条件的数为 6
16
26
126
36
136
输出:
6
21. 自然数的拆分问题。
给定自然数n,将其拆分成若干自然数的和。
输出所有解，每组解中数字按从小到大排列。
相同数字的不同排列算一组解。
如：
3=1+1+1
3=1+2
3=3
22. 用递归的方法求N个数中最大的数及其位置。
23. 写出折半查找的递归算法。
24. 快速排序法。
思考题 :
1、数学宝塔，从最顶上走到最底层，每次只能走到下一层的左边或右边的数字，求出使所走到的所有数字之和为60的途径。
7
4 6
6 9 3
6 3 7 1
2 5 3 2 8
5 9 4 7 3 2
6 4 1 8 5 6 3
3 9 7 6 8 4 1 5
2 5 7 3 5 7 8 4 2
2、 汉诺塔问题：
设有三个塔座，依次命名为x,y,z。
有z个直径不同的圆盘，由小到大依次编号为1、2、……，n。
开始时，它们全部按递减的次序插在塔座上。
现要求按下列规则把n个圆盘按次序插放在z塔座上。
（1）、每次只能移动一个圆盘；
（2）、圆盘可以从任一个塔座上移到另一个塔座上；
（3）、任何时刻都不能把一个较大的圆盘压在较小的圆盘上。
典型例题:
1.设有n个数已经按从大到小的顺序排列，现在从键盘上输入n，判断它是否在这n 个数中，如果存在则输出“yes”否则输出“no”。
Program lx4;
Const n=30;
Var a:
array[1..n]of integer;
F,r,x,k:
integer;
Program search（x,top,bot:
integer）;
Var mid:
integer;
Begin
if top<=bot then
Begin
Mid=（top + bot） div 2;
If x =a[mid] then writeln（x:
5,mid:
5,’yes’）
else If x Else search（x,mid+1,r）;
End
else Writeln（x:
5,‘no’）;
End;
Begin
Writeln（‘input n ge shu’）;
For k:
=1 to n do read（a[k]）;
Read（x）;
F:
=1;r:
=n;
Search（x,f,r）;
End.
2.hanoi塔问题。
递归：
procedure Hanoi（n:
integer;x,y,z:
char）;
Begin
If n=1 then writeln（x,’--’n,’---’,z）
Else begin
Hanoi（n-1,x,z,y）;
Writeln（x,’--’,n,’---’,z）;
Hanoi（n-1,y,x,z）
End;
End;
Begin
Write（‘input n:
’）;
Read（n）;
Hanoi（n,’A’,’B’,’C’）
End.
3.有n个硬币（n为偶数）正面朝上排成一排，每次将n-1个硬币翻成朝上为止。
编程让计算机把翻硬币的最简过程及翻币次数打印出来（用*代表正面，用0代表反面）。
基本形式：
D[1]=0;d[2]=1
递归式：
d[n]= （n-1）*（ d[n-1] + d[n-2]）
var n:
integer;
function d（n:
integer）:
longint;
begin
case n of
1:
d:
=0;
2:
d:
=1;
else d:
=（n-1）*（d（n-1）+d（n-2））;
end;
end;
begin
repeat
write（'n='）;
readln（n）;
if n<=0 then writeln（'Once more!
'）
until n>0;
writeln（'d=',d（n））;
readln;
end.
4.有一对雌雄兔子，假定两个月便可以繁殖雌雄各一对兔子。
问n各月后共有多少对兔子？
递归的三要素：
递归的形式：
T[n]= T[n-1]+ T[n-2]
基本：
T[1]=1，T[2]=1
结束条件：
n个月
program rabbit;
var n:
integer;
function fa（n:
integer）:
integer;
begin
if n<3 then fa:
=1
else fa:
=fa（n-1）+fa（n-2）;
end;
begin
write（'n='）;readln（n）;
writeln（'The number of the rabbits:
',fa（n））;
end.
5.梯有N阶，上楼可以一步上一价，也可以一次上二阶。
编一个程序，计算共有多少种不同的走法。
递归的形式：
s[n]=s[n-1]+s[n-2]
基本式子：
s[1]=1;s[2]=2
program upstairs;
var n:
integer;
function s（n:
integer）:
longint;
begin
if （n=1）or（n=2） then s:
=n
else s:
=s（n-1）+s（n-2）;
end;
begin
repeat
write（'N='）;readln（n）;
until n>0;
writeln（'s=',s（n））;
readln;
end.
6.斐波那切数列
递归：
var m,p:
integer;
Function fib（n:
integer）:
integer;
Begin
If n=0 then fib:
=0
Else if n=1 then fib:
=1
Else fib:
=fib（n-1）+fib（n-2）;
End;
Begin
Read（m）;
P:
=fib（m）;
Writeln（‘fib（’,mm’）=’,p）
End.
7.设有2^n个运动员要进行网球比赛。
现要设计一个满足以下要求的比赛日程表：
（1）、每个选手必须与其他n-1个选手各赛一次；
（2）、每个选手每天只能参赛一次；
（3）、循环赛在n-1天内结束。
program match;
const k=3;n=8;
var
s:
array[1..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;
begin
if jug then
begin
if be=1 then
begin if s[en,en]=0 then
begin copy1（be,en div 2,true,q div 2）;
copy1（（en div 2）+1,en,false,q div 2）;
end;
for m:
=1 to en do
for t:
=1 to en do
s[m+q,t+q]:
=s[m,t]
end
else begin if s[be+q-1,q]=0 then
begin copy1（be,be+（q div 2）-1,true,q div 2）;
copy1（be+（q div 2）,en,false,q div 2）
end;
for m:
=be to en do
for t:
=1 to q do
s[m+q,t+q]:
=s[m,t]
end
end
else begin
if s[be,q]=0 then
begin copy1（be,be+（q div 2）-1,true,q div 2）;
copy1（be+（q div 2）,en,false,q div 2）
end;
for m:
=be to en do
for t:
=1 to q do
s[m-q,t+q]:
=s[m,t]
end
end;
begin
p:
=8;
for i:
=1 to n do
for j:
=1 to n do
s[i,j]:
=0;
for i:
=1 to n do
begin
s[i,1]:
=i;
if odd（i） then s[i+1,2]:
=s[i,1]
else s[i-1,2]:
=s[i,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 do
begin
for j:
=1 to n do
write（s[i,j],' '）;
writeln;
end;
end.
以下是USACO contest上的题目，全是递归
-----------------------------------------------
**********************************************************************
BRONZE PROBLEMS
**********************************************************************
三道题目，从11到13
**********************************************************************
Problem 11:
谷仓的安保 [Traditional, 2005]
Farmer John给谷仓安装了一个新的安全系统，并且要给牛群中的每一个奶牛安排一个有效的密码。
一个有效的密码由L（3 <= L <= 15）个小写字母（来自传统的拉丁字母集'a'...'z'）组成，至少有一个元音（'a', 'e', 'i', 'o', 或者 'u'），至少两个辅音（除去元音以外的音节），并且有按字母表顺序出现的字母（例如，'abc'是有效的，而'bac'不是） 。
给定一个期望长度L和C个小写字母，写一个程序，打印出所有的长度为L、能由这些字母组成的有效密码。
密码必须按字母表顺序打印出来，一行一个。
题目名称:
passwd
输入格式:
* 第一行:
两个由空格分开的整数，L和C
* 第二行:
C个空格分开的小写字母，密码是由这个字母集中的字母来构建的。
输入样例 （文件 passwd.in）:
4 6
a t c i s w
输入详细说明:
由从给定的六个字母中选择的、长度为4的密码。
输出格式:
* 第一至?
行:
每一个输出行包括一个长度为L个字符的密码（没有空格）。
输出行必须按照字母顺序排列。
输出样例 （文件 passwd.out）:
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw
**********************************************************************
Problem 12:
"跳房子" [Hal Burch, 2005]
奶牛们按不太传统的方式玩起了小孩子们玩的"跳房子"游戏。
奶牛们创造了
一个5x5的、由与x,y轴平行的数字组成的直线型网格，而不是用来在里面跳
的、线性排列的、带数字的方格。
然后他们熟练地在网格中的数字中跳：
向前跳、向后跳、向左跳、向右跳
（从不斜过来跳），跳到网格中的另一个数字上。
他们再这样跳啊跳（按相同规
则），跳到另外一个数字上（可能是已经跳过的数字）。
一共在网格内跳过五次后，他们的跳跃构建了一个六位整数（可能以0开头，
例如000201）。
求出所有能被这样创造出来的不同整数的总数。
问题名称:
numgrid
输入格式:
* 第1到5行:
这样的网格，一行5个整数
输入样例 （文件 numgrid.in）:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1
输出格式:
* 第1行:
能构建的不同整数的总数
输出样例 （文件 numgrid.out）:
15
输出详细说明:
111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112,121211, 121212, 211111, 211121, 212111和 212121 能够被构建。
没有其它可能的数了。
**********************************************************************
Problem 13:
卫星照片 [Rob Kolstad, 2005]
Farmer John给他的农场买了W x H像素的卫星照片（1 <= W <= 80, 1 <= H
<= 1000），希望找出最大的"连续的"（互相连接的）牧场。
任何一对像素，一个
像素如果能横向的或纵向的与属于这个牧场的另一个像素相连，这样的牧场称
作是连续的（这句话太难翻了，大家将就着理解一下，看了后面的范例应该不
会影响做题—译者）。
（很容易创建形状稀奇古怪的牧场，甚至是围着其它圆圈
的圆圈。
）
每一张照片都数字化的抽象了，牧场区显示为"*",非牧场区显示为"."。
下面
是一个10 x 5的卫星照片样例:
..*.....**
.**..*****
.*...*....
..****.***
..****.***
这张照片显示了大小分别为4、16、6个像素的连续牧场区。
帮助FJ在他的每张
卫星照片中找到最大的连续牧场。
问题名称:
satpix
输入格式:
* 第1行:
两个由空格分开的整数，H 和 W。
* 第2到H+1行:
每一行包含W个"*"或者"."，代表卫星照片的横向行。
输出样例 （文件 satpix.in）:
10 5
..*.....**
.**..*****
.*...*....
..****.***
..****.***
输出格式:
* 第1行:
最大连续牧场的大小
输出样例 （文件 satpix.out）:
16
升级会员 