程序設(shè)計(jì)基礎(chǔ)課件第02章 算法與計(jì)算思維

v程序設(shè)計(jì)基礎(chǔ)——從問(wèn)題到程序（第3版）第2章算法與計(jì)算思維本章主要內(nèi)容計(jì)算思維程序的靈魂——算法算法是計(jì)算機(jī)科學(xué)的重要基石，同時(shí)也是計(jì)算機(jī)科學(xué)研究的一項(xiàng)永恒主題。在計(jì)算機(jī)無(wú)處不在的現(xiàn)代社會(huì)，對(duì)于非計(jì)算機(jī)專業(yè)的學(xué)生，學(xué)會(huì)讀懂算法，掌握計(jì)算思維，應(yīng)該是一項(xiàng)必備的基本技能，對(duì)于計(jì)算機(jī)相關(guān)專業(yè)的學(xué)生，學(xué)會(huì)讀懂并設(shè)計(jì)算法，掌握并運(yùn)用計(jì)算思維，應(yīng)該是一項(xiàng)最基本的要求。什么是算法？算法：對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。此外，構(gòu)成算法的求解步驟必須滿足以下條件：1.有窮性;2.確定性;3.可行性。算法（y=f(x)）有窮性：在合理時(shí)間內(nèi)結(jié)束；確定性：不存在二義性；可行性：計(jì)算機(jī)可實(shí)現(xiàn)；…輸入…輸出2.1程序的靈魂——算法算法不是問(wèn)題的答案，而是解決問(wèn)題的操作步驟，執(zhí)行這個(gè)操作步驟就能獲得問(wèn)題的答案。如何描述算法?描述算法：算法設(shè)計(jì)者在構(gòu)思和設(shè)計(jì)了一個(gè)算法之后，必須清楚準(zhǔn)確地將所設(shè)計(jì)的求解步驟記錄下來(lái)。使用算法：算法使用者知道如何調(diào)用算法。例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)的最大公約數(shù)mnr

歐幾里德算法2.1程序的靈魂——算法描述算法的方法——自然語(yǔ)言步驟1：將m除以n得到余數(shù)r；步驟2：若r等于0，則n為最大公約數(shù)，算法結(jié)束；否則執(zhí)行步驟3步驟3：將n的值放在m中，將r的值放在n中；步驟4：重新執(zhí)行步驟1；優(yōu)點(diǎn)：容易理解，缺點(diǎn)：冗長(zhǎng)、二義性使用方法：粗線條描述算法思想注意事項(xiàng)：避免寫(xiě)成自然段2.1程序的靈魂——算法圖形符號(hào)名稱含義起止框表示算法的開(kāi)始或結(jié)束處理框表示處理或運(yùn)算等功能輸入/輸出框表示進(jìn)行輸入/輸出操作判斷框根據(jù)條件是否滿足決定執(zhí)行兩條路徑中的某一條路徑控制流表示算法執(zhí)行的路徑，箭頭代表方向N開(kāi)始輸入m和n

r=m%nr=0m=n；n=r輸出n結(jié)束Y描述算法的方法——程序流程圖2.1程序的靈魂——算法偽代碼：介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間。處理和條件

結(jié)構(gòu)、語(yǔ)句和控制成分

描述算法的方法——偽代碼step1

r=m%n;step2

循環(huán)直到r=0step2.1

m=n;step2.2

n=r;step2.3

r=m%n;step3輸出n;

優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，

抽象性強(qiáng)，

容易理解，

被稱為算法語(yǔ)言

使用方法：7±22.1程序的靈魂——算法例2.1用偽代碼描述求解下列問(wèn)題的算法：（1）兩個(gè)瓶子A和B分別盛放醬油和醋，要求將A瓶和B瓶的液體互換，即A瓶盛放醋B瓶盛放醬油。step1:將A瓶的醬油倒入C瓶，即C

A；

step2:將B瓶的醋倒入A瓶，即A

B；step3:將C瓶暫存的醬油倒入B瓶，即B

C；偽代碼（2）將三個(gè)數(shù)由小到大排序。step1:如果x＞y，則將x和y交換；

step2:如果z＜x，則temp

z；z

y；y

x；x

temp；否則，如果z＜y，則將y和z交換；step3:依次輸出x,y,z；偽代碼2.1程序的靈魂——算法（3）在一個(gè)含有n個(gè)元素的集合中查找最大值元素。step1:max

第1個(gè)元素；step2:初始化被比較元素的序號(hào)i

2；

step3:當(dāng)i小于等于n時(shí)重復(fù)執(zhí)行下述操作：step3.1:如果第i個(gè)元素大于max，則max

第i個(gè)元素；step3.2:i

i+1；

step4:輸出max；偽代碼例2.1用偽代碼描述求解下列問(wèn)題的算法：2.1程序的靈魂——算法如何評(píng)價(jià)算法？時(shí)間和空間效率：一個(gè)好算法應(yīng)該具有較短的執(zhí)行時(shí)間并占用較少的輔助存儲(chǔ)空間。算法的復(fù)雜性：對(duì)算法所需時(shí)空資源的一種度量，所需資源越多，算法的復(fù)雜性就越高；反之，算法的復(fù)雜性就越低。對(duì)于給定的實(shí)際問(wèn)題，設(shè)計(jì)出復(fù)雜性盡可能低的算法是算法設(shè)計(jì)者需要考慮的一個(gè)重要目標(biāo)。當(dāng)給定的問(wèn)題有多種算法時(shí)，選擇復(fù)雜性最低的算法，是選擇算法時(shí)應(yīng)遵循的一個(gè)重要準(zhǔn)則。2.1程序的靈魂——算法如何評(píng)價(jià)算法？

定義2-1若存在兩個(gè)正的常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))（或稱算法在O(f(n))中）。2.1程序的靈魂——算法算法的重要性例2.3用短除法和歐幾里得算法求兩個(gè)自然數(shù)的最大公約數(shù)，請(qǐng)通過(guò)一個(gè)具體實(shí)例比較兩個(gè)算法的效率。2.1程序的靈魂——算法對(duì)于兩個(gè)自然數(shù)48和36，短除法須進(jìn)行12次求余操作（對(duì)于12和9，試除2和3得到公因子3；對(duì)于4和3，試除2和3后結(jié)束），而歐幾里得算法只進(jìn)行2次求余操作，程序設(shè)計(jì)的一般過(guò)程2.2計(jì)算思維問(wèn)題算法程序想法抽象模型基本思路數(shù)據(jù)表示數(shù)據(jù)處理程序語(yǔ)言編程環(huán)境人（設(shè)計(jì)方案）計(jì)算機(jī)(執(zhí)行方案)程序設(shè)計(jì)實(shí)例——雞兔同籠問(wèn)題【問(wèn)題】籠子里共有M

只頭N

只腳，問(wèn)雞和兔子各有多少只？【算法】設(shè)變量chicken表示雞的個(gè)數(shù)，rabbit表示兔子的個(gè)數(shù)，算法如下：step1:chicken從0~M重復(fù)執(zhí)行下述操作：step1.1:rabbit=M–chicken;step1.2:如果(2*chicken+4*rabbit等于N)，則跳出循環(huán);step1.3:chicken++;step2:如果是提前跳出循環(huán)，則輸出chicken和rabbit的值;

否則輸出“無(wú)解”;偽代碼x+y=M2x+4y=N且滿足0≤x,y≤M【想法】設(shè)雞有x

只兔子有y

只，則有如下方程組成立：#include<stdio.h>/*使用庫(kù)函數(shù)printf和scanf*//*空行，下面是主函數(shù)*/intmain(){intM,N;/*M存儲(chǔ)頭的個(gè)數(shù)，N存儲(chǔ)腳的個(gè)數(shù)*/intchicken,rabbit;/*chicken存儲(chǔ)雞的個(gè)數(shù)，rabbit存儲(chǔ)兔子的個(gè)數(shù)*/printf(“請(qǐng)輸入頭的個(gè)數(shù)和腳的個(gè)數(shù):”);/*輸出提示信息*/scanf("%d%d",&M,&N);/*從鍵盤(pán)接收兩個(gè)整數(shù)*/for(chicken=0;chicken<=M;chicken++)/*依次進(jìn)行試探*/{rabbit=M–chicken;if(2*chicken+4*rabbit==N)break;

/*方程組已解，跳出循環(huán)*/}if(chicken<=M)/*如果是提前跳出循環(huán)*/printf("雞有%d只，兔子有%d只\n",chicken,rabbit);else

printf("輸入數(shù)據(jù)不合理，無(wú)解\n");return0;/*將0返回操作系統(tǒng)，表明程序正常結(jié)束*/}【程序】以chicken作為循環(huán)變量，依次試探變量chicken和rabbit的取值是否滿足方程組，程序如下：程序設(shè)計(jì)實(shí)例——雞兔同籠問(wèn)題程序設(shè)計(jì)與計(jì)算思維2.2計(jì)算思維計(jì)算思維：基于計(jì)算機(jī)科學(xué)的概念體系進(jìn)行問(wèn)題求解、系統(tǒng)設(shè)計(jì)，以及理解人類行為等涵蓋計(jì)算機(jī)科學(xué)之廣度的一系列思維活動(dòng)。程序的基本框架2.2計(jì)算思維IPO框架：程序一般由三部分組成：輸入（Input）、處理（Process）和輸出（Output）。所謂輸入/輸出是以計(jì)算機(jī)主機(jī)為主體而言的，從計(jì)算機(jī)向外部輸出設(shè)備（如顯示器、打印機(jī)、磁盤(pán)等）輸出數(shù)據(jù)稱為輸出，從外部輸入設(shè)備（如鍵盤(pán)、鼠標(biāo)、掃描儀、磁盤(pán)等）向計(jì)算機(jī)輸入數(shù)據(jù)稱為輸入。程序的基本框架2.2計(jì)算思維輸入部分處理部分輸出部分#include<stdio.h>

intmain(