河内塔迭代解决方案问题

本文关键字：问题 解决方案 迭代 内塔 | 更新日期: 2023-09-27 18:19:19

我遇到了河内塔谜题的迭代解决方案。由于这是一项大学任务，我们已经得到了伪代码来执行。

Towers(number, src, dest, alt)
begin
    push { number, src, dest, alt }
    while NOT stack.empty
        pop { number, src, dest, alt }
        if number = 1
            print "Move 1 disc from " + src + " to " + dest
        else
            push { number – 1, alt, dest, src }
            push { 1, src, dest, alt }
            push { number – 1, src, alt, dest }
        end-if
    end-while
end

这是我在c#中的尝试:

static void TowersIterative(uint number, char src, char dest, char alt)
{
    Stack<Move> _Stack = new Stack<Move>();
    _Stack.Push(new Move(number, src, dest, alt));
    while (_Stack.Count != 0)
    {
        _Stack.Pop();
        if (number == 1)
            Console.WriteLine("Move one disc from {0} to {1}", src, dest);
        else
        {
            _Stack.Push(new Move(number - 1, alt, dest, src));
            _Stack.Push(new Move(1, src, dest, alt));
            _Stack.Push(new Move(number - 1, src, alt, dest));
        }
    }
}

目前move类没有发生什么。

class Move
{
    private char _Src, _Alt, _Dest;
    private uint _Number;
    public Move(uint number, char src, char dest, char alt)
    {
        _Number = number;
        _Src = src;
        _Alt = alt;
        _Dest = dest;
    }
}

这是number = 3, src = 'L', alt = 'M'和dest = 'R'的期望输出示例:

将一个磁盘从L移到M
将一个磁盘从L移到R
从M移到R

目前，TowersIterative方法中的while循环是无限循环的，number变量永远不等于1。

河内塔迭代解决方案问题

问题是，您忽略了从堆栈中弹出的数据，而是使用参数，就好像它们已经弹出一样。我建议将TowersIterative分成两部分来避免这种危险:

class Move
{
    public char Src { get; private set; }
    public char Alt { get; private set; }
    public char Dest { get; private set; }
    public uint Number { get; private set; }
    public Move(uint number, char src, char dest, char alt)
    {
        Number = number;
        Src = src;
        Alt = alt;
        Dest = dest;
    }
}
public static class Hanoi
{
    static void TowersIterative(uint number, char src, char dest, char alt)
    {
        Stack<Move> _Stack = new Stack<Move>();
        _Stack.Push(new Move(number, src, dest, alt));
        TowersIterative(_Stack);
    }
    private static void TowersIterative(Stack<Move> _Stack)
    {
        while (_Stack.Count != 0)
        {
            var move = _Stack.Pop();
            if (move.Number == 1)
                Console.WriteLine("Move one disc from {0} to {1}", move.Src, move.Dest);
            else
            {
//              _Stack.Push(new Move(number - 1, alt, dest, src));
                _Stack.Push(new Move(move.Number - 1, move.Alt, move.Dest, move.Src));
//              _Stack.Push(new Move(1, src, dest, alt));
                _Stack.Push(new Move(1, move.Src, move.Dest, move.Alt));
//              _Stack.Push(new Move(number - 1, src, alt, dest));
                _Stack.Push(new Move(move.Number - 1, move.Src, move.Alt, move.Dest));
            }
        }
    }
}

我将Move中的字段更改为公共只读属性，因为这通常被认为是良好的编程风格

这是因为number变量有两种含义——一种是方法参数名，但伪代码的目的是将其用作从堆栈中弹出的元素的number属性的值。这应该可以工作:

static void TowersIterative(uint number, char src, char dest, char alt)
{
    var stack = new Stack<Move>();
    stack.Push(new Move(number, src, dest, alt));
    while (stack.Count != 0)
    {
        var move = stack.Pop();
        if (move.Number == 1)
            Console.WriteLine("Move one disc from {0} to {1}", move.Src, move.Dest);
        else
        {
            stack.Push(new Move(move.Number - 1, move.Alt, move.Dest, move.Src));
            stack.Push(new Move(1, move.Src, move.Dest, move.Alt));
            stack.Push(new Move(move.Number - 1, move.Src, move.Alt, move.Dest));
        }
    }
}

当然还要为Move类添加适当的属性:

class Move
{
    public uint Number { get; private set; }
    public char Src { get; private set; }
    public char Dest { get; private set; }
    public char Alt { get; private set; }
    public Move(uint number, char src, char dest, char alt)
    {
        this.Number = number;
        this.Src = src;
        this.Alt = alt;
        this.Dest = dest;
    }
}

我还重命名了变量，以符合常用的约定。查看工作演示

相关文章：