鱼C论坛

 找回密码
 立即注册
查看: 1829|回复: 1

[技术交流] 1.递归算法深入学习第一天

[复制链接]
发表于 2017-1-10 15:24:56 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 致年轻的我们 于 2017-1-10 15:26 编辑

先来一个简单的递归算法,这是递归算法求阶乘:
  1. #include <stdio.h>

  2. long fun(int n)
  3. {
  4.         if(n == 0)        return 1;
  5.         else        return(n*fun(n-1));
  6. }

  7. int main()
  8. {
  9.         //5*4*3*2*1=120
  10.         printf("%d\n",fun(5));
  11.         return 0;
  12. }
复制代码

对于能不用递归解决的问题,不建议使用递归解决。而有些问题只能通过递归算法解决(例如汉诺塔),而有些问题,递归算法效率更高(全排列问题)。
上述例子图解
           | 5x
           |            | 4x
fun(5) |            |            | 3x
           | fun(4) |            |            | 2x
                        | fun(3) |            |            | 1x
                                     | fun(2) |            |
                                                  | fun(1) |
                                                               | fun(0) == 1
*********************************分割线*********************************
契波那契数列是计算机学科中一个重要的数列,它的值如下
0 1 1 2 3 5 8 13 21 34 55 ......
数列规律是后一项是前两项之和
实现代码如下:
  1. #include <stdio.h>

  2. int Finonacci(int n)
  3. {
  4.         if(n == 0)        return 0;
  5.         else if(n == 1)        return 1;
  6.         else return(Finonacci(n-1) + Finonacci(n-2));
  7. }

  8. int main()
  9. {
  10.         //0 1 2 3 4 5 6 7  8  9  10
  11.         //0 1 1 2 3 5 8 13 21 34 55
  12.         printf("%d\n",Finonacci(10));
  13.         return 0;
  14. }
复制代码

简易图解:
F(5) |
       | F(4) |
       |        | F(3) |
       |        |        | F(2) |
       |        |        |        | F(1) ==1
       |        |        |   +   |    +
       |        |   +   |        | F(0) ==0
       |   +   |        |   
       |        |        | F(1) == 1
       |        |   
       |        | F(2) |
       |                 | F(1) ==1
       |                 |    +
       |                 | F(0) ==0
       | F(3) (注:这个就不展开了)
数学形式如下
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
*********************************分割线*********************************
汉诺塔问题
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在第一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门借助第二根柱子把圆盘从下面开始按大小顺序重新摆放在第三根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
这是一个典型的只能用递归,而不能使用其他方法解决的问题。

解决问题思路:
1.首先借助第3根柱子把63个圆盘放到第2根柱子
2.把第64个盘子直接从第1根柱子放到第3根柱子
3.借助第1根柱子把第2根柱子的63个圆盘放到第3根柱子
以上只不过是大致的步骤,1 3步骤还需要细分
按照此思路代码实现

  1. #include <stdio.h>

  2. //n是需要移动的盘子数目
  3. void hanoi(int n,char start,char temp,char finish)
  4. {
  5.         if(n == 1)
  6.         {
  7.                 printf("%c -> %c\n",start,finish);//如果只有一个盘子,当然是直接从start到finish
  8.         }
  9.         else
  10.         {
  11.                 hanoi(n-1,start,finish,temp);//这是上述的第一步,把n-1个盘子借助finish移动到temp
  12.                 printf("%c -> %c\n",start,finish);//这是第二步,把第n个盘子直接从start移动到finish
  13.                 hanoi(n-1,temp,start,finish);//这是第三步。借助start把temp上的n-1个圆盘放到finish上
  14.         }
  15. }

  16. int main()
  17. {
  18.         printf("start\n");
  19.         //3个盘子时
  20.         hanoi(3,'1','2','3');
  21.         printf("end\n");
  22.         return 0;
  23. }
复制代码

今天就到这里明天继续。
欢迎加入编程爱好者交流群:518384767,期待您的加入。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-1-10 16:42:47 | 显示全部楼层
一楼备用
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:26

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表