4. 介紹三柱河內塔最少搬動次數的計算遞迴關係式終止條件 hanoi_step(n) = 2 * hanoi_step(n-1) + 1 hanoi_step(1) = 1 5. 列出三柱河內塔的最佳搬動步驟遞迴關係

Size: px

Start display at page:

Download "4. 介紹三柱河內塔最少搬動次數的計算遞迴關係式終止條件 hanoi_step(n) = 2 * hanoi_step(n-1) + 1 hanoi_step(1) = 1 5. 列出三柱河內塔的最佳搬動步驟遞迴關係 "

衩绩琢樊
7 years ago
Views:

1 踩地雷遊戲程式撰寫及教學應用分享建國中學王鼎中緣起在程式語言的教學過程中, 介紹完函數 (Function) 的用法後, 接著就希望能將程式語言中相當強大直觀的遞迴呼叫功能介紹給學生, 最經典的範例便是河內塔, 不論是三柱河內塔最少搬動次數的計算, 或是列出三柱河內塔的最佳搬動步驟, 都相當能引起學生的學習動機, 甚至有些學生在學習過後, 還會想知道遞迴呼叫除了用來計算加總階層組合數之外, 是不是還有其他的應用, 因此, 筆者希望能找到另一個能展現遞迴呼叫功能的應用, 在幾經嘗試之後發現, 學生們經常在 windows 環境下玩的踩地雷遊戲是個不錯的選擇, 只是不曉得有了小朋友齊打交 CS 及 candy crush 之後, 踩地雷是不是還那麼吸引人就是了遞迴呼叫的教學流程分享在開始介紹踩地雷遊戲的遞迴應用前, 先分享一下筆者在介紹遞迴呼叫的教學流程 : 1. 介紹在函數 (Function) 中呼叫另一個函數 (Function) 的用法接著學生可能會問到那函數 (Function) 可不可以呼叫函數 (Function) 本身 2. 介紹函數呼叫函數本身的用法詢問學生為什麼函數要呼叫函數本身, 引導關注函數的遞迴關係引導學生發現可能產生的遞迴無法終止的問題 3. 介紹遞迴函數呼叫的兩大要素 : 遞迴關係及終止條件舉例介紹遞迴關係及終止條件加總 SUM: 遞迴關係式終止條件 S(n) = (n-1) + n S(0) = 0 S(n) = S(n-1) + n 階層 : 遞迴關係式 f(n) = n * (n-1) * (n-2) * * 2 * 1 f(n) = n * f(n-1) 終止條件 f(1) = 1 計算組合數遞迴關係式 C(m,n) = m! / (n!*(m-n)!) C(m,n) =C(m-1,n) + C(m-1,n-1) 終止條件 C(m,m) = 1 C(m,0) = 1 C(0,n) = 0

個能展現遞迴呼叫功能的應用, 在幾經嘗試之後發現, 學生們經常在 windows 環境下玩的踩地雷遊戲是個不錯的選擇, 只是不曉得有了小朋友齊打交 CS 及 candy crush 之後, 踩地雷是不是還那麼吸引人就是了遞迴呼叫的教學流程分

2 4. 介紹三柱河內塔最少搬動次數的計算遞迴關係式終止條件 hanoi_step(n) = 2 * hanoi_step(n-1) + 1 hanoi_step(1) = 1 5. 列出三柱河內塔的最佳搬動步驟遞迴關係搬動 n 個盤子從 A 到 C 的步驟 = 搬動 n-1 個盤子從 A 到 B 搬動最下面的盤子從 A 到 C 搬動 n-1 個盤子從 B 到 C 終止條件當搬動的盤子只有一個時則搬動該盤子從 A 到 C 6. 以踩地雷遊戲介紹遞迴呼叫的應用踩地雷遊戲應用到遞迴呼叫的部分, 主要是在當使用者所踩的位置, 周邊相鄰的八個位置的炸彈總數等於 0, 亦即周邊都沒有炸彈時, 我們會應用遞迴呼叫的方式, 分別去踩周邊的那八個位置, 若去踩的那個位置又有同樣的狀況時, 則繼續遞迴呼叫下去而當周邊炸彈總數不等於 0 時, 則僅需將炸彈數儲存在陣列中即可遞迴關係終止條件當周邊炸彈總數等於 0 時去踩周邊的那八個位置當周邊炸彈總數不等於 0 時將炸彈數儲存在對應陣列中教學時若擔心整體程式複雜度可能較高, 影響學生學習的話, 建議可如以下分享的程式, 將程式需用到的功能先用函數的方式撰寫好, 提供給學生依所介紹的遞迴呼叫方式, 完成遞迴部分的程式撰寫, 對於程度較好的學生則可視其接受程度, 斟酌提供所撰寫好的部分函數踩地雷遊戲撰寫實例分享以下為筆者所撰寫的一個簡易版踩地雷遊戲, 程式的撰寫不見得最佳最正確, 但力求清楚簡潔, 希望能提供給大家做為教學上的一個參考這一個版本的程式, 僅是一個具核心功能的毛胚程式, 主要是想強調周邊沒有炸彈時的遞迴展開動作, 並沒有做炸彈標示遊戲介面顯示完成遊戲的判斷, 以及輸入錯誤的偵測等功能的設計, 這些部分可以作為學生延伸學習的課題, 讓學生嘗試去解決若您對以上功能的撰寫有興趣, 請參閱另附的完整版程式

以踩地雷遊戲介紹遞迴呼叫的應用踩地雷遊戲應用到遞迴呼叫的部分, 主要是在當使用者所踩的位置, 周邊相鄰的八個位置的炸彈總數等於 0, 亦即周邊都沒有炸彈時, 我們會應用遞迴呼叫的方式, 分別去踩周邊的那八個位置, 若去踩

3 定義及宣告定義踩地雷範圍的大小 : 調整行數及列數的數值即可改變盤面的大小 #define ROWS 9 // 踩地雷範圍的列數 #define COLS 9 // 踩地雷範圍的行數宣告儲存踩地雷資訊的陣列 int data[rows+2][cols+2]; // 儲存踩地雷相關資訊用 data 陣列是一個二維陣列, 大小分別 ROWS+2 及 COLS+2, 亦即 ( 列數 + 左右兩邊的邊界 ) 以及 ( 行數 + 左右兩邊的邊界 ), 陣列資料型態為 ( 整數 ), 其內容標記大致有下列數種 :(-8): 邊界 (99): 炸彈 (-1): 尚未被踩的地方 (1-8 的數字 ): 該位置周邊的炸彈數在踩地雷範圍的周邊多加一圈邊界 (-8) 的用意, 在於遞迴展開時可省去邊界的偵測, 並避免產生存取超出陣列範圍元素的錯誤, 降低判斷的次數及程式的複雜性基本函數撰寫介紹 (1) Init() 函數 : 功能 : 踩地雷盤面初始化傳入參數 :bombs 為炸彈總數 ( 整數型態 ) 函數設計的概念 : 先在列數為 0 或 ROWS+1, 或行數為 0 或 COLS+1 的陣列位置上填上 (-8), 代表邊界, 其他的位置填上 (-1), 代表尚未被踩的地方, 接著, 每次隨機產生一組 x y 座標值, 在該陣列位置填上 (99), 代表炸彈, 重複進行多次完成炸彈得隨機佈置, 由於隨機產生出的座標值很有可能會重複, 因此, 實際產生的炸彈數量有可能會較預期的數量少, 此部分在判定是否完成遊戲時須特別留意 void init(int bombs) int i,j,temp1,temp2;

的地方 (1-8 的數字 ): 該位置周邊的炸彈數在踩地雷範圍的周邊多加一圈邊界 (-8) 的用意, 在於遞迴展開時可省去邊界的偵測, 並避免產生存取超出陣列範圍元素的錯誤, 降低判斷的次數及程式的複雜性基本函數撰寫介紹 (1)

4 for( i=0; i<=rows+1; i++) for( j=0; j<=cols+1; j++) if( i==0 j==0 i==rows+1 j==cols+1 ) // 設定邊界 data[i][j]=-8; // 設定盤面初始內容 data[i][j]=-1; // 隨機產生 bombs 個炸彈 for( i=1; i<=bombs; i++) temp1=rand()%(rows) + 1 ; temp2=rand()%(cols) + 1 ; data[temp1][temp2]=99; (2) display() 函數 : 功能 : 顯示踩地雷盤面傳入參數 : 無函數設計的概念 : 此函數主要是將 data 陣列的內容顯示出來, 重點在於 ( 印出盤面內容 ) 的部分 : 在 data[i][j] 的內容為 0 時 ( 踩過且周邊都沒有炸彈 ) 印出空白, 在 data[i][j] 的內容為 -1 時 ( 該位置尚未踩過 ) 印出底線 _, 其餘皆用 data 陣列中的原始內容輸出若要將此程式改寫為遊戲版, 則只要在函數中加入將炸彈隱藏起來的處理, 亦即當 data[i][j] 的值 (99) 時顯示為 _, 以及處理炸彈標示顯示的部分即可 void display() int i,j; system("cls"); // 印出 Y 橫軸的座標 cout << "x/y"; for( j=0; j<=cols+1; j++) if( j==0 j==cols+1 ) cout << " ";

內容 ) 的部分 : 在 data[i][j] 的內容為 0 時 ( 踩過且周邊都沒有炸彈 ) 印出空白, 在 data[i][j] 的內容為 -1 時 ( 該位置尚未踩過 ) 印出底線 _, 其餘皆用 data 陣列中的原始內容輸出若要將此程式改寫為遊戲版, 則只要在函數中

5 cout << setw(2) << j; cout << endl; // 顯示所有盤面內容 for( i=0; i<=rows+1; i++) // 印出 X 縱軸的座標 if( i==0 i==rows+1 ) cout << " "; cout << setw(2) << i; // 印出盤面內容 for( j=0; j<=cols+1; j++) if( data[i][j]==0 ) cout << " "; cout << setw(2) << data[i][j]; cout << endl; (3) step_on(int x, int y) 函數 : 功能 : 進行 X,Y 座標處的踩地雷處理傳入參數 :int x, int y 分別為 X 座標與 Y 座標值函數設計的概念 : 此函數主要是進行 X,Y 座標處的踩地雷處理, 函數一開始會先以迴圈計算 X,Y 座標處周邊八個位置的炸彈總數, 接著, 若炸彈總數等於 0, 則依序以周邊八個位置的 X,Y 座標值為參數, 遞迴呼叫 step_on() 函數進行踩地雷處理, 若炸彈總數不等於 0, 則將周邊炸彈總數儲存在 X,Y 座標值對應的陣列中 for(j=-1;j<=1;j++) for(i=-1;i<=1;i++) // i+x j+y (X-1,Y-1) (X+0,Y-1) (X+1,Y-1) (X-1,Y+0) (X+0,Y+0) (X+1,Y+0) (X-1,Y+1) (X+0,Y+1) (X+1,Y+1) 小技巧 : 計算周邊八個位置的炸彈總數, 及對周邊八個位置進行遞迴呼叫的踩地

: 此函數主要是進行 X,Y 座標處的踩地雷處理, 函數一開始會先以迴圈計算 X,Y 座標處周邊八個位置的炸彈總數, 接著, 若炸彈總數等於 0, 則依序以周邊八個位置的 X,Y 座標值為參數, 遞迴呼叫 step_on() 函數進行踩地雷處理, 若炸

6 雷處理, 都單純的僅用到了兩層迴圈處理, 且中間位置 (X+0,Y+0) 並不需要特別做處理, 原因在於 : (1) 計算周邊八個位置的炸彈總數 : 由於在處理前已先檢查本身 (X+0,Y+0) 是不是炸彈, 不是炸彈才會進入計算炸彈總數的處理, 因此, 加入本身 (X+0,Y+0) 的計算, 並不會影響炸彈總數的計算 (2) 對周邊八個位置進行遞迴呼叫的踩地雷處理 : 由於在周邊炸彈總數等於 0 時, 才會進行遞迴呼叫, 因此, 在遞迴呼叫前先將 data[x][y] 設定為 0, 如此一來, 只要在迴圈中加一個 if( data[i+x][j+y]==-1 ), 即該點仍未被踩過的判斷, 即可避免掉中心位置 (X+0,Y+0) 呼叫到中心位置 (X+0,Y+0), 所產生的無窮遞迴的狀況 void step_on(int x, int y) int i,j,count; count=0; // 統計該位置周邊的炸彈總數 for(i=-1;i<=1;i++) for(j=-1;j<=1;j++) if( data[i+x][j+y] == 99 ) count = count + 1; // 若周邊炸彈數為 0 時, 遞迴呼叫展開 // 每一輪呼叫的順序為 // 2 7 // // 否則將周邊炸彈總數儲存在該座標的陣列中 if( count==0 ) data[x][y]=0; for(j=-1;j<=1;j++) for(i=-1;i<=1;i++) // 取消下兩行註解可顯示目前處理的座標位置 //cout << i+x <<" " << j+y << endl; //system("pause"); if( data[i+x][j+y]==-1 ) // 取消下兩行註解可動態展示遞迴展開的狀況 // display(); // system("pause"); step_on(i+x,j+y);

中加一個 if( data[i+x][j+y]==-1 ), 即該點仍未被踩過的判斷, 即可避免掉中心位置 (X+0,Y+0) 呼叫到中心位置 (X+0,Y+0), 所產生的無窮遞迴的狀況 void step_on(int x, int y) int i,j,count; count=0; // 統計該位置周邊

7 data[x][y]=count; 遞迴教學展示應用若要展示踩地雷的遞迴展開動作時, 可以在每一次遞迴呼叫前, 亦即在 step_on() 函數中, 每次呼叫 step_on() 函數之前, 加入以下兩行程式即可 : display(); system("pause"); step_on(i+x,j+y); 以下為遞迴展開的狀況 : 主程式撰寫先以 init() 函數及 display() 函數完成 : 初始化踩地雷盤面並完成炸彈佈置, 以及顯示盤面的動作 init(20); display(); 接著, 以 do while 迴圈重複進行下列處理程序 : (1) 讓使用者輸入要踩的 x y 座標位置 cout << " 請輸入要踩的 x y 座標位置 :"; cin >> x >> y;

先以 init() 函數及 display() 函數完成 : 初始化踩地雷盤面並完成炸彈佈置, 以及顯示盤面的動作 init(20); display(); 接著, 以 do

8 (2) 判斷是否踩到炸彈 if(data[x][y]==99) cout << "BOMB!!" << endl; break; (3) 進行 X,Y 座標處的踩地雷處理 step_on(x,y); (4) 顯示盤面 display(); 附踩地雷完整版遊戲程式, 提供大家參考文中所附程式為簡易版毛胚程式, 程式撰寫力求簡單, 盡量不去處理畫面以及遊戲判斷的動作, 以使教學概念能清楚呈現若學生能清楚理解文中的簡易版程式, 則可讓學生嘗試完成一個完整版的踩地雷遊戲, 因此, 附上一個以簡易版程式為基礎繼續發展的完整版遊戲程式, 提供給大家參考, 程式若有不盡完善或謬誤之處, 亦請不吝指教 #include <iostream> #include <iomanip> #define ROWS 9 // 踩地雷範圍的列數 #define COLS 9 // 踩地雷範圍的行數 #define TOTAL_BOMBS 10 // 設定炸彈總數 using namespace std; int data[rows+2][cols+2]; // 儲存踩地雷相關資訊用內容標記說明如下 : // -8: 邊界 99: 炸彈 -1: 尚未被踩的地方 // 1-8 的數字 : 該位置周邊的炸彈數 int mark[rows+2][cols+2]; // 儲存炸彈標記資訊 // 0: 未標記 1: 標記為炸彈 int real_bombs=total_bombs; // 儲存隨機產生出的實際炸彈數 // real_bombs = (TOTAL_BOMBS - 重複指定的炸彈數 ) // 踩地雷盤面初始化傳入參數 bombs 為炸彈總數 void init(int bombs) int i,j,temp1,temp2; for( i=0; i<=rows+1; i++) for( j=0; j<=cols+1; j++)

作, 以使教學概念能清楚呈現若學生能清楚理解文中的簡易版程式, 則可讓學生嘗試完成一個完整版的踩地雷遊戲, 因此, 附上一個以簡易版程式為基礎繼續發展的完整版遊戲程式, 提供給大家參考, 程式若有不盡完善或謬誤之處, 亦

9 if( i==0 j==0 i==rows+1 j==cols+1 ) // 設定邊界 data[i][j]=-8; mark[i][j]=-8; // 設定盤面初始內容 data[i][j]=-1; mark[i][j]=-1; // 隨機產生 bombs 個炸彈 for( i=1; i<=bombs; i++) temp1=rand()%(rows) + 1 ; temp2=rand()%(cols) + 1 ; // 當發生重複指定炸彈的狀況時, 將 real_bombs-1 if( data[temp1][temp2]==99 ) real_bombs = real_bombs-1; data[temp1][temp2]=99; // 顯示踩地雷盤面 void display() int i,j; system("cls"); // 印出 Y 橫軸的座標 cout << "x/y"; for( j=0; j<=cols+1; j++) if( j==0 j==cols+1 ) cout << " "; cout << setw(2) << j; cout << endl; // 顯示所有盤面內容 for( i=0; i<=rows+1; i++) // 印出 X 縱軸的座標 if( i==0 i==rows+1 ) cout << " ";

real_bombs-1; data[temp1][temp2]=99; // 顯示踩地雷盤面 void display() int i,j; system("cls"); // 印出 Y 橫軸的座標 cout << "x/y"; for( j=0; j<=cols+1; j++) if(

10 cout << setw(2) << i; // 印出盤面內容 for( j=0; j<=cols+1; j++) // 印出炸彈標記 if( mark[i][j]==1 ) cout << if( data[i][j]==-1 data[i][j]==99 ) cout << " _"; if( data[i][j]==0 ) cout << " "; cout << setw(2) << data[i][j]; cout << endl; void step_on(int x, int y) int i,j,count; count=0; // 統計該位置周邊的炸彈總數 for(i=-1;i<=1;i++) for(j=-1;j<=1;j++) if( data[i+x][j+y] == 99 ) count = count + 1; // 若周邊炸彈數為 0 時, 遞迴呼叫展開 // 每一輪呼叫的順序為 // 2 7 // // 否則將周邊炸彈總數儲存在該座標的陣列中 if( count==0 ) data[x][y]=0; for(j=-1;j<=1;j++) for(i=-1;i<=1;i++)

// 統計該位置周邊的炸彈總數 for(i=-1;i<=1;i++) for(j=-1;j<=1;j++) if( data[i+x][j+y] == 99 ) count = count + 1; // 若周邊炸彈數為 0 時, 遞迴呼叫展開

11 // 取消下兩行註解可顯示目前處理的座標位置 //cout << i+x <<" " << j+y << endl; //system("pause"); if( data[i+x][j+y]==-1 ) // 取消下兩行註解可動態展示遞迴展開的狀況 // display(); // system("pause"); step_on(i+x,j+y); data[x][y]=count; int win_judge() int win_or_not = 0; int i,j; int correct_items=0, untreated_items=0; for( i=1; i<=rows; i++) for( j=1; j<=cols; j++) if( mark[i][j]==1 && data[i][j]==99 ) // 累計標示正確的數量 correct_items = correct_items + 1; if( data[i][j] == -1 ) // 累計尚未踩的位置數量 untreated_items = untreated_items + 1; if( (correct_items == real_bombs) && (untreated_items==0) ) win_or_not = 1; return win_or_not; int main() int x,y,choose,win; srand( time(null) ); // 初始化踩地雷盤面並設定炸彈數 init(total_bombs); // 顯示盤面

if( mark[i][j]==1 && data[i][j]==99 ) // 累計標示正確的數量 correct_items = correct_items + 1; if( data[i][j] == -1 ) // 累計尚未踩的位置數量 untreated_items = untreated_items + 1; if(

12 display(); do // 進行功能選擇 cout << " 請輸入所要執行的動作 (1)\" 踩 \" (2) 標記地雷 (3) 結束 :"; cin >> choose; switch (choose) case 1: // 輸入要踩的 x y 座標位置 cout << " 請輸入要踩的 x y 座標位置 :"; cin >> x >> y; // 判斷是否踩到炸彈 if(data[x][y]==99) cout << "BOMB!!" << endl; break; // 進行 X,Y 座標處的踩地雷處理 step_on(x,y); // 顯示盤面 display(); break; case 2: // 輸入要標記的 x y 座標位置 cout << " 請輸入要標記的 x y 座標位置 :"; cin >> x >> y; // 儲存標記 mark[x][y] = mark[x][y]*(-1); // 顯示盤面 display(); break; case 3: cout << " 遊戲結束, 再會!!" << endl; break; win = win_judge(); if( win==1 ) cout << " 恭喜你獲勝了, 再會!!"; break; while( choose!=3 &&!(choose==1&&data[x][y]==99) ); system("pause"); return 0;

!" << endl; break; // 進行 X,Y 座標處的踩地雷處理 step_on(x,y); // 顯示盤面 display(); break; case 2: // 輸入要標記的 x y 座標位置 cout << " 請輸入要標記的 x y 座標位置 :"; cin >> x >>

6-1-1極限的概念

6-1-1極限的概念選修數學 (I-4 多項式函數的極限與導數 - 導數與切線斜率定義. f ( 在的導數 : f ( h 對實函數 f ( 若極限存在 h h 則稱 f ( 在點可微分而此極限值稱為 f ( 在的導數以 f ( 表示 f ( f ( 函數 f ( 在的導數也可以表成 f ( 註 : 為了

4. 介 紹 三 柱 河 內 塔 最 少 搬 動 次 數 的 計 算 遞 迴 關 係 式 終 止 條 件 hanoi_step(n) = 2 * hanoi_step(n-1) + 1 hanoi_step(1) = 1 5. 列 出 三 柱 河 內 塔 的 最 佳 搬 動 步 驟 遞 迴 關 係

4. 介紹三柱河內塔最少搬動次數的計算遞迴關係式終止條件 hanoi_step(n) = 2 * hanoi_step(n-1) + 1 hanoi_step(1) = 1 5. 列出三柱河內塔的最佳搬動步驟遞迴關係