資源簡介

(共21張PPT)
第三章 算法基礎
第三章 算法基礎
Chapter Three Algorithm Basics
匯報人
時間：05.16
體驗計算機解決問題的過程
第一部分
算法及其描述
第二部分
CONTENTS
目錄
第三章 算法基礎
創設情景，提出問題
開學時同學們紛紛購買用于學習的各種文具，假如同學手中有50元現金，分別購買單價為6元的筆記本，單價為5元的簽字筆，和單價為4元的橡皮，每種文具至少一個，請問各種文具應該購買何種數量，才能讓手中的資金最大化利用（即剛好用完）呢？
筆記本
單價：6元/本
簽字筆
單價：5元/支
橡皮
單價：4元/塊
需求分析
問題描述：
三種商品單價分別為6元，5元，4元；
用于購買商品的總資金為50元；
需求：
現求三種商品分別的購買數量，可讓資金剛好用完（要求每種商品的購買數量不得小于1）。
如果假設購買三種文具的數量分別為x，y，z
同學們是否可以據此列出含有x，y，z的數學方程來表達這一關系呢？
思考
第三章 算法基礎
小組討論
討論要求：
（1）列出含有x，y，z的求解方程
（2）分析x，y，z的取值是否存在界限范圍，如果有，這個界限范圍是多少？
（3）求解該方程的方法是什么？
6x+5y+4z=50
極限情況下，假設y和z都為1，則x可取到最大值為6，同理，y有最大值為8，z有最大值為10
故，1 ≤ x ≤ 6，1 ≤ y ≤ 8，1 ≤ z ≤ 10
第三章 算法基礎
問題解決
由于三元一次方程6x+5y+4z=50不存在其它約束條件，可以嘗試把x，y，z的取值都計算一次來判斷其是否滿足條件：
思路： 令y=1，z=1，令x=1，計算6x+5y+4z是否等于50；
令y=1，z=1，令x=2，計算6x+5y+4z是否等于50；
……
令y=1，z=1，令x=6，計算6x+5y+4z是否等于50；
……
令y=2，z=1，令x=6，計算6x+5y+4z是否等于50；
找到：x=6，y=2，z=1是方程的一個正整數解，但是……解唯一嗎？
思
考
第三章 算法基礎
第三章 算法基礎
算法是指在有限步驟內求解某一問題所使用的一組定義明確的規則。通俗的說就是用計算機求解某一問題的方法，是能被機械執行的動作或指令的有窮集合。
自然語言描述算法
使用日常交流所用語言來描述算法（如漢語、英語等）
例：
①輸入a，b的值；
②如果a大于b，則把a的值賦值給max。如果a不大于b，則把b的值賦給max；
③輸出max；
流程圖描述算法
使用程序框圖來描述算法
Max=b
Max=a
開始
結束
a>b？
輸入a、b
輸出Max
Y
N
第三章 算法基礎
描述算法的常用方法（比較a,b的大小，并輸出較大的數）
開始/結束
輸入/輸出
處理框
判斷框
流程線
連接點
流程圖又叫程序框圖，是算法的一種圖形化表示方法，相較于自然語言，更形象、直觀、易理解。使用流程圖描述算法可使算法的流程描述的清晰、簡潔。
流程圖的基本圖形及其功能
第三章 算法基礎
自然語言描述算法
流程圖描述算法
使用程序框圖來描述算法
Max=b
Max=a
開始
結束
a>b？
輸入a、b
輸出Max
Y
N
偽代碼描述算法
介于自然語言與計算機語言之間的文字與符號。不使用圖形符號，書寫方便 ，易于理解。
例：
if a>b:
max=a
第三章 算法基礎
描述算法的常用方法（比較a,b的大小，并輸出較大的數）
使用日常交流所用語言來描述算法（如漢語、英語等）
例：
①輸入a，b的值；
②如果a大于b，則把a的值賦值給max。如果a不大于b，則把b的值賦給max；
③輸出max；
設計算法
① t=0（把0賦值給t）;
② x=1;
③ y=1;
④ z=1;
⑤ 如果滿足式子6x+5y+42=50，則解的個數加t (即t=t+1)，并輸出這個解(即輸出t，x，y，z的值) ;
⑥ z=z+1（把z+1的值賦值給z）;
⑦ 如果z≤10則轉步驟⑤，否則繼續步驟⑧;
⑧ y=y+1;
⑨ 如果y≤8則轉步驟④，否則繼續步驟⑩;
⑩ x=x+1;
如果x≤6則轉步驟③，否則繼續步驟 ;
結束。
自然語言描述算法
流程圖描述算法
第三章 算法基礎
設計算法
用偽代碼描述算法
t=0
for x in range(1,7):
for y in range(1,9):
for z in range(1,11):
if(x*6+y*5+z*4==50)
{t=t+1;
輸出解的個數t和三個整數x,y,z}
第三章 算法基礎
編寫程序
第三章 算法基礎
打開python編輯器嘗試編寫程序
調試運行程序
打開老師文件下的“三元一次方程1、2、3、4”并運行程序
語法錯誤
第三章 算法基礎
調試運行程序
打開老師文件下的“三元一次方程5”并運行程序
算法有問題
邏輯錯誤
修改程序的錯誤后再調試運行
第三章 算法基礎
根據“三元一次方程”程序，總結算法的特征
有窮性 執行有窮步之后結束，計算步驟是有限的
確定性 執行的每一步驟都必須有確切的定義
數據輸入 0個或多個數據輸入
數據輸出 1個或多個數據輸出
可行性 基本可執行步驟的集合，有限時間內完成。
第三章 算法基礎
分析問題
求最佳購買方案、已知商品單價和總價、求最佳購買方案，轉化為求三元一次方程6x+5y+4z=50正整數解集
設計算法
遍歷所有取值可能
編寫程序
用Python語言實現計算程序
調試運行
運行程序，得出結果
第三章 算法基礎
計算機解決問題的一般步驟
02 算法及其描述
三種基本控制結構
使用三種基本控制結構組合來描述算法，可以改善算法的清晰度，提高算法的可讀性。
第三章 算法基礎
小明編寫好解密程序后，調試運行時，程序沒有報錯且能順利運行，卻不能正確解密，造成這個結果的原因是（　　）。A．解密算法邏輯錯誤 B．程序語句語法錯誤C．程序過期了 D．程序設計窗口配置不對
人們利用計算機解決問題的基本過程為（ ）
①調試運行程序 ②分析問題 ③設計算法 ④問題解決 ⑤編寫程序
A①②③④⑤ B②④③⑤① C④②③⑤① D②③⑤①④
D
A
6步驟①輸入圓的半徑; 步驟②求圓的面積; 步驟③輸出圓的面積。
以上算法的描述方法屬于( )
A.自然語言描述法 B.流程圖描述法 C.偽代碼描述法 D.簡碼描述法
A
第三章 算法基礎
實踐
在《幾何原本》一書中，歐幾里得闡述了關于求兩個正整數的最大公約數的過程，這就是著名的歐幾里得算法——輾轉相除法，其具體過程如下:
設給定的兩個正整數為m和n，求它們的最大公約數的步驟為:
以m除以n，令所得的余數為R。
若R=0，則輸出結果n，算法結束;否則，繼續步驟③。
令m=n，n=R，并返回步驟①繼續進行。
用流程圖將上述算法表示出來，試探索歐幾里得算法在現實生活中有哪些應用，舉出兩個應用實例。
匯報人
時間：05.16
THANKS

展開更多......

收起↑