Embedded Files
(Please read "scoring" before submission)
Due-date: 2019/10/2 (Wed.) 23:00 == > Extended: 10/9 23:00
Requirement :
Requirement :
*Implement (1) Permutation and (2) Towers of Hanoi using recursive functions
For Permutation:
輸入整數 n ，產生 n 個英文字母。 (如：n=3, 排列 ABC)
輸入整數 k ，自第 k 字元開始排列。(如：n=4, k=2, output: ABCD, ABDC)
利用遞迴將 n 個字母自第 k 字元開始排列。
印出所有排列的組合，並能印出所有排列的交換步驟。
可參考範例程式 12.排列，或課本 程式1-5；並額外輸出必要的遞迴過程。
For Towers of Hanoi :
Input an integer n as number of disks
Print the process of moving disks
Bonus :
Bonus :
1. 有 input 合理性檢測 (依題意，只接受合理的輸入, 不合理會跳出警告...等)
2. 程式註解
3. 可排列非 ABC... 之輸入字串
4. 其它...
The Representation and Manipulation of String/char [] in Permutations using C++ Builder
The Representation and Manipulation of String/char [] in Permutations using C++ Builder
排列問題中字串資料的呈現與處理 (representation and manipulation)
在 C 中各英文字元佔 1 byte，欲使用多個字元可用 char [] （字元陣列、字串）或 char * （指向字元陣列的指標）資料結構存放（對英文字元、符號 ... 沒有問題，但以 unicode 編碼的字符，如：中文字... 則不適用）。
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;
wchar_t tmp; // 定義 tmp 為 wchar_t 型態 (佔2 bytes) ，可存放中文字
if (k == n) // 想想為何是 (k == n) 而非 (k == n-1)
Form1->Memo1->Lines->Add(in_string+" ["+IntToStr(count++)+"]");
else
{ for (i=k; i<=n; i++) // Note: in_string 型態為 String; 而 in_string[i] 型態為 wchar_t
{ SWAP(in_string[k], in_string[i], tmp);
permStr(in_string, k+1, n);
SWAP(in_string[k], in_string[i], tmp);
}
}
}
Interface Design:
Interface Design:
Using Panel, Splitter, PageControl, ... in C++ Builder
Program Output ScreenShots (Permutations)
Program Output ScreenShots (Permutations)
Output ScreenShots (Towers of Hanoi)
Output ScreenShots (Towers of Hanoi)
Reference :
Reference :
Google Sites
Report abuse