第四次:演算法基本概念2-問題解析與流程控制
初探演算法學習單2下載
實作1-資訊科學中的演算法及應用
(看到4分28秒即可)
Q1:思考一下:在影片中你看到了什麼演算法?應用在哪一些領域?
推薦書籍
評量:撰寫學習單第一題
資訊科學中的演算法
資訊科學演算法的定義
(1)廣義
根據韋伯字典的定義,凡是為解決某一特定問題的一步一步程序(a step-by-step procedure for solving a problem)均可以稱為演算法。
(2)狹義
演算法是一個由一些步驟所構成的集合,依循這些步驟得以解決數學問題或完成計算機過程。從計算的角度給定演算法的嚴謹定義如下:
由有限(finite) 步驟(step) 所構成的集合,依照給定輸入(input) 依序執行每個明確(definite) 且有效(effective) 的步驟,以便能夠解決特定的問題;而步驟的執行必定會終止(terminate),並產生輸出(output) |
評量:撰寫學習單第二題
Programming Thinking Process(程式思維過程)
當有一個待處理的問題時,我們將會依照以下的過程進行電腦程式設計:
1.用人類(自己)的思考方式去理解、了解這個問題。
2.將我們的理解改用電腦程式邏輯思考。
3.產出程式化的處理過程描述。
4.此程式化的處理過程描述選擇合適程式語言,如(C、Java、Python…)等實作產生電腦程式。
這個過程中真正困難的地方,應該是在「將我們的理解改用電腦程式邏輯思考」並且「產出程式化的處理過程描述」。「電腦程式邏輯思考」應該才是學習程式設計者的任督二脈,而「產出程式化的處理過程描述」就是虛擬碼(Pseudo code)的功用。
範例1: 問題描述:『爸爸有6個蘋果,拿走3個還有幾個?』
1.人類思考:6-3=3
2.電腦程式邏輯思考:『爸爸有一個箱子叫做A,裡面有6個蘋果,拿走了3個,裡面還有幾個?』
問題定義及抽象化: 將具體問題符號化(抽象化)即實際問題轉化為數學問題,建立數學模型。其中A就是變數,有了變數我們必須有一個方法將數值放入其中
3.虛擬碼示例
A ← 6 (6的值給A.←這個反向箭頭符號是指定或賦值的意思) Print(A-3) |
解說
演算法的表示2
虛擬碼(Pseudo Code)
虛擬碼說明: 虛擬碼並不是真的要在電腦上執行,所以只要能看得懂就行了、沒有什麼語法要遵守。 簡單的說,Pseudo code (虛擬碼)是讓不同電腦程式語言的程式設計師可以用來溝通程式的一種非正式、接近自然語言的工具。
4.程式語言實作
應用資訊科學演算法解決問題
實作2-電腦解決問題-數學累加問題
範例:求出1+2+3+ … + 99+100 (從1加到100)的和。
數學家的故事:「高斯」的小時候
運用Scratch求1+2+3+...+N的程式
問題1:為何電腦可以計算得如此快.它是套公式嗎?
解說:
1.因為電腦擁有資料處理速度快及儲存容量大....等特性
運算思維解析問題
1.求出從1+2+3+...100的和,如果我們就是從1開始,先兩個數相加,然後再用這兩個數相加的結果與後一個數相加,一直加到100,如先計算1+2=3,然後計算3+3=6,然後6+4等於10,如此一直加到100,這樣一定可以計算出來,但此方法非常花時間且沒效率。
高斯數學家的解法
圖片來源:https://zhuanlan.zhihu.com/p/53205895
2×(1+2+...+100) =101×100=100100 1+2+...+100 =100100÷2=5050 |
評量:撰寫學習單第三題
2.如果用人工計算求1+2+3+...100的和是非常費時的,但我們利用程式設計讓電腦去做卻是非常簡單的事情,因為這種有規律的計算恰好是電腦最擅長的事情。所以我們不需要去用技巧公式,我們只需要想一種演算法,能夠讓電腦正確完成計算。
3.連續相加就是拿上一個結果和下一個數相加得到一個新的和,然後再拿這個和與下一個數相加,這是很有規律的,我們使用循環過程。為了完成這個循環相加,我們需要使用兩個變量:一個是數字,一個是和,計算算式如下:
和 ←和+數字 |
4.數字是一個變量,每執行一次要增加1,算式=號右邊的和就是數字加之前的所有數之和,加上數字之後的結果成為一個新的和,然後再用這個和與下一個數進行相加,又的一個新的和,如此循環,一直到數字變為100為止。
數字 ← 數字+1 |
5.虛擬碼示例
首先可以定義兩個變量 i(記錄1到100變化的加數) ,S(記錄累加的總和),演算法以虛擬碼的寫法可以表示為
步驟1:i←1,s←0(設定數字為1.總和為0==>初始化) 。 步驟2:s←s+i(設定總和為總和+數字==>累加和) 。 步驟3:i←i+1(設定數字 = 數字+1==>規律性) 。 步驟4:假如i大於100就結束並印出總和s,否則返回重新執行步驟2。 |
Tracing an algorithm
i與s變數的數值變化如下表
i |
s |
1 |
1 |
2 |
3 |
3 |
6 |
4 |
10 |
5 |
15 |
|
|
|
|
100 |
5050 |
由上例的演算過程得知演算法的基本原則及特性符合明確性、有限性、正確性和具有結果的輸出。
6.程式實作
總結:本題看上去很簡單,但卻是理解演算法的一個很好的入門題,需要用到循環執行、變量以及加法指令等知識,可以對變量有一個更深刻的認識和理解。
評量:撰寫學習單第四題
參考資料:
Scratch編程入門練習作業—求連續數之和
https://kknews.cc/news/ky8ex98.html
https://kknews.cc/education/g225rr9.html
簡介演算法
資訊科學演算法小結
1.演算法是用來解決問題
2.演算法將解法切割成不同步驟
3.演算法的解決問題的步驟是精確(明確)的,不靠人類的直覺與猜測
4.程式(軟體)設計的思維最重要是演算法,而演算法是建立在數學思維上的
因為上面的幾個特性,我們才能夠藉由將演算法編寫成程式利用電腦做運行計算,來解決我們生活上的問題
作業上傳到雲端
1.點自己班的連結.輸入各班密碼
2.點自己的座號資料夾
3.點上傳
4.選桌面你的作業107****alogrithm02.doc
5.檢查是否上傳成功