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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34、卡牌的計數(shù)；每個人手中卡牌的計數(shù)；分發(fā)順序號的規(guī)律；判斷是否有人手中無牌；什么時候結(jié)束發(fā)牌。在這個問題的具體處理中，整體發(fā)牌過程是一個需要重復(fù)處理的過程，只是在每發(fā)出一張牌，就需要處理上面羅列的多條線索，為下一次發(fā)牌做準備。,56,,規(guī)則：有11個人圍成1圈，發(fā)卡牌，依次給1、3、6、8、11、2、5、7、10、1、4、6、…號發(fā)，問至少發(fā)到多少張時每人都有卡牌？最后拿到卡牌的是幾號。,發(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,計算機問題求解算法——案例分析與求解,兔子繁殖問題一般而言，兔子在出生兩個月后，就具備了繁殖能力，

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

37、數(shù)列不難發(fā)現(xiàn)其中的規(guī)律：從第3項開始，當(dāng)前項等于其前兩項之和：F（N）=F（N-1）+F（N-2）。,73,計算機問題求解算法——案例分析與求解,楊輝三角形楊輝三角形的陣列中，值與值之間存在著一定的推算關(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ù)組實現(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ù)組實現(xiàn)）,x(i,j)=x(i-1,j-1)+x(i-1,j),,i=3→n,j=2→i,76,計算機問題求解算法——案例分析與求解,排序問題對給定的N個大小不同的無序數(shù)進行從小到大整理排序。,77,三杯水顏色深淺排序,對三杯不同顏色的水進行顏色深

41、淺排序處理，你會怎么做？計算機又會怎么做？計算機為什么那樣做？,,,,,,,,,,,,,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,,程序代碼實現(xiàn),85,,,原始排列順序,排序后的順序,比較交換排序法,86,,,原始排列順序,排序后的順序,N個數(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,計算機問題求解算法——案例分析與求解,信息查找問題在給定的N個大小不同的無序數(shù)中尋找指定的數(shù)；在給定的N個大小不同的有序數(shù)中尋找指定的數(shù)。,131,,1 2 3 4 5 6 7 8 9 10 11 12 13

50、 14 15,,N個有序數(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