ch5问题解决答辩课件

1、ch5問題解決國立台中二中 劉洲溶第1页，共46页。課綱節數：10(2學分)26(4學分)第2页，共46页。5-1電腦解題概論 5-1-1電腦解題簡介5-1-2電腦解題在各領域應用 第3页，共46页。教學目標認識垂直式思考及水平式思考。了解電腦的特性適合垂直式思考之解題。能以循序漸進的流程提出解決問題的可能方法。培養學生分析問題及解決問題的能力。第4页，共46页。垂直式思考VS水平式思考 垂直思考具有選擇性，水平思考則具有創造性。垂直思考乃序列性step by step，水平思考則為跳躍式。垂直思考必須通常有正確解答，水平思考則無對錯之分。垂直思考依循最有可能的途徑，水平思考則探索最不可能的。

2、垂直思考是的確定的，水平思考則和機率有關。垂直思考像是用來把同一個洞挖得更深，而水平式思考則是在別的地方另外挖洞。第5页，共46页。水平思考法實例：寫出能想到有關電燈泡的所有用途？ 第6页，共46页。水平思考法實例：問題：父母親攜帶兩個孩子去學校辦理新生入學手續。這兩個孩子的臉幾乎一模一樣，出生的年月日都相同，而且是同一父母生的。老師問：你們兩是雙胞胎嗎？不是。兩個孩子異口同聲的回答。老師奇怪了。這是怎麼一回事。 第7页，共46页。垂直思考法實例： 食譜：方法廚師：電腦菜名：水餃材料：冷水麵糰400公克豬絞肉320公克薑 8公克蔥12公克高麗菜或韭菜200公克調味料：鹽3公克雞精粉4公克細砂糖

3、3公克醬油10料理米酒10水50白胡椒粉1茶匙香油1大匙做法：1.冷水麵糰分割成每個重約10公克的小麵糰，再分別桿圓、桿薄成水餃皮備用。2.薑切末、蔥切碎；高麗菜洗淨後切丁，用1公克的鹽抓勻，醃漬約10分鐘後，擠去水分備用。3.豬絞肉放入鋼盆中，加入鹽後攪拌至有黏性，再加入雞精粉、細砂糖及醬油、料理米酒拌勻後，將50的水分兩次加入，邊加水邊攪拌至水分被肉吸收，最後再加入作法2的高麗菜、蔥碎、薑末、白胡椒粉及香油拌勻成內餡。4.取作法1水餃皮一張，包入15公克的作法3內餡，包起捏緊封口成水餃。5.燒一鍋水，水開後放入作法4包好的水餃，以小火煮約5分鐘，至水餃浮起呈鼓鼓狀即可。 第8页，共46页。

4、電腦的特性計算速度快準確處理資料量大不會自主式思考 第9页，共46页。適合用電腦解決的問題大量資料的計算、比對、搜尋步驟明確例如：排序、搜尋、 第10页，共46页。不適合用電腦來解決的問題純機率問題和人有關和情意第11页，共46页。電腦解題在各領域應用實例：路線指引資料壓縮輾轉相除法、萬年曆問題(閏年問題)求質數問題 （質因數分解)離散數學問題益智遊戲-.tw/linss/網路資料搜尋網路訂票系統第12页，共46页。5-2電腦解題程序 5-2-1問題分析5-2-2解題方法設計5-2-3測試與修正 第13页，共46页。學習目標 初步認識可運用之電腦解題工具。了解電腦解題程序中問題分析的方法。熟悉

5、電腦解題程序中解題方法設計。了解電腦解題程序中以工具測試與修正方法。建立學生程式設計的基本觀念。 第14页，共46页。分析問題已知的資料、狀況和條件要達成的目標可用的資源問題的限制範圍第15页，共46页。解決問題實例一 例：四個連續整數的乘積為3204，求此四數?四數中，沒有10 ( 否則個位數是0 ) 至少有一數小於10 ( 否則乘積大於四位數 ) 四數皆小於10 ( 因為四數不包含10 ) 四數中沒有5 ( 否則個位數是5或0 )第16页，共46页。解決問題實例二假設只有兩個小水桶，一個容積為4公升，另一個是9公升，要如何從河中舀出6公升的水。第17页，共46页。解決問題實例三請列出求2到

6、30之間所有的質數。 第18页，共46页。問題分析質數定義：除了1與數字本身沒有其它因數的自然數，稱為質數因數範圍：任一自然數N，N之最大的質因數為小於或等於 SQR(N)輸入：一個數字輸出：一數列第19页，共46页。解題方法設計(1)先列出2到30所有數字，已知2為質數，30的最大因數為小或等於sqr(30)。故30的最大因數為5。(2)找出2的倍數，然後將所有2的倍數改為0，然後列印輸出數字2。產生新的一串數字中，第一個非0的數字是3，3即為質數。(3)找出3的倍數，然後將所有3的倍數改為0，然後列印輸出數字3。產生新的一串數字中，第一個非0的數字是5，5即為質數。(4)找出5的倍數，然後

7、將所有5的倍數改為0，然後列印輸出數字5。(5)產生新的一串數字中，列印輸出所有非0的數字。所有列印輸出的數字為即為2到30之間所有的質數。 第20页，共46页。解題流程(1)列出2到30所有數字2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25、26、27、28、29、30(2)找出2的倍數，然後將所有2的倍數改為0，然後列印輸出數字。產生新的一串數字中，第一個非0的數字是3，3即為質數。0、3、0、5、0、7、0、9、0、11、0、13、0、15、0、17、0、19、0、21、0、23、0、25、0、27、0、29

8、、0。列印輸出結果：2(3)找出3的倍數，然後將所有3的倍數改為0，然後列印輸出3數字。產生新的一串數字中，第一個非0的數字是5，5即為質數。0、0、0、5、0、7、0、0、0、11、0、13、0、0、0、17、0、19、0、0、0、23、0、25、0、0、0、29、0。列印輸出結果：2、3(4)找出5的倍數，然後將所有3的倍數改為0，然後輸出5。0、0、0、0、0、7、0、0、0、11、0、13、0、0、0、17、0、19、0、0、0、23、0、0、0、0、0、29、0。列印輸出結果：2、3、5(5)產生新的一串數字中，列印輸出所有非0的數字。所有列印輸出的數字為即為2到30之間所有的質數。

9、列印輸出結果：2、3、5、7、11、13、17、19、23、29第21页，共46页。測試與修正以google 計算工具進行測試(順帶介紹雲端運算之概念, 以電腦解決問題，不一定是個人電腦，也可能是browser加上遠端伺服器)第22页，共46页。第23页，共46页。第24页，共46页。第25页，共46页。=IF(MOD(A1,$A$1)=0,0,A1) 第26页，共46页。=IF(MOD(A2,$B$2)=0,0,A2) = IF(MOD(A3,$D$3)=0,0,A3) 第27页，共46页。第28页，共46页。實作練習閏年判斷以逼近法求根號N第29页，共46页。5-3演算法概論 5-3-1演

10、算法特性5-3-2演算法表示方法5-3-3資料結構與演算法5-3-4演算法與電腦解題 第30页，共46页。教學目標了解何謂演算法。認識演算法表示方法。了解程式設計與資料結構與演算法的關係。培養以演算法思考解決問題的能力。 第31页，共46页。演算法示例一河內塔f(n)=2*f(n-1)+1第32页，共46页。演算法示例二閏年的判定解題步驟如下：輸入N，先看看N能否被4整除，若是不能被4整除，則不是閏年，若是N能被4整除但不能被100整除，是閏年；若是能被4整除，又能被100整除，但不能被400整除，則不是閏年，若是能被4整除，又能被100整除，又能被400整除，是閏年。 第33页，共46页。演

11、算法的特性 1.完整性 ：要有輸入，並且至少一個的輸出當結果。2. 明確性 ：演算法中的程序代表的涵義須明確且可行，不能有模糊不清的情況。3. 可決定性 （Deterministic）：在明確而定義清楚的程序被執行後，演算法所達到的結果應該是可預期的。4. 有限的 （Finite）：演算法必須要能在有限的步驟內完成或終止，而且所使用的資料量也是有限的。 第34页，共46页。演算法表示方法 代數的表示法表格式的表示法 虛擬碼表示法 流程圖表示法 第35页，共46页。結構化的演算法 循序結構選擇結構重覆結構 第36页，共46页。資料結構與演算法 變數的意義變數與演算法 例：（1+2+3+N）的演算

12、法？第37页，共46页。資料結構與演算法-續變數與資料型態常用的資料型態介紹陣列(array)堆疊(Stack)佇列(Queue) 鏈結串列(linked list)程式設計=資料結構+演算法 第38页，共46页。電腦解題之演算法實例探討 攝氏、華氏溫度換算。BMI計算與身材判斷。(閏年判斷)累加計算。逼近法求N的平方根。二分搜尋法。氣泡排序法。第39页，共46页。5-4電腦解題實作5-4-1電腦解題工具介紹文書處理軟體繪圖軟體流程圖程式設計樂高機器人第40页，共46页。流程圖繪製Dia for Windows可用(相關網站：http:/dia-installer.de/index_en.html)Visio版權軟體Word第41页，共46页。程式