計(jì)算機(jī)基礎(chǔ)案例解析指導(dǎo)教程_案例8 計(jì)算機(jī)問題求解算法

1、解析指導(dǎo)教程,計(jì)算機(jī)基礎(chǔ)案例,案例8 計(jì)算機(jī)問題求解算法,2,,案例實(shí)踐8 計(jì)算機(jī)問題求解算法,概述算法的發(fā)現(xiàn)問題求解的藝術(shù)算法的概念算法的表示算法的有效性和正確性程序設(shè)計(jì)案例分析與求解,3,計(jì)算機(jī)問題求解算法——概述,我們生存在一個(gè)信息爆炸的計(jì)算機(jī)時(shí)代，在工作、生活甚至娛樂中，我們會(huì)遇到很多與信息處理相關(guān)的問題，并需要解決各種各樣的問題。當(dāng)我們必須求解一個(gè)特定的問題時(shí)，首先會(huì)問：這個(gè)問題確定是可解的嗎？解決這個(gè)

2、問題有多么困難？怎樣才是最佳的解決方法？ 這時(shí)就不僅僅是考慮傳統(tǒng)的手工處理方式，而應(yīng)該將計(jì)算機(jī)的因素考慮其中，因?yàn)槲覀円柚?jì)算機(jī)來幫助我們解決問題。 于是，我們又會(huì)好奇地問：計(jì)算機(jī)是怎樣求解問題的？ 下面就讓我們在不同類型的案例求解過程中，了解和學(xué)習(xí)計(jì)算機(jī)求解問題的思想和方法。,4,計(jì)算機(jī)問題求解算法——概述,針對具體的問題求解要求，我們需要考慮的問題很多，諸如：常規(guī)我們怎么處理這個(gè)問題

3、？利用計(jì)算機(jī)來實(shí)現(xiàn)是可行的嗎？需要做哪些規(guī)律性的歸納和一致性的整合？如何發(fā)現(xiàn)算法并直觀地表示算法？實(shí)現(xiàn)的效率是我們可以接受的嗎？怎樣在人與計(jì)算機(jī)之間找到一個(gè)最佳的契合點(diǎn)？計(jì)算機(jī)提供的軟件工具平臺如何使用？語法規(guī)則與數(shù)據(jù)描述有哪些？如何將算法轉(zhuǎn)換為可實(shí)現(xiàn)的高級語言程序代碼？,5,計(jì)算機(jī)問題求解算法——概述,要想有效地利用計(jì)算機(jī)來實(shí)現(xiàn)問題的求解和處理，就必須具備計(jì)算思維能力和程序設(shè)計(jì)開發(fā)技能。 問題的分析、歸納

4、、建模和整理算法（粗框架）的過程屬于計(jì)算思維范疇；而具體的實(shí)現(xiàn)算法（細(xì)化）、數(shù)據(jù)描述、控制結(jié)構(gòu)、特定計(jì)算機(jī)高級語言軟件環(huán)境的工具運(yùn)用、編碼、調(diào)試和實(shí)現(xiàn)的過程就屬于程序設(shè)計(jì)范疇。,6,,案例實(shí)踐8 計(jì)算機(jī)問題求解算法,概述算法的發(fā)現(xiàn)問題求解的藝術(shù)算法的概念算法的表示算法的有效性和正確性程序設(shè)計(jì)案例分析與求解,7,計(jì)算機(jī)問題求解算法——算法的發(fā)現(xiàn),問題求解的技術(shù)與學(xué)習(xí)不僅僅是在計(jì)算機(jī)科學(xué)領(lǐng)域，而是在任何領(lǐng)域，都是要求永久需

5、要和具備的技能。算法發(fā)現(xiàn)的過程和一般問題的求解過程之間存在著緊密的聯(lián)系，因此在計(jì)算機(jī)科學(xué)領(lǐng)域人們把問題的求解簡化為一種算法，但并不是所有的問題都一定都能找到解決問題的算法。,8,計(jì)算機(jī)問題求解算法——算法的發(fā)現(xiàn),程序開發(fā)由兩個(gè)活動(dòng)組成：發(fā)現(xiàn)潛在的算法和以程序的方法表示算法。要理解算法是如何發(fā)現(xiàn)的就是要理解問題的求解過程。算法的發(fā)現(xiàn)起源于公元前3000年~公元前1500年的巴比倫，當(dāng)時(shí)巴比倫人求解“算法”的過程：先用解代數(shù)方法，再計(jì)算

6、實(shí)際數(shù)目，最后寫上一句短句“這就是一個(gè)過程”。,9,,案例實(shí)踐10 計(jì)算機(jī)問題求解算法,概述算法的發(fā)現(xiàn)問題求解的藝術(shù)算法的概念算法的表示算法的有效性和正確性程序設(shè)計(jì)案例分析與求解,10,計(jì)算機(jī)問題求解算法——問題求解的藝術(shù),問題求解的藝術(shù)包括四個(gè)階段：第一階段：理解問題；第二階段：尋找一個(gè)可能解決問題的算法過程的思路；第三階段：闡明算法并且用程序?qū)⑵浔磉_(dá)出來；第四階段：從準(zhǔn)確度及其是否有潛力作為一個(gè)解決其他問題的

7、工具這兩方面來評估這個(gè)程序。但這些階段不是一定要遵循的步驟，也不必一定按順序完成。算法發(fā)現(xiàn)是一種富有挑戰(zhàn)性的藝術(shù)，必須花費(fèi)時(shí)間去學(xué)習(xí)。,11,,案例實(shí)踐10 計(jì)算機(jī)問題求解算法,概述算法的發(fā)現(xiàn)問題求解的藝術(shù)算法的概念算法的表示算法的有效性和正確性程序設(shè)計(jì)案例分析與求解,12,計(jì)算機(jī)問題求解算法——概念,算法的概念算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的方法步驟或清晰指令的陳述。算

8、法存在于人們的生活中，如：上街購物、顧客付款、營業(yè)員找銀等等。算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。如果一個(gè)算法有缺陷，或不適合于某個(gè)問題，執(zhí)行這個(gè)算法將不會(huì)解決這個(gè)問題。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度（是指算法需要消耗的內(nèi)存空間）與時(shí)間復(fù)雜度（是指執(zhí)行算法所需要的時(shí)間）來衡量。不同的算法可能用不同的時(shí)間、空間或效率來完成同樣的任務(wù)。,13,計(jì)算機(jī)問題求解算法—

9、—概念,算法要素一個(gè)算法是由操作與控制結(jié)構(gòu)兩個(gè)要素組成。操作：計(jì)算機(jī)最基本的操作有：算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算和數(shù)據(jù)傳送等?？刂平Y(jié)構(gòu)：各操作之間的執(zhí)行順序?yàn)樗惴ǖ目刂平Y(jié)構(gòu)，有：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。,14,計(jì)算機(jī)問題求解算法——概念,算法性質(zhì)一般歸納為下列五點(diǎn)：輸入：要求若干個(gè)信息的輸入；有窮性：任意一個(gè)算法在執(zhí)行有限個(gè)計(jì)算步驟后必須終止；可行性：有限個(gè)步驟應(yīng)該可以在一個(gè)合理的范圍內(nèi)進(jìn)行；確定性：每一個(gè)計(jì)算步驟

10、，必須是精確地定義、無二義性；輸出：有若干個(gè)輸出信息即處理結(jié)果。,15,,案例實(shí)踐10 計(jì)算機(jī)問題求解算法,概述算法的發(fā)現(xiàn)問題求解的藝術(shù)算法的概念算法的表示算法的有效性和正確性程序設(shè)計(jì)案例分析與求解,16,計(jì)算機(jī)問題求解算法 ——算法描述,算法描述可以使用多種方法描述算法：自然語言、流程圖、偽代碼和計(jì)算機(jī)語言。例如：分析一天中，根據(jù)時(shí)間歸納出一個(gè)人的日程安排情況。下面用了四種方法描述算法。,17,計(jì)算機(jī)問題求解算法

11、——算法描述,自然語言用自然語言表達(dá)算法，就是把算法的各個(gè)步驟，依次用人們所熟悉的自然語言表示出來。自然語言描述算法的特點(diǎn)是通俗易懂，但缺乏直觀性和簡潔性，且易產(chǎn)生歧義。使用此種方式描述算法，需要注意的事項(xiàng)是：描述要求盡可能精確和詳盡。,18,計(jì)算機(jī)問題求解算法——算法描述,流程圖流程圖是用一些圖框、線條以及文字說明來形象地、直觀地描述算法。,,19,計(jì)算機(jī)問題求解算法——算法描述,偽代碼偽代碼（Pseudocode）是一

12、種在算法開發(fā)過程中非正式地表達(dá)思想的符號系統(tǒng)，也是一種算法描述語言，它是通過使用一些介于自然語言與高級語言之間的符號語言表達(dá)算法。使用偽代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言（Visual Basic、C或Java）實(shí)現(xiàn)。用偽代碼描述算法的特點(diǎn)是它介于自然語言與編程語言之間，結(jié)構(gòu)清晰、代碼簡單、不拘于具體實(shí)現(xiàn)，可讀性好。,20,計(jì)算機(jī)問題求解算法——算法描述,21,計(jì)算機(jī)問題求解算法——算法描述,22,計(jì)算機(jī)

13、問題求解算法 ——算法描述,計(jì)算機(jī)語言計(jì)算機(jī)無法識別和執(zhí)行自然語言、流程圖和偽代碼描述的算法，這些方法只是為了幫助人們描述和梳理算法。要用計(jì)算機(jī)解決問題，最終必須用計(jì)算機(jī)程序設(shè)計(jì)語言來描述算法。這里涉及到大量的代碼語言元素、語法規(guī)則和語言環(huán)境工具。,23,計(jì)算機(jī)問題求解算法 ——算法描述,24,,案例實(shí)踐10 計(jì)算機(jī)問題求解算法,概述算法的發(fā)現(xiàn)問題求解的藝術(shù)算法的概念算法的表示算法的有效性和正確性程序設(shè)計(jì)案例分析與求

14、解,25,計(jì)算機(jī)問題求解算法——算法的有效性和正確性,算法無處不在！在我們的生活中處處可見，很多日常問題的處理也都會(huì)用到了算法。解決方案的優(yōu)劣，即評價(jià)算法的標(biāo)準(zhǔn)，基本包括：算法的正確性算法的運(yùn)行效率（時(shí)間、空間和資源）算法的可讀性,26,計(jì)算機(jī)問題求解算法——算法的有效性和正確性,算法的有效性是算法設(shè)計(jì)中所關(guān)注的一個(gè)主要問題。在效率高低不同的兩種算法中選擇會(huì)產(chǎn)生對于解決問題的實(shí)用方法和不實(shí)用方法兩種解。分析算法可以預(yù)測這一

15、算法適合在什么樣的環(huán)境中有效地運(yùn)行，對解決同一問題的不同算法的有效性作出比較。算法分析通常包括最優(yōu)情況分析，最差情況分析和平均情況分析。,27,計(jì)算機(jī)問題求解算法——算法的有效性和正確性,例如我們要在學(xué)生信息表中查找某個(gè)學(xué)生，這些表是按照學(xué)號順序排列的。分別用順序查找法和二分搜索法來解決這個(gè)問題，下面就看看這兩個(gè)算法帶來的不同效果。給定一個(gè)學(xué)生的學(xué)號，那么順序查找法就是從表的開頭開始，將記錄與目標(biāo)學(xué)號一一對比，直到記錄與目標(biāo)學(xué)號匹配

16、或全部記錄比對完畢也沒有匹配上為止。假定有30000個(gè)學(xué)生，由于沒有目標(biāo)值的任何其他信息，因此不能確定要查找多少次才能得到結(jié)果。經(jīng)過多次查找，我們認(rèn)為平均查找深度是表的一半長度，那么順序搜索方法平均每次需要查找15000條記錄，假設(shè)檢索比對一條記錄需要1ms,那么整個(gè)查找需要15s，顯然這個(gè)等待時(shí)間是比較長的。,28,計(jì)算機(jī)問題求解算法——算法的有效性和正確性,接下來我們用二分搜索法來解決這個(gè)問題。二分搜索法是通過比較目標(biāo)值和表的中間

17、值來進(jìn)行查找。所以對于30000條記錄，最多通過15次就能夠找到目標(biāo)值或者在30000條記錄中不存在目標(biāo)值。假設(shè)檢索比對一條記錄需要1ms，那么整個(gè)查找需要0.015s，這個(gè)時(shí)間完全是我們可以接受的等待時(shí)間。當(dāng)在長度為N的表中應(yīng)用時(shí)，順序搜索方法的平均查找長度是n/2，而二分搜索法在最差情況下的查找長度不超過lgn。,29,計(jì)算機(jī)問題求解算法——程序設(shè)計(jì),程序設(shè)計(jì)（Programming）就是運(yùn)用計(jì)算思維分析問題、確定算法，選定軟件

18、平臺、編制計(jì)算機(jī)程序并實(shí)現(xiàn)求解等步驟來解決問題的全過程。程序設(shè)計(jì)語言（Programming Language），是用于書寫計(jì)算機(jī)程序的語言。語言的基礎(chǔ)是一組記號和一組規(guī)則。根據(jù)規(guī)則由記號構(gòu)成的記號串的集合就是語言。計(jì)算機(jī)程序就是選用特定的程序設(shè)計(jì)語言，按照解決實(shí)際問題的算法步驟，而編制好的具有特殊功能的指令序列。,30,,案例實(shí)踐10 計(jì)算機(jī)問題求解算法,概述算法的發(fā)現(xiàn)問題求解的藝術(shù)算法的概念算法的表示算法的有效性和正確

19、性程序設(shè)計(jì)案例分析與求解,31,計(jì)算機(jī)問題求解算法——程序設(shè)計(jì),程序設(shè)計(jì)的過程大致分下列幾個(gè)步驟：選定一種高級程序設(shè)計(jì)語言（如：Visual Basic、C、JAVA等）；安裝好選定語言的運(yùn)行環(huán)境（語言處理程序）；啟動(dòng)并進(jìn)入程序編輯狀態(tài)；依照算法和高級程序設(shè)計(jì)語言語法規(guī)則編制計(jì)算機(jī)程序源代碼；運(yùn)行計(jì)算機(jī)程序并經(jīng)過調(diào)試實(shí)現(xiàn)應(yīng)用問題的求解。,32,計(jì)算機(jī)問題求解算法——程序設(shè)計(jì),著名的瑞士計(jì)算機(jī)科學(xué)家尼克勞斯.沃斯（Nik

20、laus E. Wirth）提出了：算法+數(shù)據(jù)結(jié)構(gòu)=程序。其中，算法在整個(gè)程序設(shè)計(jì)過程中具有重要的作用，它能夠提供一種思考問題的方向和問題求解的方法。通過計(jì)算思維可以歸納出問題的算法思路，借助高級程序設(shè)計(jì)語言作為程序設(shè)計(jì)的工具，結(jié)合相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，可以驗(yàn)證算法的可行性并實(shí)現(xiàn)問題的最終求解。,33,,案例實(shí)踐10 計(jì)算機(jī)問題求解算法,概述算法的發(fā)現(xiàn)問題求解的藝術(shù)算法的概念算法的表示算法的有效性和正確性程序設(shè)計(jì)案例分析與求解

21、,34,計(jì)算機(jī)問題求解算法——案例分析與求解,牧羊人過河有一個(gè)牧羊人，帶著一頭羊，一只狼和一顆大白菜準(zhǔn)備過河。他找到一只很小的竹排，每次只能帶一樣?xùn)|西過去，可是如果讓狼與羊單獨(dú)在一起，狼會(huì)吃羊；如果讓羊與白菜單獨(dú)在一起，羊會(huì)吃白菜；牧羊人應(yīng)如何過河？,35,計(jì)算機(jī)問題求解算法——案例分析與求解,牧羊人過河這是一個(gè)邏輯推理類的趣味性問題，沒有涉及數(shù)學(xué)計(jì)算方面的要求，僅僅是根據(jù)給出的條件制約，做合理性的邏輯推理即可。具體

22、解決方案是：只需要做一個(gè)簡單的情景模擬，保證羊與狼不能獨(dú)處、羊與白菜不能獨(dú)處、竹排每次只能搭載牧羊人和一樣物件。對于這個(gè)問題，人與計(jì)算機(jī)的問題求解思路是一致的，只是在具體實(shí)現(xiàn)上，人是依靠邏輯推理，而計(jì)算機(jī)是依據(jù)邏輯條件判斷。,36,計(jì)算機(jī)問題求解算法——案例分析與求解,牧羊人過河,37,計(jì)算機(jī)問題求解算法——案例分析與求解,牧羊人過河,38,計(jì)算機(jī)問題求解算法——案例分析與求解,牧羊人過河,39,計(jì)算機(jī)問題求解算法——案例分析

23、與求解,牧羊人過河,40,計(jì)算機(jī)問題求解算法——案例分析與求解,牧羊人過河,41,計(jì)算機(jī)問題求解算法——案例分析與求解,推算年齡約翰并沒有見過蘇珊的三個(gè)孩子，蘇珊讓約翰猜測她三個(gè)孩子的年齡。,42,計(jì)算機(jī)問題求解算法——案例分析與求解,推算年齡蘇珊告訴約翰，三個(gè)孩子的年齡的乘積是36。在考慮了這個(gè)線索之后，約翰回答說，結(jié)果并不唯一，還需要另外的線索。于是蘇珊告訴了約翰這三個(gè)孩子的年齡總和。在把新的線索考慮進(jìn)去之后，約翰再次回

24、答說，結(jié)果依然不唯一，還需要另外的線索。于是，蘇珊又告訴約翰，她最大的孩子會(huì)演奏鋼琴。得到這個(gè)線索后，約翰就將三個(gè)孩子的年齡推算出來了，并得到蘇珊的確認(rèn)。三個(gè)孩子的年齡到底分別是多少？,43,計(jì)算機(jī)問題求解算法——案例分析與求解,推算年齡解決方案是：需要將所有可能的線索都羅列出來。假設(shè)三個(gè)孩子的年齡分別為：X、Y和Z；線索一：X*Y*Z=36 （發(fā)現(xiàn)有多種組合，不能得到唯一結(jié)果）線索二：確定X+Y+Z的和值 （發(fā)現(xiàn)有兩個(gè)重

25、復(fù)和值，而這個(gè)值恰恰是蘇珊告訴約翰的 這三個(gè)孩子的年齡總和，所以依然不能得到唯一結(jié)果，但是約翰知道了結(jié)果就是這兩個(gè)組合之一了）線索三：最大孩子會(huì)彈鋼琴（假設(shè)X是最大孩子的年齡，說明：X>Y 同時(shí)X>Z）至此，在確定問題是可解的（有唯一結(jié)果）前提下，找處符合條件的年齡值。,44,計(jì)算機(jī)問題求解算法——案例分析與求解,推算年齡對于這個(gè)問題，是在逐步推理的過程中，驗(yàn)證線索的充分性，進(jìn)而發(fā)現(xiàn)問題求解的可行性。在

26、這個(gè)方面，人與計(jì)算機(jī)的問題求解思路有些不同，比如在具體實(shí)現(xiàn)上，人是依靠邏輯推理，找出符合條件的可能的數(shù)，并需要保證答案是唯一的。而計(jì)算機(jī)是通過窮舉法，在一個(gè)可能的范圍，一個(gè)個(gè)代入線索公式中進(jìn)行邏輯條件判斷，如果都滿足，就得到最終的結(jié)果了，但是這樣得到的結(jié)果可能有多種組合。,45,計(jì)算機(jī)問題求解算法——案例分析與求解,推算年齡如果只有線索一，會(huì)有很多種可能情況，結(jié)果并不唯一；加上線索二，結(jié)果依然不唯一；再加上線索三之后，結(jié)果才明朗。

27、窮舉法，也叫枚舉法或列舉法。在研究對象是由有限個(gè)元素構(gòu)成的集合時(shí)，把所有對象一一列舉出來，再對其一一進(jìn)行研究。有時(shí)窮舉法用于破譯密碼，又稱為暴力破解法，即將密碼進(jìn)行各種可能組合逐個(gè)推算直到找出真正的密碼為止。,46,計(jì)算機(jī)問題求解算法——案例分析與求解,百錢買百雞古代算經(jīng)中有一個(gè)經(jīng)典的數(shù)學(xué)算題：要求用一百個(gè)銅錢，去買回一百只雞來。其中：公雞一只5錢、母雞一只3錢，小雞一錢3只。問一百只雞中公雞、母雞、小雞各多少？,47,計(jì)算機(jī)問題求

28、解算法——案例分析與求解,百錢買百雞設(shè)可能的雞只數(shù)為：雞翁：X只，雞母：Y只，雞雛：Z只線索一：X+Y+Z=100 （只）線索二：5*X+3*Y+Z/3=100 （錢）三個(gè)未知數(shù)，兩個(gè)方程，無法求解但如果將X和Y可能的只數(shù)逐個(gè)枚舉（窮舉）出來，帶入上面兩個(gè)方程，就可以得解：X可能的只數(shù)是：0~20Y可能的只數(shù)是：0~33Z可能的只數(shù)是：Z=100-X-Y,48,計(jì)算機(jī)問題求解算法——案例分析與求解,百錢買百雞對

29、于這個(gè)問題，人與計(jì)算機(jī)的問題求解思路類似，只是由于需要枚舉的數(shù)據(jù)范圍比較大，如果僅僅是通過手工計(jì)算，需要耗費(fèi)大量的時(shí)間，而通過計(jì)算機(jī)來解決，就只需要一眨眼的瞬間就完成了。這個(gè)問題得到的結(jié)果可能有多種組合。,49,計(jì)算機(jī)問題求解算法——案例分析與求解,剪正方形從一張長2002毫米，寬847毫米的長方形紙片上，剪下一個(gè)邊長盡可能大的正方形，如果剩下的部分不是正方形，那么在剩下的紙片上再剪下一個(gè)邊長盡可能大的正方形，按照上面的過程不斷地重

30、復(fù)，最后剪得的正方形的邊長是多少毫米呢？,50,計(jì)算機(jī)問題求解算法——案例分析與求解,剪正方形這個(gè)問題表面上看，似乎是個(gè)純手工操作，但如果把思路稍稍往規(guī)律上靠，就會(huì)發(fā)現(xiàn)這是一個(gè)在指定的兩個(gè)數(shù)2002和847之間求最大公約數(shù)的問題。首先必須先了解數(shù)學(xué)上關(guān)于公倍數(shù)和公約數(shù)的概念。公倍數(shù)是兩個(gè)正整數(shù)的公共倍數(shù)（有無限多個(gè)）。而公約數(shù)是兩個(gè)正整型數(shù)的公共約數(shù)（通常也有多個(gè)）。,51,計(jì)算機(jī)問題求解算法——案例分析與求解,剪正方形“輾轉(zhuǎn)

31、相除法”又叫做“歐幾里得算法”，是歐幾里得在他的著作《幾何原本》第七卷中提出的。利用這個(gè)方法，可以較快地求出兩個(gè)自然數(shù)的最大公約數(shù)。, 當(dāng)將問題求解的算法歸納出來了，直接用手工運(yùn)算也不是不可，只是效率太低。如果可以配合計(jì)算機(jī)高級語言環(huán)境實(shí)現(xiàn)的語法規(guī)則和控制結(jié)構(gòu)，就可以高效輕松地完成運(yùn)算，得到所需的結(jié)果。這里會(huì)用到迭代的算法，它的基本思想是：不斷用新值取代變量的舊值，或由舊值遞推出變量的新值。,52,計(jì)算機(jī)問題求解算法——案例分析與

32、求解,比賽評分計(jì)算在N個(gè)評委給出的大小不同的無序評分中，去掉一個(gè)最高分和最低分，然后求平均分?jǐn)?shù)。,53,計(jì)算機(jī)問題求解算法——案例分析與求解,比賽評分計(jì)算這類問題有兩個(gè)關(guān)鍵點(diǎn)：一個(gè)是找出最大和最??；二個(gè)是求和再平均。在N個(gè)數(shù)中找最大最小的方法很簡單，只要預(yù)設(shè)兩個(gè)變量，用于存放最大和最小值，將N個(gè)數(shù)中的第一個(gè)數(shù)作為最大最小的初值，依次與其他N-1個(gè)數(shù)逐個(gè)比較大小，大的放到存放最大的變量中，小的放到存放最小的變量中。至于求和，只要

33、逐個(gè)將N個(gè)數(shù)累加起來，再減去得到的最大最小數(shù)，最后除以N-2即得平均分。,54,計(jì)算機(jī)問題求解算法——案例分析與求解,分卡牌有11個(gè)人圍成一圈，按固定規(guī)則發(fā)卡牌，依次按1、3、6、8、11、2、5、7、10、1、4、6、……的序號發(fā)，問至少發(fā)到多少張時(shí)每人手上至少都有卡牌？最后拿到卡牌的是幾號？每個(gè)人手上的牌數(shù)分別是多少？,55,計(jì)算機(jī)問題求解算法——案例分析與求解,分卡牌這個(gè)問題需要考慮的線索比較多：當(dāng)前該給幾號發(fā)牌；發(fā)出

34、卡牌的計(jì)數(shù)；每個(gè)人手中卡牌的計(jì)數(shù)；分發(fā)順序號的規(guī)律；判斷是否有人手中無牌；什么時(shí)候結(jié)束發(fā)牌。在這個(gè)問題的具體處理中，整體發(fā)牌過程是一個(gè)需要重復(fù)處理的過程，只是在每發(fā)出一張牌，就需要處理上面羅列的多條線索，為下一次發(fā)牌做準(zhǔn)備。,56,,規(guī)則：有11個(gè)人圍成1圈，發(fā)卡牌，依次給1、3、6、8、11、2、5、7、10、1、4、6、…號發(fā)，問至少發(fā)到多少張時(shí)每人都有卡牌？最后拿到卡牌的是幾號。,發(fā)卡牌,57,,,58,,1,,59,,

35、2,,,60,,3,,,,61,,4,,,,,,62,,5,,,,,,63,,6,,,,,,,64,,7,,,,,,,,65,,8,,,,,,,,,66,,9,,,,,,,,,,67,,,,,,,,,,,10,,68,,,,,,,,,,,11,,,69,,,,,,,,,,,12,,,,70,,,,,,,,,,,13,,,,,13,71,計(jì)算機(jī)問題求解算法——案例分析與求解,兔子繁殖問題一般而言，兔子在出生兩個(gè)月后，就具備了繁殖能力，

36、一對兔子每個(gè)月能生出一對小兔子來。如果所有兔子都不死，那么一年以后可以繁殖多少對兔子？,72,計(jì)算機(jī)問題求解算法——案例分析與求解,兔子繁殖問題兔子繁殖問題，是著名的Fibonacci（斐波拉契）序列數(shù)的趣味版。Fibonacci（斐波拉契）序列數(shù)的計(jì)算，是通過遞推算法實(shí)現(xiàn)的。遞推算法是數(shù)學(xué)上常用的一種算法，即通過已知條件，利用數(shù)據(jù)之間的特定關(guān)系得出中間推論，直至得到最終結(jié)果的算法。1、1、2、3、5、8、13、21……，從這個(gè)

37、數(shù)列不難發(fā)現(xiàn)其中的規(guī)律：從第3項(xiàng)開始，當(dāng)前項(xiàng)等于其前兩項(xiàng)之和：F（N）=F（N-1）+F（N-2）。,73,計(jì)算機(jī)問題求解算法——案例分析與求解,楊輝三角形楊輝三角形的陣列中，值與值之間存在著一定的推算關(guān)系，如圖所示是5行和6行的楊輝三角形陣列，那么如何推算更多行的數(shù)值？,74,111121133114641,12345,12345,,,,,,,,,,,,楊輝三角形,X(1)=1,x(2)=0,x(3)=0,x(4)

38、=0,x(5)=0X(1)=1,x(2)=1,x(3)=0,x(4)=0,x(5)=0X(1)=1,x(2)=2,x(3)=1,x(4)=0,x(5)=0X(1)=1,x(2)=3,x(3)=3,x(4)=1,x(5)=0X(1)=1,x(2)=4,x(3)=6,x(4)=3,x(5)=1,,,,,歸納整理輸出N行N列的楊輝三角形的算法（要求用一維數(shù)組實(shí)現(xiàn)）,i=1→n，j=(i-1)→2(遞減),x(j)=x(j-1)+x(j

39、),,75,111121133114641,12345,12345,,,,,,,,,,,,楊輝三角形,X(1,1)=1,x(1,2)=0,x(1,3)=0,x(1,4)=0,x(1,5)=0X(2,1)=1,x(2,2)=1,x(2,3)=0,x(2,4)=0,x(2,5)=0X(3,1)=1,x(3,2)=2,x(3,3)=1,x(3,4)=0,x(3,5)=0X(4,1)=1,x(4,2)=3,x(4,3)=3

40、,x(4,4)=1,x(4,5)=0X(5,1)=1,x(5,2)=4,x(5,3)=6,x(5,4)=3,x(5,5)=1,,,,,歸納整理輸出N行N列的楊輝三角形的算法（要求用二維數(shù)組實(shí)現(xiàn)）,x(i,j)=x(i-1,j-1)+x(i-1,j),,i=3→n,j=2→i,76,計(jì)算機(jī)問題求解算法——案例分析與求解,排序問題對給定的N個(gè)大小不同的無序數(shù)進(jìn)行從小到大整理排序。,77,三杯水顏色深淺排序,對三杯不同顏色的水進(jìn)行顏色深

41、淺排序處理，你會(huì)怎么做？計(jì)算機(jī)又會(huì)怎么做？計(jì)算機(jī)為什么那樣做？,,,,,,,,,,,,,A B C,輸入：,輸出：,分析過程,可能的輸入排列情況,,,,,分析過程,,,,,,,,,,,,,,A B C T,第一步：,交換：,,,,,,,,,,,,,,,,,,,,,,,,A

42、 B C T,第二步：,交換：,,,,,,,,,,,,分析過程,,,,,,,,,,,,,,A B C T,第三步：,交換：,,,,,,,,,,,,分析過程,,,,,A B C,第三步：,交換：,,,,,,最終結(jié)

43、果,算法表示,開始,分別從鍵盤輸入數(shù)值A(chǔ)，B，C,,交換A,B的值，T=A,A=B,B=T,輸出結(jié)果A,B,C,結(jié)束,,,,,A>B?,,交換A,C的值，T=A,A=C,C=T,,A>C?,,A,A,,B>C?,,,,,,,,N,N,N,Y,Y,Y,,,,交換B,C的值，T=B,B=C,C=T,,程序代碼實(shí)現(xiàn),85,,,原始排列順序,排序后的順序,比較交換排序法,86,,,原始排列順序,排序后的順序,N個(gè)數(shù)的從小到大排

44、序問題,87,,,第一輪比較,,比較交換排序法,88,,,第一輪比較,,比較交換排序法,89,,,第一輪比較,,第一輪比較后的順序,比較交換排序法,90,,,第二輪比較,,比較交換排序法,91,,,第二輪比較,,第二輪比較后的順序,比較交換排序法,92,,,第三輪比較,,第三輪比較后的順序,比較交換排序法,93,,,第四輪比較,,第四輪比較后的順序,比較交換排序法,94,,,比較交換排序法,第四輪比較后的順序,第四輪比較,95,,,最終

45、排好的順序,比較交換排序法,96,,,原始排列順序,排序后的順序,選擇排序法,97,,,第一輪比較,排序后的順序,選擇排序法,,,98,,,第一輪比較,排序后的順序,選擇排序法,,,99,,,第一輪比較,排序后的順序,選擇排序法,,,100,,,第一輪比較,排序后的順序,選擇排序法,,,101,,,第一輪比較,排序后的順序,選擇排序法,,,,102,,,第一輪比較結(jié)果,排序后的順序,選擇排序法,103,,,第二輪比較,排序后的順序,選擇

46、排序法,,,104,,,第二輪比較,排序后的順序,選擇排序法,,,105,,,第二輪比較,排序后的順序,選擇排序法,,,106,,,第二輪比較,排序后的順序,選擇排序法,,,,107,,,第二輪比較結(jié)果,排序后的順序,選擇排序法,108,,,第三輪比較,排序后的順序,選擇排序法,,,109,,,第三輪比較,排序后的順序,選擇排序法,,,110,,,第三輪比較,排序后的順序,選擇排序法,,,,111,,,第三輪比較結(jié)果,排序后的順序,選擇

47、排序法,112,,,第四輪比較,排序后的順序,選擇排序法,,,113,,,第四輪比較,排序后的順序,選擇排序法,,,,114,,,排序后的順序,選擇排序法,最終排好的順序,115,,,原始排列順序,排序后的順序,冒泡排序法,116,,,第一輪比較,,冒泡排序法,,117,,,第一輪比較,,冒泡排序法,,118,,,第一輪比較,,冒泡排序法,,119,,,第一輪比較,,冒泡排序法,,120,,,第一輪比較后得到最大的,,第一輪比較后的順序

48、,冒泡排序法,,,121,,,第二輪比較,,第一輪比較后的順序,冒泡排序法,,,122,,,第二輪比較,,冒泡排序法,,,123,,,第二輪比較,,冒泡排序法,,,124,,,第二輪比較后得到次大的,,第二輪比較后的順序,冒泡排序法,,,,125,,,第三輪比較,,冒泡排序法,,,,126,,,第三輪比較,,冒泡排序法,,,,127,,,第三輪比較后得到第三大的,,第三輪比較后的順序,冒泡排序法,,,,,128,,,第四輪比較,,冒泡排

49、序法,,,,,,129,,,第四輪比較之后得到最小和次小,,第四輪比較后的順序,冒泡排序法,,,,,,,130,計(jì)算機(jī)問題求解算法——案例分析與求解,信息查找問題在給定的N個(gè)大小不同的無序數(shù)中尋找指定的數(shù)；在給定的N個(gè)大小不同的有序數(shù)中尋找指定的數(shù)。,131,,1 2 3 4 5 6 7 8 9 10 11 12 13

50、 14 15,,N個(gè)有序數(shù)中查找指定數(shù)問題,132,,折半查找法,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,,TOP=1,,BOTTOM=15,MIDDLE=（BOTTOM+TOP）/2=8,,133,,折半

51、查找法,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,,,TOP=1,,BOTTOM=15,MIDDLE=（BOTTOM+TOP）/2=8,,>?,<?,=?,134,,折半查找法,1 2 3 4 5 6 7 8

52、 9 10 11 12 13 14 15,,,TOP= MIDDLE+1=9,,BOTTOM=15,MIDDLE=（BOTTOM+TOP）/2=12,,>?,<?,=?,135,,折半查找法,1 2 3 4 5 6 7 8 9 10 1

53、1 12 13 14 15,,,TOP= MIDDLE+1=9,,BOTTOM=MIDDLE-1=11,MIDDLE=（BOTTOM+TOP）/2=10,,>?,<?,=?,136,,折半查找法,1 2 3 4 5 6 7 8 9 10 11 12

54、 13 14 15,,,TOP= MIDDLE+1=11,,BOTTOM=MIDDLE-1=11,MIDDLE=（BOTTOM+TOP）/2=11,,=?,找到了！,137,,折半查找法,1 2 3 4 5 6 7 8 9 10 11 12 13

55、 14 15,,TOP=1,,BOTTOM=15,MIDDLE=（BOTTOM+TOP）/2=8,,138,,折半查找法,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,,TOP=1,,BOTTOM=15,MIDDLE=（B

56、OTTOM+TOP）/2=8,,139,,折半查找法,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,,TOP=MIDDLE+1=9,,BOTTOM=15,MIDDLE=（BOTTOM+TOP）/2=12,,140,,折半查找法,1 2 3 4 5

57、 6 7 8 9 10 11 12 13 14 15,,TOP=MIDDLE+1=13,,BOTTOM=15,MIDDLE=（BOTTOM+TOP）/2=14,,141,,折半查找法,1 2 3 4 5 6 7 8 9 10