C語言遞歸練習附答案

dic遞歸基礎(chǔ)練習題：

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.

數(shù)的全排列問題。將n個數(shù)字1，2，…n的所有排列按字典順序枚舉出猴

2

3

1

2

1

3

3

1

2

3

2

1

4.

數(shù)的組合問題。從1,2,…,n中取出m個數(shù)，將所有組合按照字典順序列出。

如n=3,m=2時，輸出：

1

2

1

3

2

3

5.

小猴子第一天摘下若干桃子,當即吃掉一半,又多吃一個.第二天早上又將剩下的桃子吃一半,又多吃一個.以后每天早上吃前一天剩下的一半另一個.到第10天早上猴子想再吃時發(fā)現(xiàn),只剩下一個桃子了.問第一天猴子共摘多少個桃子？fruit(intbegin,inttimes){ if(times==10)returnbegin; returnfruit((begin+1)*2,times+1);}

6.

有雌雄一對兔子，假定過兩個月便可繁殖雌雄各一的一對小兔子。問過n個月后共有多少對兔子？

7.

一個人趕著鴨子去每個村莊賣，每經(jīng)過一個村子賣去所趕鴨子的一半又一只。這樣他經(jīng)過了七個村子后還剩兩只鴨子，問他出發(fā)時共趕多少只鴨子？經(jīng)過每個村子賣出多少只鴨子？duck(intbegin,inttimes){ if(times==7)returnbegin; returnduck((begin+1)*2,times+1);}

8.

著名的菲波拉契(Fibonacci)數(shù)列，其第一項為0，第二項為1，從第三項開始，其每一項都是前兩項的和。編程求出該數(shù)列前N項數(shù)據(jù)。intfbi(inti){ if(i<2) { if(i==0)return0; elsereturn1; } returnfbi(i-1)+fbi(i-2);}

9.

求兩個數(shù)的最大公約數(shù)。fgongyue(intm,intn)//m要大于n，前面可以交換讓它實現(xiàn){ if(n==0)returnm; fgongyue(n,m%n);}

10.

求兩個數(shù)的最小公倍數(shù)。最小公倍數(shù)等于２個數(shù)之積乘最好公約數(shù)m*n/fgongyue(m,n)

11.

輸入一個數(shù)，求這個數(shù)的各位數(shù)字之和。add_every_num(intnum){ if(num<10)returnnum; returnnum%10+add_every_num(num/10);}

12.

角谷定理。輸入一個自然數(shù)，若為偶數(shù)，則把它除以2，若為奇數(shù)，則把它乘以3加1。經(jīng)過如此有限次運算后，總可以得到自然數(shù)值1。求經(jīng)過多少次可得到自然數(shù)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.

將十進制轉(zhuǎn)換為二進制。#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.

求把一個整數(shù)n無序劃分成k份互不相同的正整數(shù)之和的方法總數(shù)。

19.

已知一個一維數(shù)組A[1..N]。{N<50}

又已知一整數(shù)M。如能使數(shù)組A中任意幾個元素之和等于M，則輸出YES，反之則為NO。

20.

要求找出具有下列性質(zhì)的數(shù)的個數(shù)(包含輸入的自然數(shù)n)：

先輸入一個自然數(shù)n(n<=500),然后對此自然數(shù)按照如下方法進行處理:

①.

不作任何處理;

②.

在它的左邊加上一個自然數(shù),但該自然數(shù)不能超過原數(shù)首位數(shù)字的一半;

③.

加上數(shù)后,繼續(xù)按此規(guī)則進行處理,直到不能再加自然數(shù)為止.

樣例:

輸入:

6

滿足條件的數(shù)為

6

16

26

126

36

136

輸出:

6

21.

自然數(shù)的拆分問題。給定自然數(shù)n,將其拆分成若干自然數(shù)的和。輸出所有解，每組解中數(shù)字按從小到大排列。相同數(shù)字的不同排列算一組解。如：

3=1+1+1

3=1+2

3=3

22.

用遞歸的方法求N個數(shù)中最大的數(shù)及其位置。

23.

寫出折半查找的遞歸算法。

24.

快速排序法。

思考題

:

1、數(shù)學寶塔，從最頂上走到最底層，每次只能走到下一層的左邊或右邊的數(shù)字，求出使所走到的所有數(shù)字之和為60的途徑。

7

46

693

6371

25328

5947

32

6418563

39768415

257357842

2、

漢諾塔問題：設(shè)有三個塔座，依次命名為x,y,z。有z個直徑不同的圓盤，由小到大依次編號為1、2、……，n。開始時，它們?nèi)堪催f減的次序插在塔座上。現(xiàn)要求按下列規(guī)則把n個圓盤按次序插放在z塔座上。

（1）、每次只能移動一個圓盤；

（2）、圓盤可以從任一個塔座上移到另一個塔座上；

（3）、任何時刻都不能把一個較大的圓盤壓在較小的圓盤上。

典型例題:

1.設(shè)有n個數(shù)已經(jīng)按從大到小的順序排列，現(xiàn)在從鍵盤上輸入n，判斷它是否在這n

個數(shù)中，如果存在則輸出“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<a[mid]

then

search(x,top,mid-1)

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為偶數(shù)）正面朝上排成一排，每次將n-1個硬幣翻成朝上為止。編程讓計算機把翻硬幣的最簡過程及翻幣次數(shù)打印出來（用*代表正面，用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

結(jié)束條件：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.斐波那切數(shù)列

遞歸：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.設(shè)有2^n個運動員要進行網(wǎng)球比賽?，F(xiàn)要設(shè)計一個滿足以下要求的比賽日程表：

（1）、每個選手必須與其他n-1個選手各賽一次；

（2）、每個選手每天只能參賽一次；

（3）、循環(huán)賽在n-1天內(nèi)結(jié)束。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給谷倉安裝了一個新的安全系統(tǒng)，并且要給牛群中的每一個奶牛安排一個有效的密碼。一個有效的密碼由L(3

<=

L

<=

15)個小寫字母(來自傳統(tǒng)的拉丁字母集'a'...'z')組成，至少有一個元音('a',

'e',

'i',

'o',

或者

'u')，至少兩個輔音(除去元音以外的音節(jié))，并且有按字母表順序出現(xiàn)的字母(例如，'abc'是有效的，而'bac'不是)

。

給定一個期望長度L和C個小寫字母，寫一個程序，打印出所有的長度為L、能由這些字母組成的有效密碼。密碼必須按字母表順序打印出來，一行一個。

題目名稱:

passwd

輸入格式:

*

第一行:

兩個由空格分開的整數(shù)，L和C

*

第二行:

C個空格分開的小寫字母，密碼是由這個字母集中的字母來構(gòu)建的。

輸入樣例

(文件

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]

奶牛們按不太傳統(tǒng)的方式玩起了小孩子們玩的"跳房子"游戲。奶牛們創(chuàng)造了

一個5x5的、由與x,y軸平行的數(shù)字組成的直線型網(wǎng)格，而不是用來在里面跳

的、線性排列的、帶數(shù)字的方格。

然后他們熟練地在網(wǎng)格中的數(shù)字中跳：向前跳、向后跳、向左跳、向右跳

(從不斜過來跳)，跳到網(wǎng)格中的另一個數(shù)字上。他們再這樣跳啊跳(按相同規(guī)

則)，跳到另外一個數(shù)字上(可能是已經(jīng)跳過的數(shù)字)。

一共在網(wǎng)格內(nèi)跳過五次后，他們的跳躍構(gòu)建了一個六位整數(shù)(可能以0開頭，

例如000201)。

求出所有能被這樣創(chuàng)造出來的不同整數(shù)的總數(shù)。

問題名稱:

numgrid

輸入格式:

*

第1到5行:

這樣的網(wǎng)格，一行5個整數(shù)

輸入樣例

(文件

numgr