5

有人可以就如何创建 GetEnumerator() 的递归版本给我建议吗？著名的河内塔问题可以作为一个例子，与我遇到的实际问题相当。显示一堆高度为 n 的磁盘的所有移动的简单算法是：

void MoveTower0 (int n, Needle start, Needle finish, Needle temp)
{
  if (n > 0)
  {
    MoveTower0 (n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTower0 (n - 1, temp, finish, start);
  }
}

我真正想做的是设置一个实现 IEnumerable 的类 HanoiTowerMoves ，它使我能够迭代所有移动，如下所示：

foreach (Move m in HanoiTowerMoves) Console.WriteLine (m);

GetEnumerator() 实现的第一步似乎摆脱了 MoveTower 参数。这可以通过使用堆栈轻松完成。我还介绍了一个 Move 类，它将参数组合成一个变量。

class Move
{
  public int N { private set; get; }
  public Needle Start { private set; get; }
  public Needle Finish { private set; get; }
  public Needle Temp { private set; get; }

  public Move (int n, Needle start, Needle finish, Needle temp)
  {
    N = n;
    Start = start;
    Finish = finish;
    Temp = temp;
  }

  public override string ToString ()
  {
    return string.Format ("Moving disk from {0} to {1}", Start, Finish);
  }
}

现在 MoveTower 可以改写如下：

void MoveTower1 ()
{
  Move m = varStack.Pop ();

  if (m.N > 0)
  {
    varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
    MoveTower1 ();
    Console.WriteLine (m);
    varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
    MoveTower1 ();
  }
}

此版本必须按如下方式调用：

varStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
MoveTower1 ();

迈向可迭代版本的下一步是实现该类：

class HanoiTowerMoves : IEnumerable<Move>
{
  Stack<Move> varStack;
  int n; // number of disks

  public HanoiTowerMoves (int n)
  {
    this.n = n;
    varStack = new Stack<Move> ();
  }

  public IEnumerator<Move> GetEnumerator ()
  {
    // ????????????????????????????  }

  // required by the compiler:
  IEnumerator IEnumerable.GetEnumerator ()
  {
    return GetEnumerator ();
  }
}

现在对我来说最大的问题是：GetEnumerator() 的主体是什么样的？有人可以为我解开这个谜吗？

下面是我创建的控制台应用程序的 Program.cs 代码。

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

/* Towers of Hanoi
 * ===============
 * Suppose you have a tower of N disks on needle A, which are supposed to end up on needle B.
 * The big picture is to first move the entire stack of the top N-1 disks to the Temp needle,
 * then move the N-th disk to B, then move the Temp stack to B using A as the new Temp needle.
 * This is reflected in the way the recursion is set up.
 */

namespace ConsoleApplication1
{
  static class main
  {
    static void Main (string [] args)
    {
      int n;
      Console.WriteLine ("Towers of Hanoi");

      while (true)
      {
        Console.Write ("\r\nEnter number of disks: ");

        if (!int.TryParse (Console.ReadLine (), out n))
        {
          break;
        }

        HanoiTowerMoves moves = new HanoiTowerMoves (n);
        moves.Run (1); // algorithm version number, see below
      }
    }
  }

  class Move
  {
    public int N { private set; get; }
    public Needle Start { private set; get; }
    public Needle Finish { private set; get; }
    public Needle Temp { private set; get; }

    public Move (int n, Needle start, Needle finish, Needle temp)
    {
      N = n;
      Start = start;
      Finish = finish;
      Temp = temp;
    }

    public override string ToString ()
    {
      return string.Format ("Moving disk from {0} to {1}", Start, Finish);
    }
  }

  enum Needle { A, B, Temp }

  class HanoiTowerMoves : IEnumerable<Move>
  {
    Stack<Move> varStack;
    int n;            // number of disks

    public HanoiTowerMoves (int n)
    {
      this.n = n;
      varStack = new Stack<Move> ();
    }

    public void Run (int version)
    {
      switch (version)
      {
        case 0: // Original version
          MoveTower0 (n, Needle.A, Needle.B, Needle.Temp);
          break;

        case 1: // No parameters (i.e. argument values passed via stack)
          varStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
          MoveTower1 ();
          break;

        case 2: // Enumeration
          foreach (Move m in this)
          {
            Console.WriteLine (m);
          }

          break;
      }
    }

    void MoveTower0 (int n, Needle start, Needle finish, Needle temp)
    {
      if (n > 0)
      {
        MoveTower0 (n - 1, start, temp, finish);
        Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
        MoveTower0 (n - 1, temp, finish, start);
      }
    }

    void MoveTower1 ()
    {
      Move m = varStack.Pop ();

      if (m.N > 0)
      {
        varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
        MoveTower1 ();
        Console.WriteLine (m);
        varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
        MoveTower1 ();
      }
    }

    public IEnumerator<Move> GetEnumerator ()
    {
      yield break; // ????????????????????????????
    }

    /*
      void MoveTower1 ()
      {
        Move m = varStack.Pop ();

        if (m.N > 0)
        {
          varStack.Push (new Move (m.N - 1, m.Start, m.Temp, m.Finish));
          MoveTower1 ();
          Console.WriteLine (m); ? yield return m;
          varStack.Push (new Move (m.N - 1, m.Temp, m.Finish, m.Start));
          MoveTower1 ();
        }
      }
    */

    // required by the compiler:
    IEnumerator IEnumerable.GetEnumerator ()
    {
      return GetEnumerator ();
    }
  }
}
4

3 回答 3

12

你的方法很好，但我认为你有点过度思考这个问题。让我们退后一步。你有一个递归算法：

void MoveTowerConsole (int n, Needle start, Needle finish, Needle temp) 
{   
  if (n > 0)   
  {
    MoveTowerConsole (n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTowerConsole (n - 1, temp, finish, start);
  } 
}

该算法的输出是一堆控制台输出。假设您希望算法的输出是要输出到控制台的字符串序列。让我们推理一下这种方法会是什么样子。

首先，我们将重命名它。其次，它的返回类型不能为 void。它必须是IEnumerable<string>：

IEnumerable<string> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    MoveTower(n - 1, start, temp, finish);
    Console.WriteLine ("Moving disk from {0} to {1}", start, finish);
    MoveTower(n - 1, temp, finish, start);
  } 
}

这是正确的吗？不，我们没有返回任何东西，我们仍在向控制台倾倒。我们希望迭代器产生什么？我们希望迭代器产生：

  • 第一个递归步骤所需的所有移动
  • 目前的举动
  • 第二个递归步骤所需的所有移动

所以我们修改算法以产生那些：

IEnumerable<string> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    foreach(string move in MoveTower(n - 1, start, temp, finish))
        yield return move;
    yield return string.Format("Moving disk from {0} to {1}", start, finish);
    foreach(string move in MoveTower(n - 1, temp, finish, start))
        yield return move;
  } 
}

我们完成了！就这么简单。无需定义整个类即可将递归算法转换为递归枚举器；让编译器为您完成这项工作。

如果您想将其更改为枚举“移动”的方法，请执行以下操作：

IEnumerable<Move> MoveTower(int n, Needle start, Needle finish, Needle temp) 
{
  if (n > 0)   
  {
    foreach(Move move in MoveTower(n - 1, start, temp, finish))
        yield return move;
    yield return new Move(start, finish);
    foreach(Move move in MoveTower(n - 1, temp, finish, start))
        yield return move;
  } 
}

现在，我会根据效率来批评这段代码。通过以这种方式制作递归枚举器，您正在做的是构建一个 n 枚举器链。当您需要下一项时，顶部枚举器调用下一个枚举器调用下一个枚举器......向下到底部，n 深。所以现在每一步实际上需要 n 步才能完成。出于这个原因，我倾向于在不递归的情况下解决问题。

练习：重写上面的迭代器块，使其完全不进行递归。您使用显式堆栈的解决方案是朝着正确方向迈出的一步，但它仍然会递归。你可以调整它以便不进行递归吗？

如果您一心想编写一个实现的类，IEnumerable<Move>那么您可以直接修改上面的代码：

class MoveIterator : IEnumerable<Move>
{
    public IEnumerator<Move> GetEnumerator()
    {
        foreach(Move move in MoveTower(whatever))
            yield return move;
    }

您可以使用 yield return 来实现返回 enumerator或enumerable的方法。

于 2012-01-11T16:04:32.013 回答
1

您的非递归解决方案很好——构建下推自动机（本质上是带有堆栈的状态机）是构建递归解决方案迭代版本的标准技术。事实上，这与我们为迭代器和异步块生成代码的方式非常相似。

但是，在这种特定情况下，您不需要拉出带有开关和当前状态的下推自动机的重型机械。你可以这样做：

IEnumerable<Move> MoveTowerConsole (int size, Needle start, Needle finish, Needle temp) 
{   
  if (size <= 0) yield break;
  var stack = new Stack<Work>();
  stack.Push(new Work(size, start, finish, temp));
  while(stack.Count > 0)
  {
    var current = stack.Pop();
    if (current.Size == 1) 
      yield return new Move(current.Start, current.Finish);
    else
    {
       // Push the work in the *opposite* order that it needs to be done.
       stack.Push(new Work(current.Size - 1, current.Temp, current.Finish, current.Start));
       stack.Push(new Work(1, current.Start, current.Finish, current.Temp));
       stack.Push(new Work(current.Size - 1, current.Start, current.Temp, current.Finish));

     }
}

您已经确切地知道在当前递归步骤之后需要做什么工作，因此无需在开关周围反弹以将这三位工作放在堆栈上。只需为给定步骤一次将所有工作排队。

于 2012-01-12T16:26:45.590 回答
0

非递归版本：

// Non-recursive version -- state engine
//rta.Push (State.Exit);
//parameters.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
//MoveTower3 ();

enum State { Init, Call1, Call2, Rtrn, Exit }

{  
  ...

  #region Non-recursive version -- state engine
  static void MoveTower3 ()
  {
    State s = State.Init;
    Move m = null;

    while (true)
      switch (s)
      {
        case State.Init:
          m = moveStack.Pop ();
          s = (m.n <= 0) ? State.Rtrn : State.Call1;
          break;
        case State.Call1:
          rta.Push (State.Call2); // where do I want to go after the call is finished
          moveStack.Push (m);    // save state for second call
          moveStack.Push (new Move (m.n-1, m.start, m.temp, m.finish)); // parameters
          s = State.Init;
          break;
        case State.Call2:
          m = moveStack.Pop ();  // restore state from just before first call
          Console.WriteLine (m);
          rta.Push (State.Rtrn);
          moveStack.Push (new Move (m.n-1, m.temp, m.finish, m.start));
          s = State.Init;
          break;
        case State.Rtrn:
          s = rta.Pop ();
          break;
        case State.Exit:
          return;
      }
  }
  #endregion

  #region Enumeration
  static IEnumerable<Move> GetEnumerable (int n)
  {
    Stack<Move> moveStack = new Stack<Move> ();
    Stack<State> rta = new Stack<State> (); // 'return addresses'
    rta.Push (State.Exit);
    moveStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
    State s = State.Init;
    Move m = null;

    while (true)
      switch (s)
      {
        case State.Init:
          m = moveStack.Pop ();
          s = (m.n <= 0) ? State.Rtrn : State.Call1;
          break;
        case State.Call1:
          rta.Push (State.Call2); // where do I want to go after the call is finished
          moveStack.Push (m);    // save state for second call
          moveStack.Push (new Move (m.n-1, m.start, m.temp, m.finish)); // parameters
          s = State.Init;
          break;
        case State.Call2:
          m = moveStack.Pop ();  // restore state from just before first call
          yield return m;
          rta.Push (State.Rtrn);
          moveStack.Push (new Move (m.n-1, m.temp, m.finish, m.start));
          s = State.Init;
          break;
        case State.Rtrn:
          s = rta.Pop ();
          break;
        case State.Exit:
          yield break;
      }
  }
  #endregion
}
于 2012-01-12T07:28:20.657 回答