C++分析研究  
C++
日历
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456
统计
  • 随笔 - 92
  • 文章 - 4
  • 评论 - 4
  • 引用 - 0

导航

常用链接

留言簿

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 

  递归算法也是C语言算法中一个比较简单与常用的算法,本文我们就来谈谈递归算法,我们首先了解一下什么是递归算法,关于递归算法的概念只有一句话:一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数)
  我们再来看看递归算法的特点:
  (1) 递归就是在过程或函数里调用自身。
  (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
  (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
  (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
  再看看递归的分类:
  直接递归
  程序设计中,过程或函数直接或者间接调用自己,就被称为递归调用。子程序直接调用自己,这称为直接递归;嵌套关系的子程序A和B,内层的B调用外层的A,这是间接低归;平级关系的子程序A和B,其中A调用了B,B调用了A,这也是间接递归,不过,这种间接递归用到了"超前引用"的规则。
  下面,博主找到了一些有关于递归算法的题目。我们看看第一个题目。
  这是一道很经典的题目:阶乘。相信大部分的人都知道什么是阶乘,但是你如果不知道的话,不妨参见一下百度百科:阶乘。
  好了,其实这题非常简单,我们只需要一个函数即可解决问题。
  1 int recursive(int i)
  2 {
  3 int sum = 0;
  4 if (0 == i)
  5 return (1);
  6 else
  7 sum = i * recursive(i-1);
  8 return sum;
  9 }
  就是上面的递归函数,这题我就不浪费篇幅讲解了,重点放在第二个例题:汉诺塔问题。
  一个庙里有三个柱子,第一个有64个盘子,从上往下盘子越来越大。要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子。而且每次只能移动一个。1、此时老和尚(后面我们叫他第一个和尚)觉得很难,所以他想:要是有一个人能把前63个盘子先移动到第二个柱子上,我再把最后一个盘子直接移动到第三个柱子,再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上,我的任务就完成了,简单。所以他找了比他年轻的和尚(后面我们叫他第二个和尚),命令:
  ① 你把前63个盘子移动到第二柱子上托福答案
  ② 然后我自己把第64个盘子移动到第三个柱子上后
  ③ 你把前63个盘子移动到第三柱子上
  2、第二个和尚接了任务,也觉得很难,所以他也和第一个和尚一样想:要是有一个人能把前62个盘子先移动到第三个柱子上,我再把最后一个盘子直接移动到第二个柱子,再让那个人把刚才的前62个盘子从第三个柱子上移动到第三个柱子上,我的任务就完成了,简单。所以他也找了比他年轻的和尚(后面我们叫他第三和尚),命令:
  ① 你把前62个盘子移动到第三柱子上
  ② 然后我自己把第63个盘子移动到第二个柱子上后
  ③ 你把前62个盘子移动到第二柱子上
  3、第三个和尚接了任务,又把移动前61个盘子的任务依葫芦话瓢的交给了第四个和尚,等等递推下去,直到把任务交给了第64个和尚为止(估计第64个和尚很郁闷,没机会也命令下别人,因为到他这里盘子已经只有一个了)。
  4、到此任务下交完成,到各司其职完成的时候了。完成回推了:
  第64个和尚移动第1个盘子,把它移开,然后第63个和尚移动他给自己分配的第2个盘子。
  第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成,第63个和尚完成了第62个和尚交给他的任务的第一步。
  从上面可以看出,只有第64个和尚的任务完成了,第63个和尚的任务才能完成,只有第2个和尚----第64个和尚的任务完成后,第1个和尚的任务才能完成。这是一个典型的递归问题。 现在我们以有3个盘子来分析:
  第1个和尚命令:
  ① 第2个和尚你先把第一柱子前2个盘子移动到第二柱子。(借助第三个柱子)
  ② 第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。
  ③ 第2个和尚你把前2个盘子从第二柱子移动到第三柱子。
  很显然,第二步很容易实现托福答案
  其中第一步,第2个和尚他有2个盘子,他就命令:
  ① 第3个和尚你把第一柱子第1个盘子移动到第三柱子。(借助第二柱子)
  ② 第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。
  ③ 第3个和尚你把第1个盘子从第三柱子移动到第二柱子。
  同样,第二步很容易实现,但第3个和尚他只需要移动1个盘子,所以他也不用在下派任务了。(注意:这就是停止递归的条件,也叫边界值)
  第三步可以分解为,第2个和尚还是有2个盘子,命令:
  ① 第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。
  ② 第2个和尚我把第2个盘子从第二柱子移动到第三柱子。
  ③ 第3个和尚你把第一柱子上的盘子移动到第三柱子。
  分析组合起来就是:1→3 1→2 3→2 借助第三个柱子移动到第二个柱子 |1→3 | 2→1 2→3 1→3借助第一个柱子移动到第三个柱子|共需要七步。
  如果是4个盘子,则第一个和尚的命令中第1步和第3步各有3个盘子,所以各需要7步,共14步,再加上第1个和尚的1步,所以4个盘子总共需要移动7+1+7=15步,同样,5个盘子需要15+1+15=31步,6个盘子需要31+1+31=64步……由此可以知道,移动n个盘子需要(2的n次方)-1步。
  从上面整体综合分析可知把n个盘子从1座(相当第一柱子)移到3座(相当第三柱子):
  (1)把1座上(n-1)个盘子借助3座移到2座。
  (2)把1座上第n个盘子移动3座。
  (3)把2座上(n-1)个盘子借助1座移动3座。
  下面用hanoi(n,a,b,c)表示把1座n个盘子借助2座移动到3座。
  很明显: (1)步上是 hanoi(n-1,1,3,2) (3)步上是 hanoi(n-1,2,1,3)

  用C语言表示出来,就是:
  1 #include <stdio.h>
  2 int method(int n,char a, char b)
  3 {
  4 printf("number%dform%cto%c"n",n,a,b);
  5 return 0;
  6 }
  7 int hanoi(int n,char a,char b,char c)
  8 {
  9 if( n==1 ) move (1,a,c);
  10 else
  11 {
  12 hanoi(n-1,a,c,b);
  13 move(n,a,c);
  14 hanoi(n-1,b,a,c);
  15 };
  16 return 0;
  17 }
  18 int main()
  19 {
  20 int num;
  21 scanf("%d",&num);
  22 hanoi(num,'A','B','C');
  23 return 0;
  24 }
  这就是递归算法,其实,在C语言中,递归算法比枚举法还要实用,但是这两种算法都很简单。

posted on 2014-05-30 09:53 HAOSOLA 阅读(306) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © HAOSOLA Powered by: 博客园 模板提供:沪江博客
PK10开奖 PK10开奖