C#中汉诺塔问题的递归解法

简介: 百度测试部2015年10月份的面试题之——汉诺塔。 汉诺塔就是将一摞盘子从一个塔转移到另一个塔的游戏,中间有一个用来过度盘子的辅助塔。 百度百科在此。 游戏试玩在此。 用递归的思想解决汉诺塔问题就是分为两种情况: 第一种情况是只有一个盘子的情况,也就是最基本的情况,这种情况下,直接将该盘子从原始塔转移到目标塔即可胜利; 第二种情况是右n个盘子的情况,也就是普遍情况,这种情况下,要将除了最底下的那个盘子以外的(n-1)个盘子从原始塔转移到辅助塔,再把最底下的那个盘子(第n个盘子)从原始塔转移到目标塔,最后将辅助塔的(n-1)个盘子从辅助塔转移到目标塔。

百度测试部2015年10月份的面试题之——汉诺塔。

汉诺塔就是将一摞盘子从一个塔转移到另一个塔的游戏,中间有一个用来过度盘子的辅助塔。

百度百科在此

游戏试玩在此

用递归的思想解决汉诺塔问题就是分为两种情况:

第一种情况是只有一个盘子的情况,也就是最基本的情况,这种情况下,直接将该盘子从原始塔转移到目标塔即可胜利;

第二种情况是右n个盘子的情况,也就是普遍情况,这种情况下,要将除了最底下的那个盘子以外的(n-1)个盘子从原始塔转移到辅助塔,再把最底下的那个盘子(第n个盘子)从原始塔转移到目标塔,最后将辅助塔的(n-1)个盘子从辅助塔转移到目标塔。

而第二种情况中(n-1)个盘子的问题又可以拆分成(n-2)个盘子和一个盘子的问题——

而(n-2)个盘子的问题又可以拆分成(n-3个情况)和一个盘子的问题——

……

最终可以拆分成(n-(n-1))个盘子的问题,也就是一个盘子的问题,这时候问题就变成了第一种情况——

将这个盘子从原始塔转移到目标塔即可。

以上就是递归的思想在解汉诺塔游戏中的应用,我们可以理解这种递归法为类似数学归纳法的逆向思维法:

数学归纳法是一种从问题最基本情况的求解过程通过找规律从而得出该问题普遍情况的求解过程的方法;

递归法是将对问题普遍情况的求解过程进行拆分,最后分解为对一种最基本情况的求解过程的方法。

通过递归法解决汉诺塔的移动顺序问题代码如下:

using System;

namespace HanoiTower
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = Int32.Parse(Console.ReadLine());
            Hanoi(n,"TowerA","TowerB","TowerC");
            Console.ReadLine();
        }

        private static void Hanoi(int n, string origin, string temp, string destination)
        {
            if (n == 1)
            {
                move(origin, destination);
            }
            else
            {
                Hanoi(n - 1, origin, destination, temp);
                move(origin, destination);
                Hanoi(n - 1, temp, origin, destination);
            }
        }

        private static void move(string origin, string destination)
        {
            Console.WriteLine("Move the plate from " + origin + " to " + destination);
        }
    }
}

运行结果如下(以三个盘子的情况为例,大家可以去游戏中操作来验证解的正确性):

相关文章
|
6月前
|
算法 C#
C#递归详解
C#递归详解
48 0
|
存储 算法 C#
【查找算法】二分查找(C# + 递归、非递归和变种形式)
本文主要介绍二分查找算法,通过图片解析每一次查找的情况。代码通过C#实现,分别有递归、非递归和变种三种形式。其中变种主要**解决数组出现重复数据**的问题。最后,我们还分析了二分查找的局限性。
【查找算法】二分查找(C# + 递归、非递归和变种形式)
|
算法 C#
【愚公系列】2021年11月 C#版 数据结构与算法解析(递归)
【愚公系列】2021年11月 C#版 数据结构与算法解析(递归)
116 0
【愚公系列】2021年11月 C#版 数据结构与算法解析(递归)
|
C# 机器学习/深度学习
|
C# 机器学习/深度学习
C#中八皇后问题的递归解法——N皇后
百度测试部2015年10月份的面试题之——八皇后。 八皇后问题的介绍在此。以下是用递归思想实现八皇后-N皇后。 代码如下: using System;using System.Collections.
1194 0
|
程序员 C#
.net c# 正则表达式 平衡组/递归匹配
原文 http://www.cnblogs.com/qiantuwuliang/archive/2011/06/11/2078482.html 平衡组/递归匹配 这里介绍的平衡组语法是由.Net Framework支持的;其它语言/库不一定支持这种功能,或者支持此功能但需要使用不同的语法。
1180 0