演算法基本概念2-問題解析與流程控制

演算法的表示

有時候，為了讓別人能了解我們解決問題的方法，我們會把想法表達成一系列的步驟與流程，其主要精神是建立思考.表示法有以下三種

1.文字描述法

範例:泡麵

1.將開水滾燙

2.打開泡麵碗

3.打開調味包

4.放進調味包

5.沖泡開水

6.經過三分鐘後

7.完成泡麵

8.拿出筷子吃麵

9.吃完回收碗筷

2.流程圖(解決問題的步驟抽象化即把"步驟"抽象成"流程")

我們將前面文字描述以「流程圖」表達，使得整個過程更加容易閱讀

抽象化

(1)定義

流程圖(flow chart)就是利用各種方塊圖形、線條及箭頭等符號來表達問題的解決問題的步驟及進行的順序

圖片來源:108課綱高中資科-科有出版社

(2)程式流程圖繪製原則

範例-標準化流程(SOP)

(3)程式流程圖優缺點

*3.虛擬碼(此單元可略過)

虛擬碼說明: 虛擬碼並不是真的要在電腦上執行，所以只要能看得懂就行了、沒有什麼語法要遵守。 簡單的說，Pseudo code (虛擬碼)是讓不同電腦程式語言的程式設計師可以用來溝通程式的一種非正式、接近自然語言的工具。

牛刀小試

食譜 vs. 演算法

Q:思考一下:是不是所有人拿到這個食譜都可做出來像大廚一樣煮出來的美味呢?

解說

我們跟著食譜一步一步的做，最後希望做出看起來和照片差不多的東西；然而，最終的結果往往不如預期，為什麼呢？ 其實問題往往出在食譜裡：

「小火煮」到底火多小?

「約30分」到底是幾分鐘?

「鹽巴少許」，少許是多少？

「醬油3匙」，哪一種匙呢？

「大火油炸到焦黃」，到底火多大?何謂焦黃呢？

食譜的問題出在不明確的文字敘述

Q:思考一下:如何評斷一個食譜的好壞呢?

解說:

好的食譜正是優秀的演算法

參考網站及資料引用

http://www.bookask.com/find/2590.html

:https://read01.com/j7LADx.html

因此把演算法定義成：

演算法就是明確、有效、最終會結束的可執行步驟

資訊科學演算法的特性

正確的演算法，應該能夠將輸入的資料，經過電腦有限次的運算後，得到所要的輸出資料， 且要完全符合以下五個特性

資料引用:教育部高中學科中心99課綱

牛刀小試

題目

完全符合演算法五項特性條件(完全:T.不完全:F)

不符合演算法五項特性條件請寫出不符合哪一項(寫出一項即可)

煎鮭魚加一點點檸檬汁

2+3=5

提示:演算法五大特性:輸入.輸出.有效.有限.明確

資訊科學演算法

(1)廣義

根據韋伯字典的定義，凡是為解決某一特定問題的一步一步程序(a step-by-step procedure for solving a problem)均可以稱為演算法。

(2)狹義

演算法是一個由一些步驟所構成的集合，依循這些步驟得以解決數學問題或完成計算機過程。從計算的角度給定演算法的嚴謹定義如下：

由有限(finite) 步驟(step) 所構成的集合，依照給定輸入(input) 依序執行每個明確(definite) 且有效(effective) 的步驟，以便能夠解決特定的問題；而步驟的執行必定會終止(terminate)，並產生輸出(output)

運用運算思維解決問題

(1)應用數學解題

Polya教授的How to Solve It（怎樣解題.張憶壽教授的譯本)

解題過程可分為四個階段：

(1) 理解問題 (understanding the problem)

(2) 設計解題策略 (devising a plan)

(3) 按步解題 (carrying out the plan)

(4) 回顧解答 (looking back)

(2)應用資訊科學解決問題

圖片引用https://shouzo.github.io/2017/07/20/Data_Structure_Book/

實作1- 數獨 (Sudoku)

資料來源:http://oddest.nc.hcc.edu.tw/

基本題

 

 

1

 

4

 

2

 

3

 

 

 

 

 

 

 

上圖是一個數獨遊戲的版面。 試在上圖填上 1， 2， 3， 4 使得每個2*2格內的數字不能重複.每個數字在每直行、每橫行也不能重複

進階題

活動說明:

1.試完成以上數獨。在進行解難途中， 留意自己的步驟及所採取之策略。

2.三位同學一組， 用兩分鐘時間討論及比較各人所用的解題策略是否相同。 三位同學是否利用同一方法去解決問題?

活動目的:

1.在解決問題時， 我們會使用不同的方法。以數獨遊戲為例，有些同學可能會隨意在格上放上一些數字，看看結果與要求是否乎合，直到所試的結果與要求相乎(這種方法稱為嘗試錯誤法.試湊法Trial-and-error approach)；在電腦科學領域稱為窮舉法或暴力法

2.有些同學會用一些較有系統的方法，一步一步把答案推導出來。學習資訊科學的其中一個重要原因，就是要去學習解決問題

Q:思考一下:在操作數獨遊戲中，你是如何解決問題?

實作2-河內塔

遊戲動畫展示及練習:

 

遊戲活動說明:

試完成河內塔遊戲。在進行解決問題中， 留意自己的步驟及所採取之策略。

Q:思考一下:在操作河內塔遊戲中，你是如何解決問題(過關)?

解說

依照密技所指示的步驟來操作，無論誰每次都可以過關。這種為遊戲通關設計的密技(定式)，也算是不錯的演算法

http://www1.mtjh.kh.edu.tw/~t394/ago/honoi.htm

http://simonsays-tw.com/web/Recursion/Iteration&Recursion.html