演算法基本概念-問題解析
運用運算思維概念進行問題解析
在日常生活中,我們往往要去面對和解決不同的問題。 解決問題的能力成為一項很重要的共通能力
活動設計1- 數獨
|
|
1 |
|
4 |
|
2 |
|
3 |
|
|
|
|
|
|
|
上圖是一個數獨遊戲的版面。 試在上圖填上 1, 2, 3, 4 使得每個2*2格內的數字不能重複.每個數字在每直行、每橫行也不能重複
活動說明:
1. 試完成以上數獨。在進行解難途中, 留意自己的步驟及所採取之策略。
2. 三位同學一組, 用兩分鐘時間討論及比較各人所用的解題策略是否相同。
三位同學是否利用同一方法去解決問題?
活動目的:
在解決問題時, 我們會使用不同的方法。以數獨遊戲為例,有些同學可能會隨意在格上放上一些數字,看看結果與要求是否乎合,直到所試的結果與要求相乎(這種方法稱為嘗試錯誤法.試湊法Trial-and-error approach);在電腦科學領域稱為窮舉法或暴力法,有些同學會用一些較有系統的方法,一步一步把答案推導出來。學習資訊科學的其中一個重要原因,就是要去學習解決問題的方法及技巧
解決問題
在Polya教授的How to Solve It書(張憶壽教授的譯本)
解題過程可分為四個階段:
(1)
理解問題
(understanding the problem)
(2)
設計解題策略
(devising a plan)
(3)
按步解題
(carrying out the plan)
(4)
回顧解答
(looking back)
系統化(System-ait Approch)解決問題
使用電腦解決問題
說明
1.釐清問題
在認清問題時,我們要清楚地把問題定義好,找出使用者需要解決什麼。
我們可採用以下方法去蒐集使用者的需求:
2.分析問題
A.找出問題的輸入及輸出
在分析問題時,我們需要找出問題的輸入、輸出:
例:要解決的問題:製作一個木偶。
輸入: |
木、布、繩、釘 |
輸出: |
木偶 |
活動設計2- 找出問題的輸入及輸出
找出以下問題的輸入及輸出
1. 找出在英文科測驗中獲得全班最高分的同學
2. 計算除數
1. _______________________________________________
2. _______________________________________________
B.拆解問題
除了找出問題的輸入及輸出外,在分析問題時,我們還要利用由上而下法把問題拆分成複雜性較少、描述較仔細且較易處理的子問題 (模組),然後把子問題逐一解決。
由上而下法又可稱為逐步求精法或模組化程序設計。我們可以利用結構圖來演示問題與子問題之間的關係。
活動設計3- 畫結構圖
範例:為「製作餐肉公仔麵」進行模組化分析,並用結構圖展示分析結果
說明
港式茶餐廳必吃:午餐肉公仔麵
公仔牌方便麵、梅林午餐肉、荷包蛋、蛋液、綠葉菜一把、干蝦
結構圖
|
REF ANS
活動設計4- 製作一杯茶
某人要求你為他製作一些茶。請寫出各步驟所需的步驟.依據上述撰寫解決問題說明書
認清問題 |
|
||||
分析問題 |
輸入/輸出分析
結構圖 (請於下頁繪畫結構圖) |
||||
設計算法 |
|
||||
建立解決方法 |
依照以上方法 |
||||
測試/ 除錯 |
|
||||
製作文件 |
|
結構圖
|
REF ANS
認清問題 |
以上句子並未能清楚列明要解決的問題。要實實在在地製作出「一些茶」,我們還要進一步認清問題,並向要求者 (用戶) 詢問以下問題:
假設用戶的答案如下: 製作一杯凍檸檬茶 |
||||
分析問題 |
製作一杯凍檸檬茶需要以下輸入及輸出:
結構圖: 見下圖
|
||||
設計算法 |
|
||||
建立解決方法 |
實踐以上算法 |
||||
測試/ 除錯 |
測試:若供自己飲用的話,可試飲凍檸檬荼,看看味道是否合適。(例如是否太淡? 是否太甜? 是否不夠凍? ) 除錯: 若凍檸茶太淡,可加入糖水或多加一片檸檬 若凍檸茶太甜,可加入多些凍滾水 若凍檸茶不夠凍,可加多些冰 若凍檸茶有怪味,可看看原材料有沒有怪味,有否變壞或有否過期如有需要,並找出怪味的源頭 |
||||
製作文件 |
嚴格來說,我們應把以上步驟寫入文件,以便日後參閱。由於製作凍檸茶沒有牽涉什麼重要技術,這部份可以豁免。 |
活動設計5-討論
從上述例子中,我們看到釐清及準確地界定問題範圍的重要性:最原始的問題是「製作一些茶」,而這個問題界定很並不準確。如上文所說,我們最少要知道要製作哪一種茶、製作多少茶等基本資料,才可進一步去考慮輸入輸出及製作方法。
制訂及準確地界定問題範圍是一個重要的步驟,若這步驟做得不出,得出來的製成品便不能解決原來用戶想解決的問題。
討論題:
在認清問題後,若以上的檸檬茶問題由「製作一杯凍檸檬茶」變成「為可樂公司製作一款新的檸檬茶以推出華人華市場」,上表的內容會有哪些改變?
在某些情況下,若我們因種種原因而未能清楚地界定問題的某些部份時,我們唯有作合理的假設,並在認清問題時清楚列出所有假設。