算法與程序設(shè)計(jì)41張課件

算法與程序設(shè)計(jì)算法與程序設(shè)計(jì)個(gè)人計(jì)算機(jī)的另一個(gè)稱呼是什么？電腦為什么稱計(jì)算機(jī)是電腦？計(jì)算機(jī)能模擬人的大腦的活動(dòng)。個(gè)人計(jì)算機(jī)的另一個(gè)稱呼是什么？為什么稱計(jì)算機(jī)是電腦？2算法初步算法與程序框圖基本算法算法案例揭開計(jì)算機(jī)解決問題的神秘面紗程序設(shè)計(jì)基礎(chǔ)可視化編程算法與程序?qū)崿F(xiàn)面向?qū)ο蟪绦蛟O(shè)計(jì)程序設(shè)計(jì)實(shí)踐算法與程序設(shè)計(jì)算法初步算法與程序框圖揭開計(jì)算機(jī)解決問題的神秘面紗算法與程序3如何用計(jì)算機(jī)解決問題當(dāng)我們用計(jì)算機(jī)解決問題時(shí)，首先要分析問題，然后根據(jù)問題的要求選擇合適的軟件。如果現(xiàn)有的軟件能滿足我們的要求，我們會(huì)直接用這些軟件來完成任務(wù)。例如：學(xué)校財(cái)務(wù)處要制作一份工資表，工資表中許多數(shù)據(jù)，我們可以用Excel解決；學(xué)生要設(shè)計(jì)一個(gè)報(bào)刊設(shè)計(jì)，可以使用word；網(wǎng)絡(luò)上的網(wǎng)頁是使用網(wǎng)頁制作工具完成的，記事本要輸入代碼，F(xiàn)rontpage和Dreamweaver可以直接使用可視化工具。除此之外，現(xiàn)實(shí)生活中還有許多工作往往比較特殊，現(xiàn)有的軟件不能很好地完成，或者由于其他方面的原因無法使用，這就需要我們編寫程序來解決問題。如何用計(jì)算機(jī)解決問題當(dāng)我們用計(jì)算機(jī)解決問題時(shí)，首先要分析問題4計(jì)算機(jī)解決問題的步驟分析問題——可采用建立數(shù)學(xué)模型的方式使問題變得更明確、易理解。設(shè)計(jì)算法——數(shù)學(xué)模型確定了應(yīng)該“做什么”，接下來就要為它尋找一個(gè)“如何做”的算法。編寫程序——用一種計(jì)算機(jī)能接受的程序設(shè)計(jì)語言來描述問題求解的算法。調(diào)試程序——查找和改正程序中存在的錯(cuò)誤，使程序能順利地執(zhí)行，得出正確結(jié)果。計(jì)算機(jī)解決問題的步驟分析問題——可采用建立數(shù)學(xué)模型的方式使問5算法的概念算法的概念6加法口訣表

直加滿五加進(jìn)十加破五進(jìn)十加一一上一一下五去四一去九進(jìn)一

二二上二二下五去三二去八進(jìn)一

三三上三三下五去二三去七進(jìn)一

四四上四四下五去一四去六進(jìn)一

五五上五

五去五進(jìn)一

六六上六

六去四進(jìn)一六上一去五進(jìn)一七七上七

七去三進(jìn)一七上二去五進(jìn)一八八上八

八去二進(jìn)一八上三去五進(jìn)一九九上九

九去一進(jìn)一九上四去五進(jìn)一加法口訣表

直加滿五加進(jìn)十加破五進(jìn)十加一一上一一下五去四一7農(nóng)夫過河問題一個(gè)農(nóng)夫帶著一只狼，一只羊和一棵白菜過河。河邊只有一條船,由于船小,農(nóng)夫一次只能帶其中的一樣過河。如無人看管,狼要吃羊,羊要吃菜。問農(nóng)夫如何安排過河,才能使狼、羊、菜都安然無恙。農(nóng)夫過河問題8渡河的方法與步驟：第一步：農(nóng)夫帶著羊渡過河去；第二步：農(nóng)夫劃船回來；第三步：農(nóng)夫帶著菜渡過河去；第四步：農(nóng)夫帶著羊劃船回來；第五步：農(nóng)夫帶著狼渡過河去；第六步：農(nóng)夫劃船回來；第七步：農(nóng)夫帶著羊渡過河。渡河的方法與步驟：第一步：農(nóng)夫帶著羊渡過河去；9一個(gè)籠子里有雞和兔，現(xiàn)在只知道里面一共有35個(gè)頭，94只腳，問雞和兔各有多少只？

X+Y=a2X+4Y=b解方程組得：X＝2a-b/2，Y＝b/2-a雞兔同籠問題一個(gè)籠子里有雞和兔，現(xiàn)在只知道里面一共有35個(gè)頭，94只腳，10設(shè)計(jì)算法輸入a和b的值求X=2a-b/2求Y=b/2-a輸出X，Y的值結(jié)束設(shè)計(jì)算法輸入a和b的值11a1X+b1Y=c1a2X+b2Y=c2輸入a1,b1,c1,a2,b2,c2的值求X=(b2*c1-b1*c2)/(a1*b2-a2*b1)求Y=(a1*c2-a2*c1)/(a1*b2-a2*b1)輸出X，Y的值結(jié)束a1X+b1Y=c112算法算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。算法是解決問題的方法和步驟

算法算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則13算法的特征輸入確定有窮性輸出能行性算法的特征輸入14判斷整數(shù)n（n>2）是否為質(zhì)數(shù)第一步：給定大于2的整數(shù)第二步：令i＝２第三步：用i除n，得到余數(shù)r．判斷余數(shù)r是否為０，若是，則n不是質(zhì)數(shù)，結(jié)束算法；否則，將i的值增加1，仍用i表示第四步：判斷i是否大于（n-1），若是，則n是質(zhì)數(shù)，返回第三步判斷整數(shù)n（n>2）是否為質(zhì)數(shù)第一步：給定大于2的整數(shù)15著名數(shù)學(xué)家華羅庚“燒水泡茶”算法一第一步：燒水；第二步：水燒開后，洗刷茶具；第三步：沏茶。算法二第一步：燒水；第二步：燒水過程中，洗刷茶具；第三步：水燒開后沏茶。著名數(shù)學(xué)家華羅庚“燒水泡茶”16求最大公約數(shù)輾轉(zhuǎn)相除法窮舉法算法在解決問題中的地位和作用見書Ｐ13表1-6求最大公約數(shù)算法在解決問題中的地位和作用見書Ｐ13表1-617兩個(gè)程序的效率比較指標(biāo)用輾轉(zhuǎn)相除法設(shè)計(jì)的程序用窮舉法設(shè)計(jì)和程序運(yùn)行結(jié)果最大公約數(shù)最大公約數(shù)運(yùn)行時(shí)間較短較長通用性較好較差兩個(gè)程序的效率比較指標(biāo)用輾轉(zhuǎn)相除法設(shè)計(jì)的程序用窮舉法設(shè)計(jì)和程18計(jì)算機(jī)只懂得根據(jù)人的命令來執(zhí)行相關(guān)的程序，而我們要編寫程序，首先要分析問題：

對問題進(jìn)行詳細(xì)地分析，通過分析，弄清楚已知條件下的初始狀態(tài)及要達(dá)到的目標(biāo)，找出求解問題的方法和過程，并抽取出一個(gè)數(shù)學(xué)模型，形成算法;然后要設(shè)計(jì)算法：

將這個(gè)數(shù)學(xué)模型連同它要處理的數(shù)據(jù)用計(jì)算機(jī)能識(shí)別的方式描述出來，使之成為計(jì)算機(jī)能處理的對象；最后，編寫程序：

用程序設(shè)計(jì)語言設(shè)計(jì)出具體的問題求解過程，形成計(jì)算機(jī)程序，這樣，計(jì)算機(jī)就會(huì)按照我們給定的指令一條一條地

進(jìn)行處理了。計(jì)算機(jī)只懂得根據(jù)人的命令來執(zhí)行相關(guān)的程序，而我們要編寫程19設(shè)計(jì)一個(gè)軟件的步驟是：開始分析問題設(shè)計(jì)算法編寫程序運(yùn)行程序驗(yàn)證結(jié)果問題解決無論使用現(xiàn)成的軟件解決問題，還是自己動(dòng)手編程解決問題，其實(shí)質(zhì)都是一樣的：現(xiàn)有的計(jì)算機(jī)軟件同樣也經(jīng)歷了這些過程，其差別在于，用程序設(shè)計(jì)解決問題需要我們親自動(dòng)手設(shè)計(jì)軟件，而使用現(xiàn)成的軟件，是別人已經(jīng)給我們設(shè)計(jì)好了的。設(shè)計(jì)一個(gè)軟件的步驟是：開始分析問題設(shè)計(jì)算法編寫程序運(yùn)行程序問20算法的描述自然語言流程圖偽代碼算法的描述自然語言211、用自然語言來描述。什么是自然語言。人們?nèi)粘Ｉ钪惺褂玫恼Z言

1、用自然語言來描述。什么是自然語言。人們?nèi)粘Ｉ钪惺褂玫恼Z22算法描述：以“韓信點(diǎn)兵問題”為例：算法描述：以“韓信點(diǎn)兵問題”23算法分析：以“韓信點(diǎn)兵問題”為例：算法分析：以“韓信點(diǎn)兵問題”24自然語言的優(yōu)點(diǎn)：通俗易懂。缺點(diǎn)：容易產(chǎn)生歧義。自然語言的優(yōu)點(diǎn)：通俗易懂。25例如：“這個(gè)人連老張也不認(rèn)識(shí)”。

意思之一：這個(gè)人不認(rèn)識(shí)老張。意思之二：老張不認(rèn)識(shí)這個(gè)人。

例如：“這個(gè)人連老張也不認(rèn)識(shí)”。意思之一：這個(gè)人不認(rèn)識(shí)老張262、用流程圖來描述流程圖也稱程序框圖，算法的一種圖形化表示方法。2、用流程圖來描述流程圖也稱程序框圖，算法的一種圖形化表示方27流程圖

圖形名稱功能開始／結(jié)束表示算法的開始或結(jié)束輸入／輸出表示算法中變量的輸入或輸出處理表示算法中變量的計(jì)算與賦值判斷表示算法中的條件判斷流程線表示算法中的流向連接點(diǎn)表示算法中的轉(zhuǎn)接流程圖

圖形名稱功能開始／結(jié)束表示算法的開始或結(jié)束輸入／輸出28算法與程序設(shè)計(jì)41張課件29流程圖的優(yōu)缺點(diǎn)與自然語言相比，用流程圖描述算法形象、直觀，更容易理解。流程圖的優(yōu)缺點(diǎn)與自然語言相比，用流程圖描述算法形象、直觀，更303、用偽代碼描述算法。

例如，給定一個(gè)四位數(shù)的年份，判斷它是否為閏年。如果用偽代碼來描述算法，可以表示如下：

算法分析：

我們知道，如果2月是28天，則這一年是平年；如果是29天，則這一年是閏年。判斷閏年的條件是：如果該年份能被4整除但不能被100整除，或者能被400整除，則該年為閏年。3、用偽代碼描述算法。例如，給定一個(gè)四位數(shù)的年31算法描述：輸入年份→yIFy能被4整除THEN

IFy不能被100整除THEN輸出“是閏年”

ELSE

IFy能被400整除THEN輸出“是閏年”

ELSE輸出“不是閏年”

ENDIF

ENDIFELSE輸出“不是閏年”ENDIF算法描述：輸入年份→y32使用偽代碼描述算法沒有嚴(yán)格的語法限制，書寫格式也比較自由，只要把意思表達(dá)清楚就可以了，它更側(cè)重于對算法本身的描述。在偽代碼描述中，表示關(guān)鍵詞的語句一般用英文單詞，其他語句可以用英文語句，也可以用漢語語句。使用偽代碼描述算法沒有嚴(yán)格的語法限制，書寫格式也比較自由，只33偽代碼的優(yōu)缺點(diǎn)：用偽代碼描述的算法簡潔、易懂，修改起來也比較容易，并且很容易轉(zhuǎn)化為程序語言代碼。缺點(diǎn)是不是很直觀。

偽代碼的優(yōu)缺點(diǎn)：用偽代碼描述的算法簡潔、易懂，修改起來也比較34開始r=m除以n的余數(shù)輸入正整數(shù)m和nr=0輸出n的值結(jié)束m=n，n=r否是INPUTm，nr=mmodnDOWHILEr≠0m=nn=rr=mmodnLoopPRINTn開始r=m除以n的余數(shù)輸入正整數(shù)m和nr=0輸出n的值結(jié)束m35程序的基本結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)程序的基本結(jié)構(gòu)順序結(jié)構(gòu)36分析問題、建立模型、設(shè)計(jì)算法、編寫程序具體問題程序設(shè)計(jì)計(jì)算機(jī)程序具體問題程序設(shè)計(jì)計(jì)算機(jī)程序37程序設(shè)計(jì)語言機(jī)器語言匯編語言高級語言程序的編輯與翻譯程序設(shè)計(jì)語言機(jī)器語言程序的編輯與翻譯38MOVAL，