c# 实现汉诺塔游戏

C#实现汉诺塔游戏攻略

思路分析

在讲解C#实现汉诺塔游戏之前，我们先来了解一下它的思路。

汉诺塔游戏是一种经典的递归算法，基本思路如下：

假设有A、B、C三条柱子，A柱子上有n个不同大小的盘子，盘子大小由下到上依次变小，现在要求将A柱子上的盘子移动到C柱子上，移动过程中可以借助B柱子，但每次只能移动最上面的盘子，并且大盘子不能放在小盘子上面。

例如，当有三个盘子时，移动过程如下：

1. 将A柱子上的1、2号盘子（此时2号盘子在1号盘子上面）移动到B柱子上。
2. 将A柱子上的3号盘子移动到C柱子上。
3. 将B柱子上的2号盘子移动到C柱子上。

递归思路就是把n个盘子看作两个盘子，即第一个和剩下的n-1个盘子，然后递归地解决子问题。

代码示例

下面是C#代码示例：

using System;

class Hanoi
{
    public static void Move(int n, char from, char to, char via)
    {
        if (n == 1)
        {
            Console.WriteLine("{0} -> {1}", from, to);
        }
        else
        {
            Move(n-1, from, via, to);
            Console.WriteLine("{0} -> {1}", from, to);
            Move(n-1, via, to, from);
        }
    }

    static void Main(string[] args)
    {
        int n = 3;
        Move(n, 'A', 'C', 'B');
    }
}

代码中，Move()方法是递归的核心代码，n表示这n个盘子，from表示开始的柱子，to表示目标柱子，via表示中介柱子。

我们可以把盘子的个数设为3，然后调用Move()方法实现汉诺塔游戏。

输出如下：

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

另一种实现方式

还有一种实现汉诺塔游戏的方式是使用栈。当我们调用Move()方法时，创建一个栈，同时将第一个盘子入栈，然后开始循环：

1. 将当前栈顶盘子从A柱子移动到C柱子。
2. 如果当前盘子不是最后一个，则将其上面的盘子入栈。
3. 如果栈不为空，则将栈顶盘子移动到B柱子。
4. 重复步骤1至3，直到所有盘子都移动到了目标柱子C。

下面是使用栈实现汉诺塔游戏的代码示例：

using System;
using System.Collections.Generic;

class Hanoi
{
    public static void Move(int n, char from, char to, char via)
    {
        Stack<int> s = new Stack<int>();

        // 将第一个盘子入栈
        s.Push(n);

        while(s.Count > 0)
        {
            // 当前盘子
            int curr = s.Peek();

            // 直接移到目标柱子
            if (curr == 1)
            {
                Console.WriteLine("{0} -> {1}", from, to);
                s.Pop();
                continue;
            }

            // 将上面的盘子入栈
            s.Push(curr-1);
            s.Push(curr-1);

            // 如果栈不空，则将其上面的盘子移到中介柱子
            if (s.Count > 2)
                Console.WriteLine("{0} -> {1}", from, via);
            else
                Console.WriteLine("{0} -> {1}", from, to);

            // 最后的盘子移到目标柱子
            if (s.Count > 2)
                s.Pop();
            else
                Console.WriteLine("{0} -> {1}", from, to);
        }
    }

    static void Main(string[] args)
    {
        int n = 3;
        Move(n, 'A', 'C', 'B');
    }
}

输出如下：

A -> B
A -> C
B -> C
A -> B
C -> A
C -> B
A -> B

总结

以上就是C#实现汉诺塔游戏的两种方式。第一种方式是递归实现，第二种方式是使用栈实现。无论哪种方式，都是基于递归思想的。除此之外，还可以使用非递归的方法来实现汉诺塔游戏，这里就不再赘述。