Joh*_*ool 5 c# recursion ienumerable enumerator
有人可以给我关于如何创建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 ();
}
}
}
Eri*_*ert 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);
}
}
算法的输出是一堆控制台输出.假设您希望算法的输出是将要输出到控制台的字符串序列.让我们来看看这种方法会是什么样子.
首先,我们将重命名它.其次,它的返回类型不能无效.它必须是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来实现返回枚举器或枚举的方法.