資源簡介

(共43張PPT)
信息技術(shù)必修一《數(shù)據(jù)與計(jì)算》
第三章 算法基礎(chǔ)
人工解決問題的過程
算法基礎(chǔ)
體驗(yàn)計(jì)算機(jī)解決問題的過程
計(jì)算機(jī)解決問題的過程
算法
算法的描述
數(shù)據(jù)的輸入與輸出
順序結(jié)構(gòu)的應(yīng)用
計(jì)算機(jī)程序與程序設(shè)計(jì)語言
算法及其描述
體驗(yàn)計(jì)算機(jī)解決問題的過程
01
探究
Q: 學(xué)期結(jié)束時(shí)，老師打算花50塊錢購買一些筆記本獎(jiǎng)勵(lì)表現(xiàn)優(yōu)秀的同學(xué)，請班長小明幫忙，小明決定同時(shí)買三種單價(jià)分別為6元、5元、4元的筆記本，錢剛好花完，請問可以有多少種方案？
人工解決問題
1. 提取題干信息：
總金額：50元
筆記本單價(jià)：6元、5元、4元
要求：錢剛好花完、同時(shí)買三種筆記本
①明確問題給出的條件
2. 轉(zhuǎn)換為數(shù)學(xué)方程，并列出可能的解：
方程：6x+5y+4z=50
方案 x y z 6x+5y+4z
一 1 4 6 50
二 1 8 1 50
三 2 2 7 50
四 2 6 2 50
五 3 4 3 50
六 4 2 4 50
七 6 2 1 50
可能的解：
②根據(jù)經(jīng)驗(yàn)和知識確定解決問題的方法
③解決問題
人工解決問題
人工解決問題的過程：
明確問題給出的條件--根據(jù)經(jīng)驗(yàn)和知識確定解決問題的方法--解決問題
但當(dāng)花費(fèi)的錢數(shù)需剛好為n時(shí)，數(shù)據(jù)量很大，人工處理效率很低。
因此我們需借助計(jì)算機(jī)工具，通過編制計(jì)算機(jī)程序來解決問題。
計(jì)算機(jī)解決問題
1. 提取問題需求情況和已知條件：
需求情況：同時(shí)購買三種類型且總價(jià)為50元的筆記本
已知條件：筆記本價(jià)格分別為6元、5元、4元
①分析問題
2. 給出解決問題的詳細(xì)方法和步驟：
①6元的筆記本數(shù)量x最少為1，最多為8；5元的筆記本數(shù)量y最少為1，最多為10；3元的筆記本數(shù)量z最少為1，最多為12。
②讓三類筆記本的數(shù)量x,y,z作為變量，在各自值域內(nèi)變化、組合。
③筆記本總價(jià)每剛好為50，則讓方案數(shù)t自加1。
②設(shè)計(jì)算法
計(jì)算機(jī)解決問題
3. 選擇一種計(jì)算機(jī)語言工具來編寫程序：
t=0
for x in range(1,9):
for y in range(1.11):
for z in range(1,13):
if x*6+y*5+z*4==50:
t=t+1
print(“方案數(shù)為”,t,“個(gè)”)
③編寫程序
4. 運(yùn)行程序，檢驗(yàn)程序執(zhí)行效果：
如果程序出錯(cuò)，可根據(jù)計(jì)算機(jī)提示的出錯(cuò)信息修改程序，重新調(diào)試運(yùn)行
④調(diào)試運(yùn)行程序
練一練
P27第2題：用計(jì)算機(jī)編程來求某一方程的解，通常的步驟是（ ）
①調(diào)試運(yùn)行程序 ②分析問題 ③設(shè)計(jì)算法 ④編寫程序
A. ②③④①
B. ①③④②
C. ③②④①
D. ②④③①
A
解析：計(jì)算機(jī)解決問題的過程：分析問題--設(shè)計(jì)算法--編寫程序--調(diào)試運(yùn)行程序
練一練
2. P28第7題：一位愛好程序設(shè)計(jì)的同學(xué)想通過程序設(shè)計(jì)解決“韓信點(diǎn)兵”的問題，
他制定的如下工作步驟，更為恰當(dāng)?shù)氖牵? ）
①調(diào)試運(yùn)行程序 ②分析問題 ③設(shè)計(jì)算法 ④問題解決 ⑤編寫程序
A. ①②③④⑤
B. ②③④⑤①
C. ④②③⑤①
D. ②③⑤①④
D
解析：計(jì)算機(jī)解決問題的過程：分析問題--設(shè)計(jì)算法--編寫程序--調(diào)試運(yùn)行程序
練一練
3. P28第8題：交通警察到達(dá)交通事故現(xiàn)場，開展工作的一般思路是（ ）
①觀察分析現(xiàn)場 ②收集必要的信息 ③進(jìn)行判斷和推理 ④給出處理方案
A. ②①③④
B. ①③②④
C. ③①②④
D. ①②③④
A
算法及其描述
02
算法
特征
有窮性：一個(gè)算法在執(zhí)行有窮步之后必須結(jié)束，即一個(gè)算法所包含的計(jì)算步驟是有限的。
確定性：算法執(zhí)行的每一個(gè)步驟必須有確切的定義。
數(shù)據(jù)輸入：一個(gè)算法必須有零個(gè)或多個(gè)數(shù)據(jù)輸入。
數(shù)據(jù)輸出：一個(gè)算法必須有一個(gè)或多個(gè)數(shù)據(jù)輸出。
可行性：每個(gè)計(jì)算步驟都可以在有限時(shí)間內(nèi)完成。
指在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。
是用計(jì)算機(jī)求解某一問題的方法，是能被機(jī)械執(zhí)行的動(dòng)作或指令的有窮集合。
練一練
4. P27第3題： 下面關(guān)于算法的特征，描述不正確的是（ ）
A. 有窮性：算法必須在有窮步之內(nèi)結(jié)束
B. 確定性：算法的每一步必須確切地定義
C. 輸入：算法必須至少有一個(gè)輸入
D. 輸出：算法必須至少有一個(gè)輸出
C
解析：一個(gè)算法應(yīng)是必須有0個(gè)或多個(gè)數(shù)據(jù)輸入
算法的描述
算法是對解題過程的精確描述，需要使用某種方法將其表示出來
自然語言
流程圖
偽代碼
用自然語言描述算法
例：若求方程6x+5y+4z=50的正整數(shù)解的個(gè)數(shù)t，則解決問題的算法步驟用自然語言描述算法，就是用人們?nèi)粘Ｋ玫恼Z言，如漢語、英語等來描述算法。
特點(diǎn)：通俗易懂，易于理解，
但文字冗長，容易產(chǎn)生歧義性
t=0;
x=1;
y=1;
z=1;
如果滿足式子6x+5y+4z=50，則解的個(gè)數(shù)加1(t=t+1)，并輸出一個(gè)解(輸出t,x,y,z的值);
z=z+1;
如果z<=12，則轉(zhuǎn)步驟⑤，否則繼續(xù)⑧；
y=y+1;
如果y<=10，則轉(zhuǎn)步驟④，否則繼續(xù)⑩;
x=x+1;
如果x<=8，則轉(zhuǎn)步驟③，否則繼續(xù)(12)
結(jié)束
用流程圖描述算法
特點(diǎn)：清晰簡潔，直觀易讀
但所占篇幅較大
例：若求方程6x+5y+4z=50的正整數(shù)解的個(gè)數(shù)t，則解決問題的算法步驟用流程圖描述算法，就是用流程框圖來描述算法的一種表示方法。
圖形形狀各異，功能不同
流程圖的基本圖形及其功能
圖形 名稱 功能
邏輯非運(yùn)算
開始/結(jié)束
表示算法的開始或結(jié)束
輸入/輸出
表示算法中變量的輸入或輸出
處理
表示算法中變量的計(jì)算與賦值
判斷
表示算法中的判斷
連接點(diǎn)
表示算法中的轉(zhuǎn)接
流程線
表示算法中的流向
用偽代碼描述算法
特點(diǎn)：書寫方便，格式緊揍
但語句不容易規(guī)范
例：若求方程6x+5y+4z=50的正整數(shù)解的個(gè)數(shù)t，則解決問題的算法步驟用偽代碼描述算法，就是用介于自然語言和計(jì)算機(jī)語言之間的文字和符號來描述算法。
t=0
for x in range(1,9):
for y in range(1,11):
for z in range (1,13):
if x*6+y*5+z*4==50;
t=t+2
print(x,y,z) #輸出三個(gè)整數(shù)x,y,z
print(‘方程的解一共有’,t, ‘種可能’)
算法三種描述方法的優(yōu)劣對比
算法描述的方法 優(yōu)勢 不足
自然語言描述 通俗易懂，易于理解 文字冗長，容易產(chǎn)生歧義性
流程圖描述 清晰簡潔，直觀易讀 所占篇幅較大
偽代碼描述 書寫方便，格式緊湊 語句不容易規(guī)范
邏輯非運(yùn)算
練一練
5. P29第13題：下列流程圖符號屬于輸入框的是（ ）
A. B. C. D.
B
解析：A代表處理，C代表開始，D代表判斷
練一練
6. 判斷題：用自然語言描述算法，比用流程圖更清晰簡潔（ ）
B
解析：流程圖描述算法比自然語言更清晰簡潔
7. 判斷題：使用流程圖描述算法存在歧義性，容易導(dǎo)致算法執(zhí)行的不確定性（ ）
B
8. 判斷題：算法只能用流程圖來描述（ ）
B
解析：存在歧義性的算法描述是自然語言
解析：算法描述有自然語言、流程圖和偽代碼
程序的三種基本控制結(jié)構(gòu)
在前面的用流程圖描述算法中，用到了以下三種基本控制結(jié)構(gòu)；
任何復(fù)雜的算法都可以用這三種基本控制結(jié)構(gòu)組合起來表示。
順序結(jié)構(gòu)
順序結(jié)構(gòu)是最簡單的一種結(jié)構(gòu)，表示程序中的各步操作按出現(xiàn)的先后順序執(zhí)行。
它的執(zhí)行順序是自上而下，依次執(zhí)行
BMI=體重 / （身高）2
輸入框身高、體重
選擇結(jié)構(gòu)
選擇結(jié)構(gòu)表示程序的處理步驟出現(xiàn)了分支，需要根據(jù)某一特定的條件選擇其中的一個(gè)分支執(zhí)行。
選擇結(jié)構(gòu)有單選擇、雙選擇和多選擇三種。
N
Y
BMI>25
輸出：體重正常
輸出：已超重
循環(huán)結(jié)構(gòu)
循環(huán)結(jié)構(gòu)表示程序反復(fù)執(zhí)行某個(gè)或某些操作，直到判斷條件為假（或真）時(shí)才可終止循環(huán)。
循環(huán)結(jié)構(gòu)可以減少程序重復(fù)書寫的工作量，用來描述重復(fù)執(zhí)行某段算法的問題，這是程序設(shè)計(jì)中最能發(fā)揮計(jì)算機(jī)特長的程序結(jié)構(gòu)。
k=50
z=z+1
k=6x+5y+4z
z<=12
Y
Y
N
N
練一練
9. 以下不是程序的基本控制結(jié)構(gòu)的是（ ）
A. 順序結(jié)構(gòu) B. 選擇結(jié)構(gòu)
C. 循環(huán)結(jié)構(gòu) D. 組合結(jié)構(gòu)
D
10. 判斷：在選秀活動(dòng)中，三個(gè)評委為每一位選手亮燈打分。如果三個(gè)評委都亮
綠燈，則選手可進(jìn)入下一輪比賽；如果兩個(gè)評委亮綠燈，則選手進(jìn)入待定席；如
果紅燈數(shù)超過兩盞，則選手被淘汰。這種情形最適合用循環(huán)結(jié)構(gòu)來描述算法（ ）
B
選擇結(jié)構(gòu)
練一練
11. 下列對算法描述中的三種基本控制結(jié)構(gòu)的敘述，不正確的是（ ）
A. 順序結(jié)構(gòu)表示程序按語句出現(xiàn)的先后順序從上到下順序執(zhí)行，每條語句可能執(zhí)行多次
選擇結(jié)構(gòu)表示程序根據(jù)判斷條件選擇其中的一條分支執(zhí)行，程序執(zhí)行過程
中有可能有的語句一次都不會被執(zhí)行
循環(huán)結(jié)構(gòu) 表示程序反復(fù)執(zhí)行某個(gè)或某些操作，循環(huán)結(jié)構(gòu)一定要終止循環(huán)的
條件
D. 在一個(gè)算法描述中，三種基本控制結(jié)構(gòu)可以混合使用
A
執(zhí)行一次
計(jì)算機(jī)程序與程序設(shè)計(jì)語言
03
1. 計(jì)算機(jī)程序的定義
計(jì)算機(jī)程序是指為了得到某種結(jié)果而可以由計(jì)算機(jī)等具有信息處理能力的裝置執(zhí)行的代碼化指令序列，或者可被自動(dòng)轉(zhuǎn)換成代碼化指令序列的符號化指令序列或者符號化語句序列。
簡而言之，計(jì)算機(jī)程序就是指計(jì)算機(jī)可以識別運(yùn)行的指令集合。
2. 計(jì)算機(jī)的基本組成
計(jì)算機(jī)的五大組成部分：運(yùn)算器、控制器、存儲器、輸入設(shè)備、
輸出設(shè)備。
運(yùn)算器
（內(nèi)）存儲器
控制器
輸入設(shè)備
輸出設(shè)備
數(shù)據(jù)流
控制流
程序
數(shù)據(jù)
請
求
信
號
響應(yīng)
信號
反
饋
信
號
操
作
指
令
響應(yīng)
信號
請
求
信
號
取
數(shù)
存
數(shù)
地
址
指
令
3. 計(jì)算表示和存儲指令或數(shù)據(jù)所采用的形式
什么？計(jì)算機(jī)只認(rèn)識 0 和 1 ？
計(jì)算內(nèi)部采用二進(jìn)制形式表示和存儲指令或數(shù)據(jù)。
計(jì)算機(jī)的工作過程實(shí)際上是周而復(fù)始地獲取指令、執(zhí)行指令的過程。
計(jì)算機(jī)程序設(shè)計(jì)語言的定義
計(jì)算機(jī)程序設(shè)計(jì)語言：是指一組用來定義計(jì)算機(jī)程序的語法規(guī)則，通常簡稱為“編程語言”。
計(jì)算機(jī)程序設(shè)計(jì)語言的發(fā)展經(jīng)歷了：
機(jī)器語言
匯編語言
高級語言
計(jì)算機(jī)程序設(shè)計(jì)語言的發(fā)展
10110000
00001001
00000100
00001000
11110100
機(jī)器語言
MOV AL，9
ADD AL，8
HLT
匯編語言
Print(9+8)
高級語言
例如：命令計(jì)算機(jī)完成“9+8”的加法運(yùn)算，對應(yīng)的計(jì)算機(jī)程序設(shè)計(jì)語言為：
計(jì)算機(jī)程序設(shè)計(jì)語言
任務(wù)2：自主閱讀教材P55-P57，總結(jié)3種程序設(shè)計(jì)語言的特點(diǎn)
語言類型 是否需要翻譯 (編譯) 優(yōu)勢 不足
1 機(jī)器語言
2 匯編語言
3 高級語言
3種計(jì)算機(jī)程序設(shè)計(jì)語言的特點(diǎn)
語言類型 是否需要翻譯 (編譯) 優(yōu)勢 不足
1 機(jī)器語言 否 能被計(jì)算機(jī)接受和執(zhí)行，運(yùn)算效率最高 程序難以理解，移植性差
2 匯編語言 是 針對計(jì)算機(jī)特定硬件而編制的匯編語言程序，比機(jī)器語言容易理解，效率仍十分高 不能被計(jì)算機(jī)直接運(yùn)行，移植性不好
3 高級語言 是 接近于數(shù)學(xué)語言或人的自然語言，易于理解，移植性好 不能被計(jì)算機(jī)直接運(yùn)行
課堂練習(xí)
12. 高級語言更接近自然語言，并不特指某種語言，也不依賴于特定的計(jì)算機(jī)系統(tǒng)，
因而更容易掌握和使用，通用性也更好。以下不屬于高級語言的是（ ）
A. Java語言 B. Python語言 C. 匯編語言 D. C語言
C
13. 計(jì)算機(jī)能直接識別、理解執(zhí)行的語言是（ ）
A. 匯編語言 B. Python語言 C. Basic語言 D. 機(jī)器語言
D
課堂練習(xí)
04
課堂練習(xí)
14. 下面關(guān)于算法的描述，正確是（ ）
A. 算法不可以用自然語言描述
B. 有些復(fù)雜算法用流程圖可能無法描述
C. 一個(gè)算法必須保證它的執(zhí)行步驟是有限的
D. 算法的流程圖表示法可以有零個(gè)或多個(gè)輸入，但只能有一個(gè)輸出
C
解析：算法可以用自然語言、流程圖描述；算法至少有一個(gè)或多個(gè)輸出。
課堂練習(xí)
15. P27第1題：算法的重要特征不包括（ ）
A. 有窮性 B. 確定性 C. 數(shù)據(jù)輸出 D. 唯一性
D
16. P27第4題：關(guān)于算法，下列敘述不正確的是（ ）
A. 解決任何一個(gè)具體問題可以有多種算法
B. 流程圖是算法的一種表示形式
C. 為了解決問題，設(shè)計(jì)算法時(shí)可以不用考慮時(shí)間成本和空間成本
D. 判斷一個(gè)算法的優(yōu)劣要看算法解決問題的執(zhí)行效率
C
課堂練習(xí)
17. P29第14題：以下流程圖描述的算法，其執(zhí)行結(jié)果是：（ ）
A. 7，18 B. 4，18
C. 7，2 D. 3，11
A
課堂練習(xí)
18. 設(shè)計(jì)程序計(jì)算矩形的面積和周長：輸入矩形的長和寬（單位：cm），輸出
矩形的面積和周長。其中定義整型變量a,b分別表示矩形的長和寬，變量s,c分
別表示矩形的面積和周長，請把流程圖中編號為①②的兩處補(bǔ)充完整。
①
a*b
②
(a+b)*2
開始
s=①
輸入變量a,b
c=②
輸出變量a,b
結(jié)束
課堂練習(xí)
19. P32第38題：利用輾轉(zhuǎn)相除法求最大公約數(shù)
①
r==0
開始
求m除以n的余數(shù)r
輸入m,n
m=n
輸出m
結(jié)束
n=r
否
是
①
②
②
r=m%n
例如：輸入m=16, n=12
當(dāng)?shù)谝淮窝h(huán)時(shí)：
r=m%n=16%12=4
m=n=12
n=r=4
r==0不成立，繼續(xù)循環(huán)
當(dāng)?shù)诙窝h(huán)時(shí)：
r=m%n=12%4=0
m=n=4
n=r=0
r==0成立，循環(huán)結(jié)束
最后輸出m的值就是最大公約數(shù)

展開更多......

收起↑