宇哥小屋 / 核心素养 / (1条消息)计算思维实践之路(五)

分享

   

(1条消息)计算思维实践之路(五)

2020-01-05  宇哥小屋

          7月31日,晴。“递归方便耗内存,来去自在汉诺塔“。

      递归与非递归哪个省内存?  

        递归更消耗内存,来说说一下递归的“可怕”程度吧,递归无非是程序调用自身,程序运行时代码和数据存到内存中,即要分配内存空间,递归程序每调用一次自身,操作系统都要为其分配相应的内存资源,这一过程是通过“栈”这种数据结构实现的,可查阅操作系统和编译原理方面的书籍,通俗地说一下,栈就像一个水桶,只有上面有口,进栈和出栈都只能通过上面的口,从而有先进后出的数据结构特性,好啦,现在再回到递归那里,递归程序的一次调用好比向桶里放一块砖,依次向上堆,调用不结束就会一直向里放“砖”,如果调用次数稍多或内存较小的话很容易溢出,你会发现每次调用有很多东西是重复的,而循环则不同,循环得每次执行是对已有变量的更新,一般不会产生大量重复的东西,从而节省内存,但为什么还要用递归呢,这是因为一些算法用递归写起来比较方便,当然不少递归算法都有他的循环版本,在嵌入式开发中,禁止写递归。

          我本是西海龙王敖闰之子,唤名龙马三太子,驮师父往西天拜佛。我来做一道简单的。

     例9 非负数n的阶乘,按以下公式

           

  1. #include<stdio.h>
  2. int fn(int n) {
  3. if(n==0)//递归终止条件
  4. return 1;
  5. else//递归通式
  6. return n*fn(n-1);
  7. }
  8. int main() {
  9. int n;
  10. printf("请输入1个整数:");
  11. scanf("%d",&n);
  12. printf("%d!的阶乘是%d\n",n,fn(n));
  13. return 0;
  14. }

                     有一个梵塔-汉诺塔,塔内有三个座A、B、C,A座上有诺干个盘子,盘子大小不等,大的在下,小的在上。把这些个盘子从A座移到C座,中间可以借用B座但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上。

             分析:描述简化---把A柱上的n个盘子移动到C柱,其中可以借用B柱。

                             

            1、任务分析                  

        2、算法构思

   任务1、把A上的n-1个盘子移动到B:  Hanoi (n-1,a,c,b);       // 操作结束为状态1     

   任务2、把A上的大盘子移动到C              move(a,c)    

   任务3、把B上的n-1移动到A     Hanoi (n-1,b,c,a);  //操作结束位状态2(和状态1相比只是规模变小)

     3、代码实现

   有了神仙姐姐的分析,俺沙悟净写一下代码:

  1. #include <iostream>
  2. using namespace std;
  3. void Hanoi(int n, char src,char mid,char dest)
  4. //将src座上的n个盘子,以mid座为中转,移动到dest座
  5. {
  6. if( n == 1) { //只需移动一个盘子
  7. cout << src << "->" << dest << endl; //直接将盘子从src移动到dest即可
  8. return ; //递归终止
  9. }
  10. Hanoi(n-1,src,dest,mid); //先将n-1个盘子从src移动到mid
  11. cout << src << "->" << dest << endl; //再将一个盘子从src移动到dest
  12. Hanoi(n-1,mid,src,dest); //最后将n-1个盘子从mid移动到dest
  13. return ;
  14. }
  15. int main() {
  16. int n;
  17. cin >> n; //输入盘子数目
  18. Hanoi(n,'A','B','C');
  19. return 0;
  20. }


       

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>