演算法基本概念-問題解析

運用運算思維概念進行問題解析

在日常生活中，我們往往要去面對和解決不同的問題。 解決問題的能力成為一項很重要的共通能力

活動設計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

       

       

      認清問題

      以上句子並未能清楚列明要解決的問題。要實實在在地製作出「一些茶」，我們還要進一步認清問題，並向要求者 (用戶) 詢問以下問題：

      1. 要製作哪一種茶 (紅茶? 香片? 奶茶?) (詢問這個問題能幫助我們決定使用什麼材料和在建立解決方法時使用什麼步驟。)
      2. 製作出來的茶是熱的還是凍的? (詢問這個問題能幫助我們決定使用什麼材料 (輸入)，因為若用戶想製作凍茶，我們便需要準備冰塊)
      3. 「一些」代表多少? (一杯? 一煲?)

       

      假設用戶的答案如下：

      製作一杯凍檸檬茶

      分析問題

      製作一杯凍檸檬茶需要以下輸入及輸出：

      輸入(源材料) :

      水、糖水、檸檬、紅茶、冰、杯、飲管、匙

      輸出：

      凍檸檬茶

      結構圖：

      見下圖

       

      設計算法

      1. 把開水煲滾
      2. 把滾水冷卻成凍滾水，放進冰箱以製作冰
      3. 把部份滾水留下來沖茶
      4. 把檸檬切片
      5. 把茶包、冰及檸檬放進杯中
      6. 倒入糖水
      7. 倒入凍滾水
      8. 放入匙及飲管

      建立解決方法

      實踐以上算法

      測試/ 除錯

      測試：若供自己飲用的話，可試飲凍檸檬荼，看看味道是否合適。(例如是否太淡? 是否太甜? 是否不夠凍? )

      除錯:

      若凍檸茶太淡，可加入糖水或多加一片檸檬

      若凍檸茶太甜，可加入多些凍滾水

      若凍檸茶不夠凍，可加多些冰

      若凍檸茶有怪味，可看看原材料有沒有怪味，有否變壞或有否過期如有需要，並找出怪味的源頭

      製作文件

      嚴格來說，我們應把以上步驟寫入文件，以便日後參閱。由於製作凍檸茶沒有牽涉什麼重要技術，這部份可以豁免。

       

       活動設計5-討論

      從上述例子中，我們看到釐清及準確地界定問題範圍的重要性：最原始的問題是「製作一些茶」，而這個問題界定很並不準確。如上文所說，我們最少要知道要製作哪一種茶、製作多少茶等基本資料，才可進一步去考慮輸入輸出及製作方法。

      制訂及準確地界定問題範圍是一個重要的步驟，若這步驟做得不出，得出來的製成品便不能解決原來用戶想解決的問題。

      討論題:

      在認清問題後，若以上的檸檬茶問題由「製作一杯凍檸檬茶」變成「為可樂公司製作一款新的檸檬茶以推出華人華市場」，上表的內容會有哪些改變?

      在某些情況下，若我們因種種原因而未能清楚地界定問題的某些部份時，我們唯有作合理的假設，並在認清問題時清楚列出所有假設。