有人可以給我建議如何創建一個遞歸版本的GetEnumerator()? 衆所周知的Towers of Hanoi problem可能會作爲一個例子,可以與我的實際問題相媲美。一個簡單的算法,以示對高n個磁盤組成的堆疊中的所有動作是:C#如何使遞歸版本的GetEnumerator()
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參數組合成單個變量的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可以如下改寫:
varStack.Push (new Move (n, Needle.A, Needle.B, Needle.Temp));
MoveTower1();
朝着一個迭代版本的下一步是實現類:
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();
}
}
如下這個版本必須調用:
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();
}
}
}
我不明白遞歸調用GetEnumerator的意義。只需編寫一個遞歸函數,即調用這個方法,並不難。 – 2012-01-11 15:43:45