开发者社区> 谙忆> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

汉洛塔递归实现的思考(C语言)

简介: 汉洛塔是古印度神话产生的智力玩具,他的玩法是,有三个柱子分别为A,B,C,A柱上面有n个盘子上面小下面大堆叠放在一起,现在要求激将A柱上的盘子全部移到C柱上面,并且一次只能移动一个盘子,必须是小盘在大盘的上面。
+关注继续查看

汉洛塔是古印度神话产生的智力玩具,他的玩法是,有三个柱子分别为A,B,C,A柱上面有n个盘子上面小下面大堆叠放在一起,现在要求激将A柱上的盘子全部移到C柱上面,并且一次只能移动一个盘子,必须是小盘在大盘的上面。现在要求用C语言递归来完成,并统计递归调用的次数。

这个实现是递归的强大功能的体现,废话不多说,请看源码:

#include<stdio.h>
void move(int n,int *cnt,char A,char B,char C)
{
    if(n==1)
    {
        printf("%d号盘:%c-->%c\n",n,A,C);     
        //如果还剩一个盘或者只有一个盘时,直接将1号盘移到C柱
        (*cnt)++;       
        //递归调用次数加1
    }

    else
    {
        move(n-1,cnt,A,C,B);       
        //将n-1个盘从A柱上借助于C柱移到B柱上
        printf("%d号盘:%c-->%c\n",n ,A,C);    
        //当将n-1个盘移到B柱成功时直接将A柱上的盘移到C柱
        move(n-1,cnt,B,A,C);        
        //再次将n-1个盘从B柱上借助于A柱移到C柱上
        (*cnt)++;          
        //递归调用次数加1
    }

}
int main(void)
{
    int h;
    int cnt = 0;
    printf("\ninput number:\n");
    scanf("%d",&h);
    printf("the step to moving %2d diskes:\n",h);
    move(h,&cnt,'A','B','C');
    printf("一共执行了%d次!\n",cnt);
}

我这里给出的源码是极为精简的,但是很健壮!现在分析如下:

首先,梳理一下思路,要用递归实现的前提是,问题规模更大的解决依赖于问题规模更小的解决,也就是说要想移动n个盘子,必须先移动n-1个盘子,这时递归的基础。那么现在有三个柱子,该如何移动呢?比较好的解决方案是:可以将n-1个盘子以C柱为中转站移动到B柱上,这样A柱上最下面的那个盘子就可自由地移动到C柱上了,然后在将n-1个盘子以A柱为中转站移动到C柱上,这就是上面代码核心的解决算法。

看到这里,很多人又有疑问,感觉这个解决方案,似乎理解了又似乎没理解,这时怎么回事?其实这就是递归的理解问题。在这个问题中,n个盘子会始终按照这个算法执行,当执行到n==1的时候一下子就返回,层层回叠返回最终的结果。

这个里面还有一个有意思的问题,就是递归调用的参数是个变量,比如说

move(n-1,cnt,A,C,B);

这一步中,他将C给了B,B给了C,这是个互换,又因为当n==1的时候不会再递归调用,故当盘子数为奇数时两个数会互换,而是偶数时就不会互换,举个例子如下:

#include <iostream>
using namespace std;
void swap (int n,int a,int b)
{
    if (n == 1)
    {
        cout << "a="<< a << "\tb=" << b << endl;
        return;
    }
    else
    {
        swap(n-1,b,a);
    }
}
int main (void)
{
    int a = 1;
    int b = 2;
    swap(3,a,b);
}

在这个例子中,当main函数中个传参的第一参数是奇数时a,b就不会互换,偶数时就会互换,这也是个互换数字的算法呢!

例外附注一下,汉洛塔的递归调用的个数是2的n次方减1,故大家在试的时候,不要输入太大的n值,以免在DOS下看不全结果!!

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
谈谈C语言的字面字符串
通过几段小程序深入分析了C语言中字面字符串(literal string)的特点以及正确的使用方式。
2930 0
《C语言及程序设计》实践项目——字符串数组
返回:贺老师课程教学链接 【项目1-带姓名的成绩单】设score数组中存储8名同学的C语言成绩,字符串数组name中存储同学们的姓名。这两个数组中,每名同学的姓名与成绩的下标要始终保持一致(例如name[i]和score[i]表示同一位同学(下标为i)的姓名和C语言成绩,否则会张冠李戴)。(1)输出按成绩排序后的同学的名单;(2)输出按同学姓名排序后的成绩单(排序对象是字符串)。#inclu
1180 0
《C语言及程序设计》实践参考——字符串复制
返回:贺老师课程教学链接  实践要求 【项目3-字符串复制】下面的程序,将str1中除空格外的所有字符,复制到了str2中。#include &lt;stdio.h&gt; int main() { char str1[100]="I am a happy boy\'s daddy.",str2[100]; int i=0,j=0; while(str1[i]!='\
713 0
《C语言及程序设计》实践项目——字符数组与字符串处理
返回:贺老师课程教学链接 【项目1-M$pszi$y是嘛意思?】背景:小明让同学传纸条给小丽。小丽接到会心一笑,大家却不知所云。纸条上写着M$pszi$y,两人暗中约定是,真实字符为实际字符前面的第4个!M$pszi$y是神马意思?推算一下,或从ASCII码表中查一下,自然是I love u。(1)小明请你写一个程序,在给小丽写情书时,再不用费功夫自己“翻译”,原信中每一个字符加密为其后的第
1194 0
《C语言及程序设计》实践参考——字符串处理函数
返回:贺老师课程教学链接  实践要求 【项目4-字符串处理函数】指针是神奇的,指向整型的指针int *p1,可以操作整型数组int a[];指向字符型的指针char *p2,可以操作字符数组(字符串)char str[];更灵活的是,在函数的传递中,指针、数组名在一定程度上可以互换。请编制函数,对字符串的进行各种操作。 序 功能 用数组名作形参 用指针作形参 1 字符串str1和str
1312 0
带有汉字的字符串截断出现半个“汉字”的解决方法-C语言源码
  汉字字符的编码为双字节,对于汉字字符和单字节字符混排的情况,如果目标截取的字符串内只包含奇数个单字节字符,则会出现半个汉字字符的问题。如下所示:   (1)天水市秦州区南郭路2号(工行七里墩分理处? --包含数字字符,单字节。
757 0
+关注
谙忆
GitHub: https://github.com/chenhaoxiang
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载