汉诺塔递归的c语⾔实现（递归）对于递归来讲, 汉诺塔实际是经典到不能再经典的例⼦了,  每个数据结构的教材对会提到.
但是到最后只给出⼀段类似下⾯的⼀段代码:
1. #include<stdio.h>
2.
3. void move(int n,char a,char b,char c)
4. {
5. if(n==1)
6. printf("\t%c->%c\n",a,c); //当n只有1个的时候直接从a移动到c
7. else
8. {
9. move(n-1,a,c,b); //把a的n-1个盘⼦通过c移动到b
0. printf("\t%c->%c\n",a,c); //把a的最后1个盘(最⼤的盘)移动到c
1. move(n-1,b,a,c); //吧b上⾯的n-1个盘通过a移动到c
2. }
3. }
14.
递归函数c语言规则5. main()
6. {
7. int n;
8. printf("请输⼊要移动的块数：");
9. scanf("%d",&n);
0. move(n,'a','b','c');
1. }
这段代码⽤来学习递归思想是⾜够的,  也能⼤概上了解到移动汉诺塔的步骤.
但是我说, 这段代码没有体会出汉诺塔的本质, 也没有办法验证.
下⾯我会敲出能体现出汉诺塔本质的递归代码. 并能根据输出每1个步汉诺塔的状态, 并且验证正确性.
1. 什么是汉诺塔
下⾯的定义摘⾃:
有三根杆⼦A，B，C。A杆上有N个(N>1)穿孔圆盘，的尺⼨由下到上依次变⼩。要求按下列规则将所有圆盘移⾄C杆：
1. 每次只能移动⼀个圆盘；
2. 盘不能叠在盘上⾯。
配图:
2. 汉诺塔的本质是3个栈
维基的定义只简单提到了汉诺塔的规则, 但是并没有揭⽰它的本质.  下⾯我们来分析它的本质.
1.每次只能移动1个盘:
也就说不能两个盘⼀齐移动, 必须按顺序1个1个套在柱⼦上,  ⽽且只能从柱⼦的上⽅套⼊, 也能只能从柱⼦的上⽅取出.
这明显就是1个先进后出的线性结构了,  因为出⼊⼝只有1个啊, 柱⼦的下⽅是不能放⼊和取出盘⼦的.
先进后出的线性结构就是栈了,  套⼊柱⼦和取出盘⼦就是对应的压栈和出栈动作.  如果读者之前没有了解过栈的话, 个⼈建议先去了解下栈, 然后再往下看.
2. ⼤盘不能套在⼩盘上⾯
代表这3个栈中, 如果不是空栈, 那么压栈的元素必须⽐栈顶元素⼩, 然后才允许压栈.  这就保证栈⾥⾯的元素是从⼩到⼤排序的.
总结:  汉诺塔的本质就是3个栈,  ⽽且压栈的元素必须⽐栈顶元素(如果存在)⼩.
3. 汉诺塔的解题思路及递归原理
好, 现在开始讲解汉诺塔的解题思路.
假如A塔有n个盘⼦, ⼤⼩从⼤(底部) 到⼩(顶部)排列,  B塔和C塔都是空塔.
如下图:
好了那么到底如何把这个n个盘⼦移动到C塔呢?
3.1  假如n=1 也就是说A塔只有1个盘⼦的情况下, 直接将1个盘⼦移动到c塔
那么我们写1个函数move()
执⾏move(A,C) 就是把A⾥唯⼀1个盘⼦移动到C
当然这⾥先不管这个函数具体是如何实现的.
但是可看出, 这个过程是不需要借助B塔中转的.
3.2  n>1的情况分析, hanoi_m(A,B,C,n) 函数
但是n>1呢? 上⾯的move函数就⾏不同了, 所以我们需要1个新的函数 hanoi_m()
hanoi_m(A, B, C, n) 函数意思就是把n个盘⼦从A借助B移动到C.
这⾥也先不管这个函数是如何具体如何实现, 知道它的参数意义和⽬地就ok了.
我上篇⽂章讲过, 递归的条件之⼀就是令数据规模不断地减少, 也就是假如1个函数f(n) 是递归函数, 则必须要出f(n) 与f(n-1)关系,  也就是说把求f(n) 转化为求f(n-1), 然后再转化为求f(n-2), 最终f(1)就是出⼝.
那么这⾥的hanoi_m(x,x,x,1) 是什么呢?  就是上⾯的move()函数了,  也就说出⼝到了.
但是hanoi_m(x,x,x,n) 与 hanoi_m(x,x,x, n-1) 的关系还不知道,  这就是汉诺塔递归函数的精髓了!
下⾯步骤就是讲解这个n 与 n-1的关系.
关键的⼀点:  假如要将n-1个盘⼦放到C塔, 如果c塔是⾮空的话, 那么c塔的盘⼦都必须⽐n-1⼤, 否则按照规则是不能放⼊的!
所以 最⼤的盘⼦必须⽐ 它⼩的所有盘⼦先放⼊C塔.
1.但是如果要将最⼤的盘⼦从A塔移动到C塔,  那么C塔必须是空的, 不让放不下
2.⽽且最⼤的盘⼦必须在A塔的最上⾯, 也就是说A塔只有1个最⼤的盘⼦.
3.所以其他盘⼦都必须在B塔上,
理解好这个那么问题就不⼤了
下⾯是详细步骤
3.3  第⼀步, 将A上⾯的n-1个盘⼦借助C塔移动到B塔. hanoi(A,C,B,n-1)
这个过程⽤函数来表⽰就是hanoi_m(A,C,B,n-1)啊, 理解这⼀步也⼗分关键:
如图:
⾄于这个过程具体如何实现, 这⾥也不⽤去管, 只有1点是明确的, 只要n-1>1 那么这个过程肯定需要C塔来中转, ⽽且肯定可以化为求hanoi_m(x,x,x, n-2).
假如n-1=1? 就直接move(A,B)就ok了, 这就是出⼝啊.
3.4  第⼆步, 将A上⾯的最后的(最⼤的)盘⼦移动到C塔 move(A,C)
因为现在A塔了只有1个最⼤盘⼦n了啊, 所以⽆需借助B塔, 直接move(A,C)搞定
如下图:
注意现在还没完成哦
3.4  第三步, 将B上⾯的所有盘⼦(n-1)个盘⼦借助A塔移动到C塔 hanoi(B,A,C,n-1)
因为C塔的盘⼦⽐B塔的所有盘⼦都⼤, 所以是可以忽略掉C盘的那个最⼤的盘⼦的, 理解这个也很重要啊.
这个函数实现就是 hanoi(B,A,C,n-1)
如图:
搞掂完成了...
3.5  总结及伪算法:
经过上⾯的图解, 我们知道hanoi(n) 与hanoi(n-1)的关系了, 可以分成三步啊
伪算法就是:
1. hanoi_m(A,B,C,n){
2. if (n==0){
3. move(A,C);
4. }
5. hanoi_m(A,C,B,n-1);
6. move(A,C);
7. hanoi_m(B,A,C,n-1);
8. }
看看这个函数, ⾃⼰调⽤了⾃⼰, ⽽且规模不断在减少, 还有1个明确的出⼝, 标准的递归函数啊.再看看本⽂开始那个函数, 是不是能理解了
然⽽ 真正的代码实现没那么简单,  但是起码逻辑已经清楚了.
4. 1个静态栈(数组内核)的容器的c语⾔代码实现
假设我们可以⽤类似下⾯的代码来定义3个栈, 和调⽤压栈和出栈函数, 就很⽅便了.
1. //declare a stucks
2. stuck A = new stuck;
3.
4. //push
5. A->push(1); //push element int "1" into the stuck
6.
7. //pop
8. int i;
9. A->pop(&i) //pop the top element, and assign the value to variable i
10.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。