踩 地 雷 遊 戲 程 式 撰 寫 及 教 學 應 用 分 享 建 國 中 學 王 鼎 中 緣 起 在 程 式 語 言 的 教 學 過 程 中, 介 紹 完 函 數 (Function) 的 用 法 後, 接 著 就 希 望 能 將 程 式 語 言 中 相 當 強 大 直 觀 的 遞 迴 呼 叫 功 能 介 紹 給 學 生, 最 經 典 的 範 例 便 是 河 內 塔, 不 論 是 三 柱 河 內 塔 最 少 搬 動 次 數 的 計 算, 或 是 列 出 三 柱 河 內 塔 的 最 佳 搬 動 步 驟, 都 相 當 能 引 起 學 生 的 學 習 動 機, 甚 至 有 些 學 生 在 學 習 過 後, 還 會 想 知 道 遞 迴 呼 叫 除 了 用 來 計 算 加 總 階 層 組 合 數 之 外, 是 不 是 還 有 其 他 的 應 用, 因 此, 筆 者 希 望 能 找 到 另 一 個 能 展 現 遞 迴 呼 叫 功 能 的 應 用, 在 幾 經 嘗 試 之 後 發 現, 學 生 們 經 常 在 windows 環 境 下 玩 的 踩 地 雷 遊 戲 是 個 不 錯 的 選 擇, 只 是 不 曉 得 有 了 小 朋 友 齊 打 交 CS 及 candy crush 之 後, 踩 地 雷 是 不 是 還 那 麼 吸 引 人 就 是 了 遞 迴 呼 叫 的 教 學 流 程 分 享 在 開 始 介 紹 踩 地 雷 遊 戲 的 遞 迴 應 用 前, 先 分 享 一 下 筆 者 在 介 紹 遞 迴 呼 叫 的 教 學 流 程 : 1. 介 紹 在 函 數 (Function) 中 呼 叫 另 一 個 函 數 (Function) 的 用 法 接 著 學 生 可 能 會 問 到 那 函 數 (Function) 可 不 可 以 呼 叫 函 數 (Function) 本 身 2. 介 紹 函 數 呼 叫 函 數 本 身 的 用 法 詢 問 學 生 為 什 麼 函 數 要 呼 叫 函 數 本 身, 引 導 關 注 函 數 的 遞 迴 關 係 引 導 學 生 發 現 可 能 產 生 的 遞 迴 無 法 終 止 的 問 題 3. 介 紹 遞 迴 函 數 呼 叫 的 兩 大 要 素 : 遞 迴 關 係 及 終 止 條 件 舉 例 介 紹 遞 迴 關 係 及 終 止 條 件 加 總 SUM: 遞 迴 關 係 式 終 止 條 件 S(n) = 1 + 2 + 3 + + (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
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 時 去 踩 周 邊 的 那 八 個 位 置 1 4 6 2 7 3 5 8 當 周 邊 炸 彈 總 數 不 等 於 0 時 將 炸 彈 數 儲 存 在 對 應 陣 列 中 教 學 時 若 擔 心 整 體 程 式 複 雜 度 可 能 較 高, 影 響 學 生 學 習 的 話, 建 議 可 如 以 下 分 享 的 程 式, 將 程 式 需 用 到 的 功 能 先 用 函 數 的 方 式 撰 寫 好, 提 供 給 學 生 依 所 介 紹 的 遞 迴 呼 叫 方 式, 完 成 遞 迴 部 分 的 程 式 撰 寫, 對 於 程 度 較 好 的 學 生 則 可 視 其 接 受 程 度, 斟 酌 提 供 所 撰 寫 好 的 部 分 函 數 踩 地 雷 遊 戲 撰 寫 實 例 分 享 以 下 為 筆 者 所 撰 寫 的 一 個 簡 易 版 踩 地 雷 遊 戲, 程 式 的 撰 寫 不 見 得 最 佳 最 正 確, 但 力 求 清 楚 簡 潔, 希 望 能 提 供 給 大 家 做 為 教 學 上 的 一 個 參 考 這 一 個 版 本 的 程 式, 僅 是 一 個 具 核 心 功 能 的 毛 胚 程 式, 主 要 是 想 強 調 周 邊 沒 有 炸 彈 時 的 遞 迴 展 開 動 作, 並 沒 有 做 炸 彈 標 示 遊 戲 介 面 顯 示 完 成 遊 戲 的 判 斷, 以 及 輸 入 錯 誤 的 偵 測 等 功 能 的 設 計, 這 些 部 分 可 以 作 為 學 生 延 伸 學 習 的 課 題, 讓 學 生 嘗 試 去 解 決 若 您 對 以 上 功 能 的 撰 寫 有 興 趣, 請 參 閱 另 附 的 完 整 版 程 式
定 義 及 宣 告 定 義 踩 地 雷 範 圍 的 大 小 : 調 整 行 數 及 列 數 的 數 值 即 可 改 變 盤 面 的 大 小 #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;
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 << " ";
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+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 時, 遞 迴 呼 叫 展 開 // 每 一 輪 呼 叫 的 順 序 為 1 4 6 // 2 7 // 3 5 8 // 否 則 將 周 邊 炸 彈 總 數 儲 存 在 該 座 標 的 陣 列 中 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);
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;
(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++)
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 << " ";
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 時, 遞 迴 呼 叫 展 開 // 每 一 輪 呼 叫 的 順 序 為 1 4 6 // 2 7 // 3 5 8 // 否 則 將 周 邊 炸 彈 總 數 儲 存 在 該 座 標 的 陣 列 中 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); 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); // 顯 示 盤 面
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;