資源簡介

(共16張PPT)
3.2算法及其描述
編制計算機程序解決問題的全過程
分析問題
設計算法
編寫程序
調試運行
檢測結果
編程能夠訓練思維，它體現(xiàn)了一種抽象交互關系，自動化執(zhí)行的思維模式。
編程重要的是邏輯思路，確定解決問題的詳細方法和步驟，即設計算法。算法是指在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則，是能夠被機械執(zhí)行的動作或者指令的有窮集合。
在《幾何原本》中，歐幾里得闡述了關于求兩個正整數(shù)的最大最大公約數(shù)的過程，這就是著名的歐幾里得算法----輾轉相除法，其具體過程如下：
設給定的兩個正整數(shù)為m和n，求它們的最大公約數(shù)的步驟為：
①以m除以n，令所得的余數(shù)為R。
②若R=0，則輸出結果n，算法結束；否則，繼續(xù)步驟③
③令m=n，n=R，并返回步驟①繼續(xù)進行。
實踐
設給定的兩個正整數(shù)m=112和n=64，利用輾轉相除法，求它們的最大公約數(shù)。
算法如下：
（1）112除以64，余數(shù)為--------；
（2）-------除以-------余數(shù)為-------
（3）-------除以-------余數(shù)為-------。
答：112和64的最大公約數(shù)為--------
48
64
48
16
48
16
0
16
算法的特征
數(shù)據(jù)輸入：一個算法有零個或多個輸入；
確定性：算法執(zhí)行的每一步必須有確切的定義，不可含混不清；
有窮性：一個算法在執(zhí)行有窮步之后必須結束；
數(shù)據(jù)輸出：一個算法有一個或多個輸出，即最后的結果
可行性：算法中執(zhí)行的任何計算步驟都可以被分解成基本的
可執(zhí)行的操作步驟，即每個基本步驟都可以在有限時間內(nèi)完成。
算法的描述
（1）用自然語言描述算法：比較容易理解，越詳細越好，但如果算法中含有比較多的分支或者循環(huán)操作等時，使用自然語言比較難將其清晰表示出來；同時由于自然語言的歧義性會導致算法執(zhí)行的不確定性。
如：咬死了獵人的狗
設給定的兩個正整數(shù)為m和n，求它們的最大公約數(shù)的步驟為：
①以m除以n，令所得的余數(shù)為R。
②若R=0，則輸出結果n，算法結束；否則，繼續(xù)步驟③
③令m=n，n=R，并返回步驟①繼續(xù)進行。
（2）用流程圖描述算法：用程序框圖來描述，使流程清晰、簡潔。
用輾轉相除法求兩數(shù)的最大公約數(shù)
（1）輸入m和n的值；
（2）用m除以n，令所得的余數(shù)為r；
（3）若r=0，則輸出n,算法結束，否則繼續(xù)（3）；
（4）令m=n，n=r，并返回步驟（1）。
開始
輸入m和n
r=m
%
n
r=0
輸出n
結束
m=n
n=r
否
是
牛刀小試：
利用流程圖描述求一元二次方程ax2+
bx+c=0的根
1.輸入a，b，c的值
2.令d=b
b-4
a
c
3.如果
d>=0
計算
x1=
x2=
輸出x1,x2
轉步驟4
否則輸出“方程無解”轉步驟4
4.結束程序
算法的描述
（3）用偽代碼描述算法：用介于自然語言和計算機語言之間的文字和符號來描述算法，易于理解，便于向計算機程序設計語言過渡。
m=input(“請輸入m的值”)
n=input(“請輸入n的值”)
R=m%n
while
R!=0:
{
m=n
n=R
R=m%n}
輸出n
算法舉例
有兩個瓶子A和B
，A瓶裝有雪碧，B瓶是可樂，問如何把雪碧和可樂互換。即A瓶原來雪碧，現(xiàn)改為盛可樂，B瓶則相反。
第一步：將A內(nèi)溶液倒入C瓶中
第二步：將B內(nèi)溶液瓶倒入A瓶中
第三步：將C內(nèi)溶液瓶倒入B瓶中
程序的三種基本結構
前面的算法描述中我們用到了順序結構、選擇結構、循環(huán)結構這三種基本控制結構。任何復雜的算法都可以使用這三種基本控制結構組合來表示。
語句1
語句2
順序結構表示程序中各個步驟按照出現(xiàn)的先后順序依次執(zhí)行。
程序的三種基本結構
選擇結構表示程序的處理步驟出現(xiàn)了分支，需要按照某一個特定的條件選擇其中一個分支執(zhí)行，有單選擇，雙選擇，多選擇。
條件
語句1
語句2
Y
N
程序的三種基本結構
循環(huán)結構表示反復執(zhí)行某些操作直到判斷條件為假或者為真時才結束循環(huán)。如輾轉相除法求兩數(shù)最大數(shù)
條件
條件
語句組
Y
N
Y
N
語句組
開始
輸入m和n
r=m
%
n
r=0
輸出n
結束
m=n
n=r
否
是
(1)人們利用計算機解決問題的基本過程為（
）
①調試運行程序
②分析問題③設計算法
④問題解決
⑤編寫
A.①②③④⑤
B.②④③⑤①
C.
④②③⑤①
D
②③⑤①④
(2)下面關于算法的描述，正確的是(
)。
A.算法不可以用自然語言描述
B.算法只能用流程圖來描述
C.一個算法必須保證它的執(zhí)行步驟是有限的
D.算法的流程圖表示法有零個或多個輸入，但只能有一個輸出
(3)計算機能直接識別、理解執(zhí)行的語言是(
)。
A.匯編語言B.
Pyhon語言C.
Basic語
言D.機器語言
(4)下列關于算法的敘述，正確的是(
)
A.解決一個問題的算法只有一種
B.有窮性是算法的基本特征之一
C.可行性不屬于算法基本特征
D.算法對程序設計沒有任何作用3.2算法及其描述
習題
一、選擇題
1.在求解“一元二次方程實數(shù)根”的算法中，如果方程不存在實數(shù)解，也要求輸出結果“無實數(shù)根”。此要求主要體現(xiàn)了算法特征中的（
B
）
A.有窮性?
B.數(shù)據(jù)輸出?
C.確定性
D可行性
2.下列問題不能用算法描述的是（
C
）
A.已知a、b、c的值，求一元二次方程ax2+bx+c=0（a≠0）的實數(shù)根
B.計算某個班級語文成績的平均分
C.列出方程y=2x+1的所有實數(shù)解
D.根據(jù)圓的半徑求圓的面積和周長
3.求交換兩個變量a
b的值的算法步驟如下：
①輸入變量ab的值
②輸出變量ab的值
③將變量a的值賦給變量b
④將變量b的值賦給變量c
⑤將變量c的值賦給變量a
⑥結束
其正確的順序是（
D
）
①②③④⑤⑥
B.①⑤④③②⑥
①③④⑤②⑥
D.①④③⑤②⑥
4.“如果下雨在體育館上體育課，不下雨則在操場上體育課”。有流程圖來描述這一問題時，判斷“是否下雨”的流程圖符號是（
B
）
矩形
B.菱形
C.平行四邊形
D.圓圈
5.執(zhí)行如圖所示的程序框圖，若輸出的S＝88，則判斷框內(nèi)應填入的條件是(
B
)
k>7?
B.
k>6?
C.
k>5?
D.
k>4?
二、填空題
1.程序的基本控制結構有
、
和
。（順序結構、選擇結構、循環(huán)結構）
流程圖中表示判斷的是
，表示計算和賦值的是
。（菱形、長方形）
介于自然語言和計算機語言之間的文字和符號來描述算法的是______________________。（偽代碼）
已知一個學生的語文成績?yōu)?9，數(shù)學成績?yōu)?6，外語成績?yōu)?9，求這個學生成績總分和平均分的一個算法如下，請將其補充完整：
第一步：取A=89，B=96，C=99.
第二步：
第三步：
第四步，輸出計算結果。
答案：計算部分D=A+B+C
計算平均分E=D/3

展開更多......

收起↑