现在的位置: 首页 > 综合 > 正文

递归的练习

2014年03月17日 ⁄ 综合 ⁄ 共 9301字 ⁄ 字号 评论关闭

对递归的基础不是很了解,从网上搜索了部分练习题进行练习,明确递归的用法~!!!!得意

dic递归基础练习题:
1.  求1+2+3+……+n的值

intsum(int a,int b)

{

       if(b==a) return a;

       return a+sum(a+1,b);    

}
2.  求1*2*3*……*n的值

cheng(intbegin,int end)

{

       if(begin==end) return begin;

       return begin * 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,int times)

{

      

       if(times==10) return begin;

       return fruit((begin+1)*2,times+1);

}
6. 有雌雄一对兔子,假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子?
7.  一个人赶着鸭子去每个村庄卖,每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子,问他出发时共赶多少只鸭子?经过每个村子卖出多少只鸭子?

duck(intbegin,int times)

{

      

       if(times==7) return begin;

       return duck((begin+1)*2,times+1);

}

8.  著名的菲波拉契(Fibonacci)数列,其第一项为0,第二项为1,从第三项开始,其每一项都是前两项的和。编程求出该数列前N项数据。

intfbi(int i)

{

       if(i<2)

       {

              if(i== 0) return 0;

              elsereturn 1;

       }

              returnfbi(i-1) +fbi(i-2);

}
9.  求两个数的最大公约数。

fgongyue(intm,int n)//m要大于n,前面可以交换让它实现

{

       if(n == 0) return m;

       fgongyue(n,m%n);

}
10.  求两个数的最小公倍数。

最小公倍数等于2个数之积乘最好公约数

m*n/fgongyue(m,n)
11
.  输入一个数,求这个数的各位数字之和。

add_every_num(int num)

    if(num<10)return num;

    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"

 

 

int i = 1;

 

int fc(int n)

{

    if(n== 1)

    {

           printf("%d",n);

           return i;

    }

    elseif(n%2 == 0)

    {

           printf("%d\t",n);

           fc(n/2);

           i++;

    }

    else

    {

           printf("%d\t",n);

           fc(n*3+1);

           i++;

          

    }

}

 

int main(int argc, char* argv[])

{

    intn,step;

    printf("Pleaseinput the num:");

    scanf("%d",&n);

    step= fc(n);

    printf("\nStep= %d\n",step);

    return0;

}

13.  将十进制转换为二进制。

 

#include "stdafx.h"

#include "stdio.h"

 

int fc(int num)

    if(num== 1)

    {

           printf("%d",num);

           return 0;

    }

    fc(num/2);

    printf("%d",num%2);   

}

 

int main(int argc, char* argv[])

{

    intnum;

    printf("pleaseinput the num:");

    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<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为偶数)正面朝上排成一排,每次将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

 

抱歉!评论已关闭.