繳交時間：2018/10/5 (Fri.) 23:00 ==> 2018/10/9 (Tue.) 23:00 遲交三天以上不收件!

Requirement :

*Implement Permutation and Hanoi Tower using recursive function

For Permutation:

• 輸入整數 n ，產生 n 個英文字母。 (如：n=3, 排列 ABC)
• 輸入整數 k ，自第 k 字元開始排列。(如：n=4, k=2, output: ABCD, ABDC)
• 利用遞迴將 n 個字母自第 k 字元開始排列。
• 印出所有排列的組合，並能印出所有排列的交換步驟。
• 可參考範例程式 12.排列，或課本 程式1-5；並額外輸出必要的遞迴過程。

For Hanoi Tower :

• Input an integer n as number of disks
• Print the process of moving disks

Bonus :

1. 有 input 合理性檢測 (依題意，只接受合理的輸入, 不合理會跳出警告...等)

2. 程式註解

3. 可排列非 ABC... 之輸入字串

4. 其它...

The Representation and Manipulation of String/char [] in Permutations using C++ Builder

排列問題中字串資料的呈現與處理 (representation and manipulation)

1. 在 C 中各英文字元佔 1 byte，欲使用多個字元可用 char [] （字元陣列、字串）或 char * （指向字元陣列的指標）資料結構存放（對英文字元、符號 ... 沒有問題，但以 unicode 編碼的字符，如：中文字... 則不適用）。
2. char [] / char * 如何在 C++ Builder 中藉由 windows 元件輸入？

基於上述兩項考量，產生排列的輸入資料可由以下方法取得：

[1] 沿用 char *（不考慮輸入中文字；注意這即為「問題限制」的考慮）

[1.1] 在程式中靜態給定，例如在程式前面即宣告 ：（只能排列 ABCD...）

char list [9] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I'};

在對應呼叫 perm() 的 button 中：

k = StrToInt(Edit1->Text);

n = StrToInt(Edit2->Text);

perm( list, k, n ); // 傳入 list 陣列、起始註標 k與結束註標 n

至於 perm(~) 此 recursive function 則可在輸出時改寫如下：

void perm(char *list, int k, int n)

{ int i, tmp;

if (k == n-1)

{ String a = list; // Convert char * list to String a

a = a.SubString(1, n); // The first n characters of a

// a.SubString(1, n) ==> the n-char starting from a[1]

Form1->Memo1->Lines->Add(a+" ["+IntToStr(count++)+"]");

}

else

{ for (i=k; i<n; i++)

{ SWAP(list[k], list[i], tmp);

perm(list, k+1, n);

SWAP(list[k], list[i], tmp);

}

}

}

[1.2] 利用 windows 元件（如：Edit），在GUI中動態設定（彈性較大，可排列輸入的字串）：

在對應呼叫 perm() 的 button 中寫下：

char ch[100];

String a = Edit3->Text;

// for (i = 1; i <= a.Length(); i++)

// Memo2->Lines->Add("ch["+IntToStr(i)+"] = "+a[i]);

// Hint: String a starting from position 1 ending at a.Length()

for (i = 0; i < a.Length(); i++) ch[i] = a[i+1];

ch[i] = '\0'; // 字元陣列、字串的結尾

// 將讀入的 String a[1:a.Length()] 逐字存入 ch[0:a.Length()-1]

k = StrToInt(Edit4->Text); // 取得排列起點

n = Edit3->Text.Length(); // 取得字串長度、毋庸輸入

perm( ch, k, n );

[2] 改用 String （允許輸入中文字，放寬「問題限制」；與 windows 元件更貼近）

在對應呼叫 permStr() 的 button 中寫下：

in_string = Edit5->Text;

k = StrToInt(Edit6->Text);

n = in_string.Length(); // 取得字串長度、毋庸輸入

permStr( in_string, k+1, n );

如此一來 permStr(~) 此 recursive function 可在輸出時簡單得多：

void permStr(String in_string, int k, int n)

{ int i, tmp;

if (k == n) // 想想為何是 (k == n) 而非 (k == n-1)

Form1->Memo1->Lines->Add(in_string+" ["+IntToStr(count++)+"]");

else

{ for (i=k; i<=n; i++)

{ SWAP(in_string[k], in_string[i], tmp);

permStr(in_string, k+1, n);

SWAP(in_string[k], in_string[i], tmp);

}

}

}

Program Output ScreenShots (Permutations)

Output ScreenShots (Towers of Hanoi)

Reference :

https://en.wikipedia.org/wiki/Tower_of_Hanoi

https://en.wikipedia.org/wiki/Permutation

https://sites.google.com/site/sjdsifm/materials/program/towerofhanoi