【算法笔记】汉诺塔问题

起因是某天刷b站，想起来自己还没把up主离忧夏天的C#数据结构看完，结果意外发现了另一位up主木子喵neko，虚拟up+可爱声音讲解数据结构与算法，于是跟着看了。我自身对知识有比较强的分享欲和记录欲（因为我发现我不记笔记总是会忘掉），于是记录一下木子喵算法小课堂第一课：汉诺塔问题。用我最熟悉的C#语言来写。

问题介绍

汉诺塔问题是一个经典的递归问题，源自一个古老的印度传说。在这个问题中，我们有三根柱子和一系列不同大小的圆盘，这些圆盘最初按大小顺序堆叠在一根柱子上。目标是将所有圆盘移动到另一根柱子上，遵循两个规则：一次只能移动一个圆盘，且在移动过程中较大的圆盘不能放在较小的圆盘上面。 ***

解题思路

这道题主要思想还是递归（说实话我现在递归还学得挺烂的），我们把柱子做好标记：A柱是起始柱，B柱是中间柱，C柱是目标柱。
形象的图片 我们假设有n个圆盘，从上到下编号为1-n,我们先假设我们通过某种手段，把上面的n-1个圆盘搬到了B柱子，接下来我们把A中剩下的一个盘子搬到了C
那么现在的情况是什么？B柱变成起始柱了，A柱变成中间柱了，按照上面的方法，我们把n-2个圆盘移动到了A柱，B柱剩下的圆盘移动到了C柱，于是A柱又变成起始柱、B柱变成中间柱...以此类推，最后把n个圆盘都搬完了。
最后越搬越少，只剩下一个圆盘时，把这个圆盘放到C柱就好了。 ***

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleDesktop
{
    class Program
    {
        static void Main(string[] args)
        {
            HanoiTower hanoi = new HanoiTower();
            int sum = hanoi.hanoiTowerSum(3, 'a', 'b', 'c');
            Console.WriteLine("总移动次数：{0}", sum);
        }
    }

    class HanoiTower
    {
        private void hanoiMove(char x, char y)
        {
            Console.WriteLine("{0} -> {1}", x, y);
        }

        public int hanoiTowerSum(int cnt, char a, char b, char c)
        {
            if(cnt == 1)
            {
                hanoiMove(a, c);
                return 1;
            }
            else
            {
                int sum = 0;
                sum += hanoiTowerSum(cnt - 1, a, c, b);		//步骤1
                hanoiMove(a, c); sum += 1;					//步骤2
                sum += hanoiTowerSum(cnt - 1, b, a, c);		//步骤3

                return sum;
            }
        }
    }
}