<4D F736F F D20B8EAB054BEC7ACECA4A4A4DFA4ADA4EBA5F7B971A46CB3F82E646F63>

Size: px

Start display at page:

Download "<4D F736F F D20B8EAB054BEC7ACECA4A4A4DFA4ADA4EBA5F7B971A46CB3F82E646F63>"

腾段
5 years ago
Views:

1 資訊學科中心五月份電子報主題 : 遞迴觀念與河內塔問題視窗程式本文以 Visual C# 為例, 來說明常見的遞迴觀念, 以及在資訊科學領域中, 重要的河內塔問題之視窗程式撰寫, 此視窗程式可以在程式運作過程中, 看到圓盤搬移的過程, 有助於幫助同學們觀察河內塔的運作流程 Visual C# 簡介 VC# 語言起源於微軟的.NET 架構計畫, 當時微軟內部開發.NET 架構使用的程式語言, 就是 C# 語言的前身, 也可以說 C# 語言是為了.NET 架構而生的產物相對於一般校園或公司開發使用率較高的 C/C++ 或是 Java Basic 語言來說,C# 可以說是非常年輕的程式語言微軟在設計 C# 時, 廣納百川並擷取各既存語言的優點, 努力推動 C# 成為微軟新一代程式設計的標準語言從 C# 名稱上就可以看出來,C# 語言建立在 C/C++ 語法基礎上, 然而 C# 也兼有 Java 的精簡嚴謹以及 C++/Java 兩種語言都強調的物件導向概念,C# 一次包含了幾乎所有 C++ 與 Java 當中你能想到的特色與功能另外在.NET 架構的推動下, 微軟也透過 Visual C# 程式設計軟體讓 C# 同時擁有和 Visual Basic 一樣簡單方便的微軟視窗程式設計能力我們將 C# 語言的優點條列如下 : 1. 程式初學者或指導者常常在 C/C++ 語言以及 Visual Basic 語言之中猶豫,C# 語言正好兼有兩者的優點, 學 C# 可以讓我們透過 Visual C# 得到與 Visual Basic 一樣強大的 Windows 視窗程式開發能力, 由於語法與 C/C++ Java 幾乎相同, 也不用擔心以後與主流 C/C++ 語言 Java 語言的銜接問題 2. 對於已經有 C/C++ 或是 Java 基礎的程式設計師來說, 轉換到 C# 平台更是沒有障礙, 程式語法與使用概念幾乎相同, 使用 Visual C# 更大幅簡化了在 Windows 底下開發視窗程式的難度, 由於 Windows 與 C# 都出自於微軟之手, 使用 C# 較其他語言, 更能得到 Windows 作業系統的原生支援 3. C# 語言已經成為微軟的新一代開發標準, 如微軟新一代網頁設計方案 Web Developer 或是與 Adobe Flash 對抗的 Silverlight, 還有能夠設計 PC Xbox360 遊戲的 Game Studio 軟體套件,C# 語言都對這些微軟的新產品, 有著全面或甚至獨佔性的支援.NET 架構簡介.NET 架構 (.NET Framework) 是微軟從 Visual Studio 程式開發平台 2002 版後, 開始為 Windows 程式加入的軟體開發架構, 當時所使用的是.NET 1.0 版, 到了 2005 版時採用的版本是.NET 2.0 版, 至於目前最新 2010 版 Visual Studio 程式開發平台所採用的版本已經是.NET 4.0 版了

2 那麼.NET 架構到底是什麼? 我們可以將.NET 架構大略的比喻成一個精通各種語言的厲害廚師, 當饕客從世界各地前來想要品嚐美味, 他們可以直接用自己熟悉的母語和他溝通, 請廚師做出他們想要的菜在點菜的過程中, 饕客不需要知道廚師的烹調方法不需要知道使用何種廚具等瑣碎的事情, 饕客只需要告訴廚師想吃的是什麼,.NET 大廚便會把食物做出來上菜饕客可以透過自己熟悉的母語向廚師點菜, 換句話說, 也就是程式設計師可以使用自己熟悉的程式語言透過.NET 架構來寫程式在這個比喻中.NET 架構可以想像成廚師, 程式設計師可以想像成饕客, 母語可以想像成程式設計師所熟悉的各種程式語言在.NET 架構下, 程式從開發到執行的方式如下 : 1. 程式設計師可以使用任何熟悉的程式語言來開發.NET 程式, 如 :Visual C# Visual C++ Visual Basic... 等等開發軟體時, 無論是使用哪種語言, 都可以套用.NET 所提供方法庫中的各種內建功能 2. 程式開發完成後, 在編譯的過程, 會把不同語言所寫的程式, 轉為相同的中繼語言 (Common Intermediate Language) 3. 程式被執行時,.NET 架構中的共通語言執行環境 CLR(Common Language Runtime) 會根據執行環境來進行編譯, 將中繼語言一一轉換成電腦上可以執行的機器語言並且執行之由於所有程式碼的執行都由 CLR 負責執行, 故 CLR 在.NET 架構中同時還扮演著保護使用者電腦, 不受不當程式碼破壞的保全角色, 以及自動辨識不再使用的記憶體區塊並加以釋放 (Garbage Collection) 的清理者角色總結.NET 架構所帶來的好處主要有 : 1. 不同程式語言之間可以相容, 因為不同的程式語言, 都會被轉為相同的中繼語言 2. 提供非常多且實用的方法庫, 透過呼叫方法庫即可完成開發軟體時所需的常用功能, 不需重覆撰寫 3. 可以避免撰寫好的程式在不同的電腦中執行時, 會因為環境不同 ( 例如使用不同的 CPU 指令... 等 ) 而造成錯誤, 提高軟體的相容性因此透過.NET 架構, 程式撰寫者可以更加專注在程式的撰寫上, 處理真正的核心問題, 而不用再費心於開發程式的常用功能或處理程式的相容性問題上遞迴的觀念遞迴是數學函數當中一個重要的觀念, 許多數列或有階層性的問題, 都能解構成遞迴的形式, 這些問題的特色通常是連續的數字間之關係, 可以用一個函數來定義而在電腦程式當中, 遞迴方法的定義是 : 一個方法直接呼叫該方法本身 ( 在程式敘述內 ) 或間接的呼叫方法本身 ( 程式敘述內呼叫其他方法, 在該方法內又呼叫了原先的方法 ), 稱為遞迴

3 許多數學公式都以遞迴的方式定義, 例如 : 我們想計算 n!(n 階乘 ), 除了直接一個一個乘起來以外, 我們也可以利用 n! = n*(n-1)! 這一個公式來計算參考下面這個方法範例 : public static int factorial(int n) { if(n!= 1) return n * factorial(n - 1); return 1; 這個求階乘的方法 factorial, 就是以遞迴形式求 n 階乘解答的方法, 我們不直接以傳入的 n 做迴圈求解, 而是依照遞迴公式的形式 n! = n*(n-1)! 來求解只要 n 不等於 1, 我們就能依此公式拆解依照這個公式, 我們已知的是引數傳入的變數 n, 至於 (n-1)! 就呼叫另一次 factorial 方法求解, 這樣一層一層呼叫下去, 總會有一層遞迴呼叫時,n 會等於 1, 該次的 factorial 方法 factorial(1) 就會回傳 1, 然後 factorial(2) 就能回傳 2*1=2, 接著 factorial(3) 就能回傳 3*2=6..., 一直回傳回到我們最初的呼叫, 得到 n! 的解答遞迴能夠幫助我們以較少的程式碼簡明的完成可使用遞迴觀念計算的問題但隨著 n 值變大, 使用遞迴的程式, 由於要付出多次方法呼叫的資源, 故與非遞迴的程式在執行效率上比較會明顯較差, 且容易在終止條件上設定錯誤, 就像迴圈的判斷式設定錯誤一樣, 會使程式卡在其中無法終結, 故我們需要審慎使用以下以一個求最大公因數程式, 來進一步說明遞迴的觀念程式範例 : 遞迴解最大公因數學習重點 : 遞迴概念練習, 用輾轉相除法求最大公因數數學問題中, 兩個數字的最大公因數, 可以使用輾轉相除法來求解, 輾轉相除法的作法是將傳入的兩個數字去相除, 如果較小的數字能夠將較大的數字整除的話, 則較小的數字就是所求的最大公因數, 若不能整除, 則將餘數與較小的數字繼續進行輾轉相除法直到找到為止, 並將整個過程以遞迴的方式撰寫一程式碼撰寫 01 using System; class Program{ public static void Main() 06 { 07 Console.Write(" 請輸入第一個數字 :");

4 08 int x = int.parse(console.readline()); 09 Console.Write(" 請輸入第二個數字 :"); 10 int y = int.parse(console.readline()); int gcd = GCD(x, y); 13 Console.WriteLine(" 最大公因數為 :" + gcd); 14 Console.Read(); public static int GCD(int a, int b){ 18 Console.WriteLine("(" + a + "," + b + ")"); 19 b = b % a; 20 if (b == 0) 21 return a; 22 return GCD(b, a); 二程式碼解說本程式的關鍵在於如何將連續的輾轉相除法以遞迴的形式撰寫, 我們宣告方法 GCD 做為遞迴求解的方法當主程式傳入兩個數字時, 程式會先印出這兩個數字 ( 作為計算進度的提示 ), 接著依照輾轉相除法的作法, 我們去求出兩者相除的餘數程式中以 b 除以 a 並將結果直接儲存代換到 b 當中, 如果餘數為 0 則 a 就是所求之最大公因數, 可以直接回傳了 ; 反之則需將 a b 兩者對調, 因為我們一開始是以 b 除以 a, 代表我們猜測 a 大於 b, 而在執行完 b = b %a; 之後, 兩者大小會相反, 若 a 小於 b, 則本來就需對調, 故最後需對調後傳入另一個 GCD 方法當中, 並可直接以該方法得到的結果回傳 public static int GCD(int a, int b){ Console.WriteLine("(" + a + "," + b + ")"); b = b % a; if (b == 0) return a; return GCD(b, a); 主程式則只要提示使用者輸入兩個數字, 並將兩個數字傳入剛剛宣告的 GCD 方法當中,GCD 方法當中的 WrtieLine 方法會將該次嘗試的兩個數字印出, 故使用者可以看到每次遞迴求解的過程, 最後將求得的解答印出即可

public static void Main() { Console.Write(" 請輸入第一個數字 :"); int x = int.parse(console.readline()); Console.Write(" 請輸入第二個數字 :"); int y = int.parse(console.readline()); int gcd = GCD(x, y); Console.

5 public static void Main() { Console.Write(" 請輸入第一個數字 :"); int x = int.parse(console.readline()); Console.Write(" 請輸入第二個數字 :"); int y = int.parse(console.readline()); int gcd = GCD(x, y); Console.WriteLine(" 最大公因數為 : " + gcd); Console.Read(); 三執行結果河內塔問題視窗程式河內塔是一個數學上的著名問題, 也是許多教科書中用來解釋遞迴的經典範例, 河內塔源自印度傳說, 有興趣的讀者可以自行上網查詢其由來, 其內容簡單來說就是有三個木棍, 其中一個上面套有 n 個由小到大的圓盤 ( 上小下大 ), 我們則要試著將這些圓盤全部移動到另一個木棍上, 但是需要遵守由上面開始拿, 一次移動一個以及大的圓盤不能在小圓盤之上三個規則程式範例 : 河內塔解題演示程式學習重點 : 進階遞迴方法的宣告呼叫及回傳物件, 並練習 Sleep 方法我們在視窗程式中要三個清單方塊 (ListBox) 來代表這三個木棍, 以 A B C 分別代表, 圓盤則用數字代替, 並利用數字大小代表圓盤大小, 數字小的代表小的圓盤, 起始的數字都在 A 清單中, 我們要用程式自動將其移動到 C 清單, 並能讓使用者自訂圓盤個數及用另一個清單顯示移動的順序一表單配置新增 4 個 ListBox 4 個 Label, 以及 TextBox Button 各 1 個, 新增完成之後表單編輯畫面大約如下 :

6 然後依照以下表格更改各物件屬性值 : 物件 Name 屬性 Text 屬性 listbox1 lista * 不用變更 listbox2 listb * 不用變更 listbox3 listc * 不用變更 listbox4 movelist * 不用變更 label1 labela A label2 labelb B label3 labelc C label4 movelabel 移動順序 textbox1 numtext 0 button1 startbutton 開始演示更改後的表單配置大約如下 :

7 二程式碼撰寫 01 private void startbutton_click(object sender, EventArgs e) 02 { 03 int num = int.parse(numtext.text); lista.items.clear(); 06 listb.items.clear(); 07 listc.items.clear(); 08 movelist.items.clear(); 09 for (int i=1; i <= num; ++i){ 10 lista.items.add(i); 11 listb.items.add("-"); 12 listc.items.add("-"); Hanoi(num, 'A','B','C'); void Hanoi(int num, char source, char tmp, char target){ 18 if(num > 0){ 19 Hanoi (num-1, source, target, tmp); 20 move(source, target); 21 Hanoi (num-1, tmp, source, target);

8 ListBox trans(char c){ if (c == 'A') return lista; else if (c == 'B') return listb; else return listc; void move(char source, char target) { System.Threading.Thread.Sleep(500); movelist.items.add(source + "->" + target); movelist.refresh(); string srctext = ""; ListBox srclist = trans(source); for (int i = 0; i < srclist.items.count; ++i){ if (srclist.items[i].tostring()!="-"){ srctext = srclist.items[i].tostring(); srclist.items[i] = "-"; break; srclist.refresh(); ListBox trglist = trans(target); for (int i = 0; i < trglist.items.count; ++i){ if (trglist.items[i].tostring()!="-"){ trglist.items[i - 1] = srctext; break; else if (i == trglist.items.count - 1) trglist.items[i] = srctext; trglist.refresh();

$Hanoi 來進行實際解題過程, 我們的目的是將所有數字 ( 圓盤 ) 移動到清單 C 當中,Hanoi 的定義我們接著講解 private void startbutton_click(object sender, EventArgs e) { int num = int.parse(numtext.text); lista.items.clear(); listb.items.clear(); listc.$

9 60 三程式碼解說程式起始於開始演示按鈕, 我們由此開始看起, 程式開始先由文字方塊 numtext 當中取得使用者輸入的圓盤個數, 將其儲存在變數 num 當中, 先將所有清單方塊執行 Clear 方法清空, 最後依據使用者輸入的數字, 將數字依序放入清單 A 當中, 清單中其餘空的部份則用 - 代替程式至此, 假設使用者輸入的數字是 5, 則畫面顯示如下 : 最後則執行遞迴方法 Hanoi 來進行實際解題過程, 我們的目的是將所有數字 ( 圓盤 ) 移動到清單 C 當中,Hanoi 的定義我們接著講解 private void startbutton_click(object sender, EventArgs e) { int num = int.parse(numtext.text); lista.items.clear(); listb.items.clear(); listc.items.clear(); movelist.items.clear(); for (int i=1; i <= num; ++i){ lista.items.add(i); listb.items.add("-"); listc.items.add("-");

10 Hanoi(num, 'A', 'B', 'C'); 遞迴方法 Hanoi 總共有四個引數, 其中整數變數 num 代表有幾個數字要移動,source tmp target 三個字元則分別代表對應起始清單, 暫存清單及目標清單, 故我們在前面呼叫 Hanoi 方法時, 預設的起始清單是 A, 要移到清單 C, 而 B 自然是暫存用的清單, 變數 num 則剛好是要移動的數字個數河內塔問題的遞迴拆解分兩個部分, 若我們想移動總共 n 個數字 ( 需檢查 n 大於 0, 代表還有數字需要移動 ), 就可分解成三個部分 : 1. 將起始清單的 n-1 個先移動到暫存清單當中, 原本的目標清單在此變成暫存清單, 此為第一個遞迴呼叫 Hanoi (num-1, source, target, tmp); 2. 接著將起始清單中剩下最後一個數字 ( 最底的圓盤 ) 移動到目標清單中, 此步驟為基礎移動, 沒有遞迴行為, 我們之後單獨用 move 方法來處理對應動作 3. 最後將剛剛擺在暫存當中的所有數字再移動到目標清單, 此為第二個遞迴呼叫 Hanoi (num-1, tmp, source, target); void Hanoi(int num, char source, char tmp, char target){ if(num > 0){ Hanoi (num-1, source, target, tmp); move(source, target); Hanoi (num-1, tmp, source, target); 在撰寫 move 方法之前, 我們要先寫另外一個小方法, 由於我們用字元型態變數來傳遞對應的清單, 為了避免之後過多的判斷式, 我們自己寫一個 trans 方法來做轉換, 讀者注意這裡 trans 方法回傳的型態就是清單方塊 (ListBox), 而引數就是一個字元變數 c 用簡單的判斷式判斷傳回對應的清單方塊元件即可 ListBox trans(char c){ if (c == 'A') return lista; else if (c == 'B') return listb; else return listc;

11 由於電腦運算速度快, 故我們在 move 方法一開始使用了 C# 程式當中內建的方法 System.Threading.Thread.Sleep(500);, 該方法可以讓程式暫停執行, 方便使用者觀察河內塔每一步的移動, 傳入的數字 500 是以毫秒為單位計算的暫停時間接著我們就將這一步移動以文字形式加入 movelist 清單當中並執行清單的 Refresh 方法, 讓螢幕顯示的畫面更新, 不受 Sleep 方法影響接著宣告一個暫時的字串變數 srctext, 用來儲存起始清單中最上面的數字 ( 用字串變數儲存是為了減少型態轉換的次數 ), 然後將 source 字元變數傳入 trans 方法取得對應的清單, 宣告名為 srclist 最後用一個迴圈檢查清單中第一個非 - 的元素, 將其內容先暫存到 srctext 當中, 並將該元素改為 -, 就完成元素移動的第一個部分了一樣使用清單的 Refresh 方法更新螢幕顯示的畫面, 才能不受 Sleep 方法影響正常顯示 void move(char source, char target) { System.Threading.Thread.Sleep(500); movelist.items.add(source + "->" + target); movelist.refresh(); string srctext = ""; ListBox srclist = trans(source); for (int i = 0; i < srclist.items.count; ++i){ if (srclist.items[i].tostring()!="-"){ srctext = srclist.items[i].tostring(); srclist.items[i] = "-"; break; srclist.refresh(); 最後是將剛剛取得的內容移到目標清單的最上層, 這次將 target 變數傳入 trans 方法取得對應清單, 宣告名為 trglist 用一個迴圈檢查清單中第一個非 - 的元素, 將其上一個元素改為剛剛從起始清單取得的內容 srctext, 若迴圈到最後一圈都沒有遇到非 - 的元素, 則是將最後一個元素改為剛剛從起始清單取得的內容 srctext, 如此一來就完成元素移動的第二個部分及整個程式了 ListBox trglist = trans(target); for (int i = 0; i < trglist.items.count; ++i){ if (trglist.items[i].tostring()!="-"){ trglist.items[i - 1] = srctext; break;

12 else if (i == trglist.items.count - 1) trglist.items[i] = srctext; trglist.refresh(); 四執行結果

第3章.doc

第3章.doc 3 3 3 3.1 3 IT Trend C++ Java SAP Advantech ERPCRM C++ C++ Synopsys C++ NEC C C++PHP C++Java C++Java VIA C++ 3COM C++ SPSS C++ Sybase C++LinuxUNIX Motorola C++ IBM C++Java Oracle Java HP C++ C++ Yahoo