我們常常碰到需要動態調整迴圈層數的技巧,例如排列組合中的,不盡相異物之排列。
範例:2 相異物在 2 個位置的排列方式。(或者題意是 2 位元 2 進制計數)
程式碼:
private const int N = 2;//相異物數
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
Console.WriteLine(i.ToString() + j.ToString());
}
}
範例:2 相異物在 3 個位置的排列方式。(或者題意是 3 位元 2 進制計數)
程式碼:
private const int N = 2;//相異物數
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
for(int k = 0; k < N; k++)
{
Console.WriteLine(i.ToString() + j.ToString() + k.ToString());
}
}
}
由上面範例可知,若是 2 個相異物在 m 個位置的排列方式,就要有 m 個 for 迴圈。
然而迴圈數量是在撰寫程式時就要決定的,所以要如何讓迴圈數量隨著問題變化而變化呢?
下面介紹 2 種方法產生動態迴圈層數。
方法一:堆疊操作
演算法:
- 將堆疊設置為初始狀態(每個元素都是0)。
- 在每次迴圈開始時,將堆疊的內容轉換為字串,然後對其進行逆序操作,輸出堆疊的內容。
- 在內部迴圈中,將堆疊的頂部元素取出,進行加 1,如果結果小於 N,則將其重新放回堆疊中,並將其後面的元素設置為0。
- 如果堆疊中的元素全部取出,則操作結束。
程式碼:
Stack stack = new Stack();
for(int i=0;i 0)
{
int u = stack.Pop() + 1;
if(u < N)
{
stack.Push(u);
while(stack.Count < N) stack.Push(0);
break;
}
}
if (stack.Count == 0) break;
}
ppt 教學 (傳統迴圈與堆疊操作的比較)
方法二:遞迴操作
演算法:
參數:prefix 目前累積層數所代表的數字,m 表示目前的迴圈層數。
- 判斷層數是否滿足 N 層,是的話輸出累積的字串 prefix,並結束程式。
- 輸出 0 ~ N-1 字串累積到 prefix
- 遞迴呼叫並傳入累積後的 prefix 及 m+1 層。
ppt 教學 (傳統迴圈與遞迴操作的比較)
程式碼:
private const int N = 2;
static void Main(string[] args)
{
string prefix = "";
dynamicLoop(prefix, 0);
}
private static void dynamicLoop(string prefix, int m)
{
if (m == N)
{
Console.WriteLine(prefix);
return;
}
for (int j = 0; j < N; j++)
dynamicLoop(prefix + j.ToString(), m+1);
}
|