資源描述：
《用偽代碼描述算法.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫(kù)。
1、第一章 如何用計(jì)算機(jī)解決問題第二節(jié)算法描述與設(shè)計(jì)一、算法是“靈魂”1.算法存在于人們生活中，如：上街購(gòu)物、顧客付款、營(yíng)業(yè)員找銀等。2.“韓信點(diǎn)兵問題”有不同的求解過程，就有不同的算法。3.算法——解決問題的方法和步驟。算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說，就是計(jì)算機(jī)解題的過程。在這個(gè)過程中，無論是形成解題思路還是編寫程序，都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。4.算法的發(fā)現(xiàn)世界上最早的算法(P5)算法是尼克勞斯.沃斯（N.Writh）提出的，他指出：算法+數(shù)據(jù)結(jié)構(gòu)=程序。（即算法不能單獨(dú)構(gòu)成程序，它
2、必須和數(shù)據(jù)結(jié)構(gòu)合二為一）算法獨(dú)立于任何具體的程序設(shè)計(jì)語言，一個(gè)算法可以用多種程序設(shè)計(jì)語言來實(shí)現(xiàn)。5-算法的特征算法要有一個(gè)清晰的起始步，表示處理問題的起點(diǎn)，且每一個(gè)步驟只能有一個(gè)確定的后繼步驟(1算法的確定性)，從而組成一個(gè)步驟的有限序列(2算法的有窮性)；要有一個(gè)終止步(序列的終止)表示問題得到解決或不能得到解決；每條規(guī)則必須是確定的、可行的(3算法的可行性)、不能存在二義性。算法總是對(duì)數(shù)據(jù)進(jìn)行加工處理，因此，算法的執(zhí)行過程中通常要有數(shù)據(jù)4輸入(0個(gè)或多個(gè))和數(shù)據(jù)5輸出（至少一個(gè)）的步驟。(書P6)例：計(jì)算1+2+3+……+100=？分析：計(jì)算這道題目
3、的算法有限制范圍，可以在有限時(shí)間內(nèi)完成，這是算法的第一個(gè)特征：有窮性。計(jì)算時(shí)可以用紙筆、算盤、運(yùn)算器和計(jì)算機(jī)來完成，且計(jì)算過程是多樣的，但結(jié)果是唯一的。這就是算法的可行性、確定性。計(jì)算方法：⑴把這100個(gè)數(shù)按順序相加。⑵用湊數(shù)法：1+99=100，2+98=100，3+97=100，……，49+51，最后只剩下50和100。⑶計(jì)算機(jī)計(jì)算法：令S=0，使1≤n≤100，先執(zhí)行S=S+n⑴，再執(zhí)行n=n+1⑵n=1，S=0時(shí)，S=1n=2，S=1時(shí)，S=3 n=3，S=3時(shí)，S=6n=4，S=6時(shí)，S=10 n=5，S=10時(shí)，S=15n=6，S=15時(shí)，S
4、=21……算法的另外一個(gè)特征：輸入、輸出。隨時(shí)可以將程序改變：N個(gè)連續(xù)數(shù)相加，N個(gè)奇數(shù)或偶數(shù)相加等……第一章如何用計(jì)算機(jī)解決問題第二節(jié)算法描述與設(shè)計(jì)為了能更好地理解什么是算法，我們利用日常生活中的“打電話”的例子來討論?！按螂娫挕钡倪^程。拿起聽筒撥號(hào)打不通通了把聽筒放下通話結(jié)束把聽筒放下等會(huì)兒再撥無人接聽把聽筒放下等會(huì)兒再撥第一章如何用計(jì)算機(jī)解決問題算法的概念：解決問題的方法和步驟就是算法。算法可以用多種方法來描述1、用自然語言來描述。2、用流程圖來描述。3、用偽代碼描述算法。1、用自然語言來描述。（書P6-7）什么是自然語言。即用人們?nèi)粘Ｊ褂玫恼Z言和數(shù)
5、學(xué)語言描述的算法算法描述：以“韓信點(diǎn)兵問題”為例：算法分析：以“韓信點(diǎn)兵問題”為例：1、將N的初始值賦為12、如果N被3、5、7整除后余數(shù)為2、3、2，則輸出N的值，轉(zhuǎn)入第4步3、將N的值加1，轉(zhuǎn)到第2步4、結(jié)束程序書P7實(shí)踐：若N=2，則密文與原文的對(duì)應(yīng)關(guān)系是……讀入字符串的方法……自然語言的優(yōu)點(diǎn)：通俗易懂。缺點(diǎn)：容易產(chǎn)生歧義。例如：“這個(gè)人連老張也不認(rèn)識(shí)”。意思之一：這個(gè)人不認(rèn)識(shí)老張。意思之二：老張不認(rèn)識(shí)這個(gè)人。2、用流程圖來描述。什么是流程圖？（也稱程序框圖）它是算法的一種圖形化表示方法。認(rèn)識(shí)流程圖符號(hào)流程圖的特點(diǎn):與自然語言相比，用流程圖描述算法
6、形象、直觀，更容易理解。1）用偽代碼描述“韓信點(diǎn)兵問題”的算法ForI=1toNifn能被3、5、7整除余數(shù)為2、3、2then輸出nendifNextI3、用偽代碼描述算法。2)例如，判斷一個(gè)四位數(shù)的年份是否為閏年。算法分析：我們知道，如果2月是28天，則這一年是平年；如果是29天，則這一年是閏年。判斷閏年的條件是：如果該年份能被4整除但不能被100整除，或者能被400整除，則該年為閏年。算法描述（偽代碼）：輸入年份→yIFy能被4整除THENIFy不能被100整除THEN輸出“是閏年”ELSEIFy能被400整除THEN輸出“是閏年”ELSE輸出“不
7、是閏年”ENDIFENDIFELSE輸出“不是閏年”ENDIF使用偽代碼描述算法沒有嚴(yán)格的語法限制，書寫格式也比較自由，只要把意思表達(dá)清楚就可以了，它更側(cè)重于對(duì)算法本身的描述。在偽代碼描述中，表示關(guān)鍵詞的語句一般用英文單詞，其他語句可以用英文語句，也可以用漢語語句。偽代碼的優(yōu)缺點(diǎn)（書P9）：用偽代碼描述的算法簡(jiǎn)潔、易懂，修改起來也比較容易，并且很容易轉(zhuǎn)化為程序語言代碼。缺點(diǎn)是不夠直觀。練習(xí)：說出下面流程圖的各框名稱開始框輸入框處理框判斷框處理框處理框處理框輸出框結(jié)束框如果兩個(gè)數(shù)有最大公約數(shù)A，那么這兩個(gè)數(shù)，以及這兩個(gè)數(shù)的差，還有大數(shù)除以小數(shù)的余數(shù)，必然都
8、是A的倍數(shù)。 所以當(dāng)最后兩個(gè)數(shù)剛好能整除時(shí)，較小的數(shù)就是最大公約數(shù)。1）什么是算
