c#汉诺塔的递归算法与解析
从左到右 A B C 柱 大盘子在下, 小盘子在上, 借助B柱将所有盘子从A柱移动到C柱, 期间只有一个原则: 大盘子只能在小盘子的下面.
如果有3个盘子, 大中小号, 越小的越在上面, 从上面给盘子按顺序编号 1(小),2(中),3(大), 后面的原理解析引用这里的编号.
小时候玩过这个游戏, 基本上玩到第7个,第8个就很没有耐心玩了,并且操作的动作都几乎相同觉得无聊. 后来学习编程, 认识到递归, 用递归解决汉诺塔的算法也是我除了简单的排序算法后学习到的第一种算法.
至于递归,简单来说就是方法内部自己调用自己, 同时也一定有一个结束点. 如果对方法调用栈了解的话,其实是很容易理解方法的调用过程的, 就是从主线程开始调用方法进行不停的压栈和出栈操作. 方法的调入就是将方法压入栈中, 方法的结束就是方法出栈的过程, 这样保证了方法调用的顺序流. 如果跟踪递归的调用情况会发现也是如此, 到最后一定是这个方法最后从栈中弹出回到主线程, 并且结束.
栈的特点:先进后出。 比如一个方法 A 自己调用自己, 我用编号区分一下进栈过程:
A -> A(1) -> A(2) -> A(3)
在A(3)时满足某种条件得以退出, 回到 A(2), A(2)结束回到A(1), 再回到A, 出栈过程:
A(3) -> A(2) -> A(1) -> A
对于递归,还有一个形象的认识,就是我小时候家里有一个柜子, 柜子两端都是玻璃, 头伸进柜子看一面镜子,会看到镜子里还有镜子, 然后镜子里还有镜子, 但和递归的特点不同的是这镜子的反射是没有尽头的, 只要眼睛一直能看到底的话.
了解完递归后, 再回头来看如何用递归的方式解决汉诺塔的问题.
案例 1 - 假设只有一个盘子的时候, 盘子数量 N=1
只有一个步骤 将第1个盘子从A移动到C, 为了对比方便我这样来描述这个步骤:
步骤 盘子编号 从柱子移动 移动到柱子
1 1 A C
案例 2 - 如果有两个盘子, 盘子数量 N = 2
步骤 盘子编号 从柱子移动 移动到柱子
1 1 A B
2 2 A C
3 1 B C
案例 3 - 如果有三个盘子, 盘子数量 N = 3
步骤 盘子编号 从柱子移动 移动到柱子
1 1 A C
2 2 A B
3 1 C B
4 3 A C
5 1 B A
6 2 B C
7 1 A C
如何找出盘子移动的规律 ?
我们要做的最重要的一件事情就是永远要把最底下的一个盘子从 A 移动到 C
看看上面从1个盘子的移动到3个盘子的移动, 在移动记录中,当盘子的编号和盘子数量相同的时候他们的步骤都是从A移动到C (看加粗的部分),其它的步骤对等.
再观察第3个案例中的第 1-3 步 和 第 5-7步
第 1-3 步 目的是从 A 移动到 B 如果我们把 B 当作终点, 那么这里的第 1-3 步理解起来和 第2个案例的三个步骤完全相同, 都是通过一个柱子来移动,和第2个案例比起来在后面加括号来表示
1 1 A C ( A -> B)
2 2 A B ( A -> C)
3 1 C B ( B -> C)
总结:将盘子B变成C即可.
第 5-7 步 目的是从 B 移动到 C 如果我们把 C 当作终点, 那么这里的 5-7 步理解起来和上面也是一样的, 和第2个案例的三个步骤也完全相同.和第2个案例比起来就是:
5 1 B A ( A -> B)
6 2 B C ( A- > C)
7 1 A C ( B -> C)
总结: 将盘子B变成A即可
根据这个演示可以明确几点规律:
1. 当盘子只有一个的时候,只有一个动作 从 A 移动到 C 即结束.
2. 当有N个盘子的时候, 中间的动作都是从 A 移动到 C, 那么表示最下面的第N个盘子移动完毕
3. 中间动作之上都可以认为是: 从 A 移动到 B
4. 中间动作之下都可以认为是: 从 B 移动到 C
2,3,4 可以表示为
1 1 A B
2 2 A C
3 1 B C
这种结构一直在重复进行,C#不太熟悉,试着写写,就有了以下代码:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure
{
class HanoiTower
{
public void MoveDisk(int DiskQuantity,string PositionA, string PositionB, string PositionC)
{
// If there's only one disk, then end.
if (DiskQuantity == 1)
{
Console.WriteLine("Move disk from position {0} to {1}.", PositionA, PositionC);
// Must return
return;
}
else
{
// Step 1 - Change B to C (A --> B)
MoveDisk(DiskQuantity - 1, PositionA,PositionC,PositionB);
// Step 2 - No changes (A --> C)
MoveDisk(1, PositionA, PositionB, PositionC);
// Step 3 - Change B to A (A --> C)
MoveDisk(DiskQuantity - 1, PositionB, PositionA, PositionC);
}
}
static void Main(string[] args)
{
HanoiTower hanoi = new HanoiTower();
Console.WriteLine("Please input Disk Quantity:");
int DiskQuantity = Convert.ToInt32(Console.ReadLine());
hanoi.MoveDisk(DiskQuantity, "A", "B", "C");
Console.ReadKey();
}
}
}
结合上面的分析,最重要的就是这里的3步交换动作, 中间从 A到C的动作是最底层盘子的最终操作.
// Step 1 - Change B to C (A --> B)
MoveDisk(DiskQuantity - 1, PositionA,PositionC,PositionB);
// Step 2 - No changes (A --> C)
MoveDisk(1, PositionA, PositionB, PositionC);
// Step 3 - Change B to A (A --> C)
MoveDisk(DiskQuantity - 1, PositionB, PositionA, PositionC);
至于第1个参数为什么是DiskQuantity - 1,或者1 大家再回到上面看看是不是所有的步骤都是.. 1. 1,2,1. 1,2,1,3,1,2,1 这种以盘子数对称的结构,而它前后都是重复1,2,1 的过程.
相关文章
- 这篇文章主要介绍了c# 实现汉诺塔游戏的示例,帮助大家更好的理解和使用c# 编程语言,感兴趣的朋友可以了解下...2020-12-08
- 之前的文章,我们给大家分享了不少汉诺塔算法的实现语言,包括C、c++、java、python等,今天我们就来使用go语言来实现一下,需要的小伙伴来参考下吧。...2020-05-07
- 这篇文章主要介绍了C++基于递归算法解决汉诺塔问题与树的遍历功能,简单描述了递归算法的原理,并结合实例形式分析了基于递归算法解决汉诺塔问题与数的遍历相关操作技巧,需要的朋友可以参考下...2020-04-25
- 这篇文章主要给大家介绍了关于C语言汉诺塔的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-08
- 这篇文章主要介绍了C#解决汉诺塔问题DEMO,本文直接给出实现代码,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了C++递归算法实例代码,还是比较不错的,运用了递归算法解决相关问题,这里分享给大家,需要的朋友可以参考下。...2020-04-25
- 汉诺塔本是C语言开门就学的东西,简单的汉诺塔问题解法代码...2020-04-25
- c#汉诺塔的递归算法与解析,需要的朋友可以参考一下...2020-06-25
- 个人觉得汉诺塔这个递归算法比电子老鼠的难了一些,不过一旦理解了也还是可以的,其实网上也有很多代码,可以直接参考。记得大一开始时就做过汉诺塔的习题,但是那时代码写得很长很长,也是不理解递归的结果。今天重新来实现一下...2020-04-25
- 本文给大家分享的是一则使用vc++实现模拟汉诺塔效果的代码,代码实现起来很简单,主要是汉诺塔算法的思路要正确,正在练习汉诺塔的小伙伴也可以来看看,希望大家能够喜欢。...2020-04-25
C#用递归算法实现:一列数的规则如下: 1、1、2、3、5、8、13、21、34,求第30位数是多少
本文主要介绍三种方法,解决面试中常见的问题,求第30位数是多少的问题,希望能给大家一个参考。...2020-06-25- 这篇文章主要介绍了C#算法之全排列递归算法实例讲解,本文讲解了算法思路、算法代码实例、解决重复元素的排列问题等内容,需要的朋友可以参考下...2020-06-25
- 这篇文章我们九里讲讲C 语言基础实现青蛙跳台阶和汉诺塔问题,感兴趣的小伙伴可以参考下面文章的具体内容...2021-09-15
- 这篇文章主要介绍了二叉树前序遍历的非递归算法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了将文件夹下所有文件输出到日志文件中,通过这个示例我们学习一下递归算法的使用方法...2020-06-25
- 快速排序由C.A.R发明,它依据中心元素的值,利用一系列递归调用将数据表划分成越来越小的子表。在每一步调用中,经过多次的交换,最终为中心元素找到最终的位置。...2020-06-25
- c语言 汉诺塔算法代码,需要的朋友可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ 实现汉诺塔的实例详解的相关资料,这里主要说明C++中数据结构的递归的应用,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用递归求第30位数的值,需要的朋友可以参考下...2020-06-25
- C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数...2020-04-25