使用递归在 C# 中解决汉内塔

Question

我遇到了汉诺塔问题，我从 wikipedia 那里读到了概念和解决它的递归方法，但我看不出我在执行上述步骤时遗漏了什么在维基百科中。

我在这里看到了很多例子，但我不希望我的程序打印这些步骤，我希望程序解决在 3 个集合之间移动 "discs" 的问题，在我的代码中我使用 3堆叠模拟钉子。

这是我当前的代码：

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var hs = new HanoiSolver(discs: 3);

        hs.Solve();

        Console.ReadKey();
    }
}

class HanoiSolver
{
    private int TotalDiscs { get; set; } = 0;
    private Stack<int> FirstPeg { get; set; } = new Stack<int>();
    private Stack<int> SecondPeg { get; set; } = new Stack<int>();
    private Stack<int> ThirdPeg { get; set; } = new Stack<int>();

    public HanoiSolver(int discs = 3)
    {
        TotalDiscs = discs;

        //Create list of items (discs)
        var discList = Enumerable.Range(1, TotalDiscs).Reverse();

        //Add items (discs) to first peg
        foreach (var d in discList)
        {
            FirstPeg.Push(d);
        }
    }

    public void Solve()
    {
        if (ThirdPeg.Count != TotalDiscs)
        {
            PrintPegs();

            //Move first item from firstpeg to secondpeg
            if (FirstPeg.Any())
            {
                var fp_f = FirstPeg.Pop();
                SecondPeg.Push(fp_f);
            }

            PrintPegs();

            //Move second item from firstpeg to thirdpeg
            if (FirstPeg.Any())
            {
                var fp_s = FirstPeg.Pop();
                ThirdPeg.Push(fp_s);
            }

            PrintPegs();

            //Move first item from secondpeg to thirdpeg
            if (SecondPeg.Any())
            {
                var sp_f = SecondPeg.Pop();
                ThirdPeg.Push(sp_f);
            }

            PrintPegs();

            Solve();
        }
    }

    private void PrintPegs()
    {
        var fp = FirstPeg.Select(x => x.ToString()).ToList();

        if (fp.Count < TotalDiscs)
        {
            fp.AddRange(Enumerable.Repeat(string.Empty, (TotalDiscs - fp.Count)));
        }

        var sp = SecondPeg.Select(x => x.ToString()).ToList();

        if (sp.Count < TotalDiscs)
        {
            sp.AddRange(Enumerable.Repeat(string.Empty, (TotalDiscs - sp.Count)));
        }

        var tp = ThirdPeg.Select(x => x.ToString()).ToList();

        if (tp.Count < TotalDiscs)
        {
            tp.AddRange(Enumerable.Repeat(string.Empty, (TotalDiscs - tp.Count)));
        }

        Console.WriteLine($"{"[First Peg]",10}" + $"{"[Second Peg]",10}" + $"{"[Third Peg]",10}");

        for (var i = 0; i < TotalDiscs; i++)
        {
            Console.WriteLine($"{fp[i],10}" +
                              $"{sp[i],10}" +
                              $"{tp[i],10}");
        }
    }
}

Answer 1

为了创建递归方法，您需要一个或多个递归结束的基本情况，然后进行一个或多个递归调用，将问题分解为更接近基本情况之一。对于汉诺塔，想法是将 n 个圆盘从 Peg A 移动到 Peg C 只是将 n-1 从 Peg A 移动到 Peg B，然后将第 n 个从 A 移动到 C，最后将 n-1 个圆盘从 C 移动到 B . 这最终会让你不移动光盘，这是你的基本情况。这可以通过递归方法非常简单地完成。

private static void Move(
    int discs, 
    Stack<int> fromPeg, 
    Stack<int> toPeg, 
    Stack<int> otherPeg)
{
    if (discs == 0)
    {
        return;
    }

    Move(discs - 1, fromPeg, otherPeg, toPeg);

    toPeg.Push(fromPeg.Pop());

    Move(discs -1, otherPeg, toPeg, fromPeg);
}

Answer 2

当您实施 TOH 时，这意味着您是 DS 和数据类型的新手。因此必须使用 DS 中不存在的数据类型，如堆栈和队列。所以下面的方法是使用数组。

使用系统；使用静态 System.Console；名称空间 TOH {

class Program
{
    // Problem statement
    //Create an array tower(a) containing all element in ascending order

    public static int[] towerSource = new int[] { 1, 3, 5,6,7,9,11,12,13,14,15,16,17};

    //solution statement
    //we have two more towers with same capacity, tower(b) as auxiliary and tower(c) as destination
    public static int[] towerAuxiliary;
    public static int[] towerDestination;

    public static void CreateTowers()
    {
        towerAuxiliary = new int[towerSource.Length];
        towerDestination = new int[towerSource.Length];
    }

    public static void Print(int[] tower)
    {
        for (int i = 0; i < tower.Length; i++)
            Write(tower[i].ToString());
        WriteLine("--------next run-------------");
    }       
    //start operation
    public static void TOH(int numberOfDisks, int[] source,int[] auxiliary,int[] destination)
    {
        //check if there is only one disk in source
        if(numberOfDisks == 1)
        {
            //move to destination and come out
            towerDestination[numberOfDisks-1] = towerSource[numberOfDisks-1];
            Print(towerDestination);
            return;
        }

        //move n-1 disks from source to auxiliary
        TOH(numberOfDisks - 1, towerSource, towerAuxiliary, towerDestination);
        towerDestination[numberOfDisks-1] = towerSource[numberOfDisks-1];

        //move nth disc from source to dest
        //this is being handeled by if condition

        //move n-1 disks from auxiliary to dest
        TOH(numberOfDisks - 1, towerAuxiliary, towerSource, towerDestination);

        return;
    }


    static void Main(string[] args)
    {
        CreateTowers();
        TOH(towerSource.Length, towerSource, towerAuxiliary, towerDestination);
    }
}

}

使用递归在 C# 中解决汉内塔

Solving Towers of Hanoi in C# using recursion

c#

recursion

towers-of-hanoi