第1章算法與程序設(shè)計(jì)

1、算算 法法1 1算法的定義算法的定義所謂算法，是指為解決問(wèn)題而采用的方法和步驟。所謂算法，是指為解決問(wèn)題而采用的方法和步驟。隨著信息社會(huì)的發(fā)展，計(jì)算機(jī)已成為人們?nèi)粘Ｉ詈凸ぷ髦胁豢扇鄙俚墓ぞ?。?tīng)音樂(lè)、看電影、玩游戲、打字、畫(huà)卡通畫(huà)、處理數(shù)據(jù)，計(jì)算機(jī)幾乎滲透到了人們生活的所有領(lǐng)域，那計(jì)算機(jī)是怎樣工作的呢？要想弄清楚這個(gè)問(wèn)題，算法的學(xué)習(xí)是一個(gè)開(kāi)始。在計(jì)算機(jī)中，利用計(jì)算機(jī)解決問(wèn)題的方法和步驟稱(chēng)為計(jì)算機(jī)的算法。算算 法法然而不是所有問(wèn)題計(jì)算機(jī)都能夠解決，根據(jù)圖靈理論：只要能夠分解為有限步驟，并且每一步驟都可以轉(zhuǎn)化為計(jì)算機(jī)可以執(zhí)行的程序指令的問(wèn)題，才是計(jì)算機(jī)可以解決的問(wèn)題。這里面包含兩層含義，一是算法的

2、步驟必須是有限的，二是算法最終可以轉(zhuǎn)化為計(jì)算機(jī)所執(zhí)行的程序。因此算法設(shè)計(jì)是程序設(shè)計(jì)的基礎(chǔ)，算法研究成為了計(jì)算機(jī)科學(xué)的核心課題之一。1 1算法的定義算法的定義算算 法法2 2算法的算法的基本特征基本特征（1）可行性（2）確定性（3）有窮性（4）零到多個(gè)輸入（5）至少一個(gè)輸出算算 法法3 3算法的算法的組成要素組成要素一個(gè)算法通常由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作；二是算法的控制結(jié)構(gòu)（1）對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作每個(gè)算法實(shí)際上是根據(jù)題意并結(jié)合環(huán)境選擇合適的操作所組成的一組指令序列，因此，計(jì)算機(jī)算法就是由計(jì)算機(jī)能處理的操作所組成的指令序列。而指令是計(jì)算機(jī)可以執(zhí)行的基本操作。算算 法法3 3

3、算法的算法的組成要素組成要素操作離不開(kāi)運(yùn)算。在一般的計(jì)算機(jī)系統(tǒng)中，基本的操作運(yùn)算有以下4類(lèi)。 算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。 邏輯運(yùn)算：主要包括“與”、“或”、“非”等運(yùn)算。 關(guān)系運(yùn)算：主要包括“大于”、“小于”、“等于”、“不等于”等運(yùn)算。 數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作算算 法法3 3算法的算法的組成要素組成要素在編制計(jì)算機(jī)的算法時(shí)通常要考慮很多與方法和分析無(wú)關(guān)的細(xì)節(jié)問(wèn)題（如語(yǔ)法規(guī)則），因此在設(shè)計(jì)算法的開(kāi)始，通常并不直接利用計(jì)算機(jī)來(lái)描述算法，而是用別的描述工具（如流程圖、專(zhuān)門(mén)的算法描述語(yǔ)言，甚至用自然語(yǔ)言）來(lái)描述算法。但不管用哪種工具來(lái)描述算法，算法的設(shè)計(jì)一般都要從上述

4、4類(lèi)基本操作運(yùn)算的考慮，根據(jù)題意從這些基本操作運(yùn)算中選擇合適的操作組成解題的操作序列。算算 法法3 3算法的算法的組成要素組成要素（2）算法的控制結(jié)構(gòu)一個(gè)算法的功能不僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱(chēng)為算法的控制結(jié)構(gòu)。算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計(jì)是否符合結(jié)構(gòu)化原則。描述算法的工具通常有自然語(yǔ)言、傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語(yǔ)言等，而流程圖特別是傳統(tǒng)流程圖是初學(xué)者最喜歡的算法表示。一個(gè)算法一般都可以用順序、選擇、循環(huán)這3種基本控制結(jié)構(gòu)組合而成。我們通過(guò)下面的傳統(tǒng)流程

5、圖的示意圖，直觀地來(lái)了解這3種結(jié)構(gòu)及圖框。算算 法法3 3算法的算法的組成要素組成要素順序結(jié)構(gòu)：算算 法法3 3算法的算法的組成要素組成要素選擇結(jié)構(gòu)：算算 法法3 3算法的算法的組成要素組成要素循環(huán)結(jié)構(gòu)： (a) (a) 當(dāng)型循環(huán)當(dāng)型循環(huán) (b) (b) 直到循環(huán)直到循環(huán)算算 法法3 3算法的算法的組成要素組成要素流程圖常用圖框與符號(hào)算算 法法4 4算法算法設(shè)計(jì)基本方法設(shè)計(jì)基本方法（1）窮舉法窮舉法是基于計(jì)算機(jī)特點(diǎn)而進(jìn)行解題的思維方法。其基本思想是：根據(jù)提出的問(wèn)題列舉所有可能的情況，然后通過(guò)一一驗(yàn)證是否符合整個(gè)問(wèn)題的求解要求，而得到問(wèn)題的解。因此，窮舉法常用于解決“是否存在”或“有多少種可能”

6、等類(lèi)型的問(wèn)題，如求解不定方程的問(wèn)題。窮舉法雖然是一種比較笨拙而原始的方法，且其運(yùn)算量比較大，但在有些實(shí)際問(wèn)題中（如尋找路徑、查找、搜索等問(wèn)題），局部使用窮舉法卻是很有效的，因此，窮舉法是計(jì)算機(jī)算法中的一個(gè)基礎(chǔ)算法。算算 法法4 4算法算法設(shè)計(jì)基本方法設(shè)計(jì)基本方法（2）歸納法歸納法是從個(gè)別性知識(shí)引出一般性知識(shí)的推理方法。其基本思想是：通過(guò)列舉少量具有代表性的信息，經(jīng)過(guò)分析，最后找出一般性的結(jié)論。（3）遞推法所謂遞推，是指從已知的初始條件出發(fā)，逐次推出所要求的各序列結(jié)果和最后結(jié)果。遞推法在數(shù)值計(jì)算中是極為常見(jiàn)的。其思想是把一個(gè)復(fù)雜的龐大的計(jì)算過(guò)程轉(zhuǎn)化為簡(jiǎn)單過(guò)程的多次重復(fù)。它是計(jì)算機(jī)中的一種常用算法

7、。該算法利用了計(jì)算機(jī)速度快和不知疲倦的機(jī)器特點(diǎn)。算算 法法4 4算法算法設(shè)計(jì)基本方法設(shè)計(jì)基本方法（4）遞歸法人們?cè)诮鉀Q一些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程度（如問(wèn)題的規(guī)模等），一般總是將問(wèn)題逐層分解，最后歸結(jié)為一些規(guī)模較小的同類(lèi)簡(jiǎn)單的問(wèn)題。這種將問(wèn)題逐層分解的過(guò)程，實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是當(dāng)解決了最后那些同類(lèi)簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的基本思想。在工程實(shí)際中，有許多問(wèn)題就是用遞歸來(lái)定義的，數(shù)學(xué)中的許多函數(shù)也是用逆歸來(lái)定義的。遞歸在計(jì)算機(jī)程序設(shè)計(jì)中占據(jù)很重要的地位。算算 法法4 4算法算法設(shè)計(jì)基本方法設(shè)計(jì)基本方法（5）回溯法回溯法也稱(chēng)為試探法，它是一種

8、系統(tǒng)地搜索問(wèn)題的解的方法。其基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路再試。它是工程中既不能用歸納法，又不能用遞推法、遞歸法，也不能進(jìn)行無(wú)限列舉的一類(lèi)問(wèn)題所采用的一種方法。對(duì)于這類(lèi)問(wèn)題，一種有效的方法就是“試”。通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)線索逐步試探，對(duì)于每一步，若試探成功，就得到問(wèn)題的解，若試探失敗，就逐步回退，換別的路線再進(jìn)行試探?；厮莘ㄔ谔幚韽?fù)雜數(shù)據(jù)結(jié)構(gòu)方面有著廣泛的應(yīng)用。算算 法法想一想想一想 做一做：做一做：1將5個(gè)蘋(píng)果放入x個(gè)籃子里，發(fā)現(xiàn)必有一個(gè)籃子的蘋(píng)果數(shù)不少于3個(gè)，用窮舉法求籃子數(shù)最多為幾個(gè)？2有一位師傅想考考他的兩個(gè)徒弟，看誰(shuí)更

9、聰明一些。他給每人一框花生去剝皮，看看每一?；ㄉ欠穸加蟹垡掳?，看誰(shuí)先給出答案。大徒弟費(fèi)了很大的力氣將花生全部剝完了；二徒弟只撿了幾個(gè)飽滿的、幾個(gè)干癟的、幾個(gè)熟透的、幾個(gè)沒(méi)熟的、幾個(gè)三仁的、幾個(gè)兩仁的和幾個(gè)一仁的，從總共不過(guò)一把花生中可以得出結(jié)論，顯然二徒弟比大徒弟聰明，那么二徒弟用的是什么方法？大徒弟用的是什么方法？算算 法法算法表示案例算法表示案例【案例1.1】 互換變量x和變量y的值案例分析：在計(jì)算機(jī)中，一個(gè)變量在內(nèi)存中均對(duì)應(yīng)相應(yīng)的存儲(chǔ)單元。而存儲(chǔ)器的性質(zhì)是：一個(gè)存儲(chǔ)單元一次只能存儲(chǔ)一個(gè)值，當(dāng)新值進(jìn)入時(shí)，則原值就被覆蓋。因此不能直接將x的值賦給y，或直接將y的值賦給x，而應(yīng)借助一個(gè)中間

10、變量z過(guò)渡。算算 法法算法表示案例算法表示案例【案例1.1】 互換變量x和變量y的值具體算法：算算 法法算法表示案例算法表示案例【案例1.2】 求ax+b=0的解案例分析：對(duì)于方程ax+b=0來(lái)講，應(yīng)該分情況討論方程的解。要對(duì)一次項(xiàng)系數(shù)a和常數(shù)項(xiàng)b的取值情況進(jìn)行分類(lèi)，分類(lèi)如下：（1）當(dāng)a 0時(shí)，方程有唯一的實(shí)數(shù)解 ；（2）當(dāng)a=0，b=0時(shí)，全體實(shí)數(shù)都是方程的解；（3）當(dāng)a=0，b 0時(shí)，方程無(wú)解。算算 法法算法表示案例算法表示案例【案例1.2】 求ax+b=0的解具體算法：算算 法法算法表示案例算法表示案例【案例1.3】 求1+2+100的值案例分析：通常，按照下列過(guò)程計(jì)算1+2+100的值

11、。第1步 0+1=1第2步 1+2=3第3步 3+3=6第4步 6+4=10第100步 4 950+100=5 050顯然，這個(gè)過(guò)程中包含重復(fù)操作的步驟，可以用循環(huán)結(jié)構(gòu)表示上述計(jì)算過(guò)程算算 法法算法表示案例算法表示案例【案例1.3】 求1+2+100的值具體算法：算算 法法算法表示案例算法表示案例【案例1.4】 將十進(jìn)制整數(shù)a轉(zhuǎn)化成二進(jìn)制數(shù)案例分析： 將十進(jìn)制整數(shù)轉(zhuǎn)化成二進(jìn)制數(shù)的方法是：除2求余反向取。具體算法：C C程序設(shè)計(jì)程序設(shè)計(jì)隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷深入和發(fā)展，利用計(jì)算機(jī)解決的問(wèn)題也越來(lái)越多、越來(lái)越復(fù)雜。要想讓計(jì)算機(jī)解決一個(gè)問(wèn)題，首先需要把解決問(wèn)題的方法和步驟設(shè)計(jì)出來(lái)，并且將解決問(wèn)題所

12、需要的數(shù)據(jù)合理組織，最后用計(jì)算機(jī)的語(yǔ)言表示出來(lái)，所以有人將程序描述為：程序 = 算法 + 數(shù)據(jù)結(jié)構(gòu) + 語(yǔ)言，而編寫(xiě)程序的過(guò)程就稱(chēng)為程序設(shè)計(jì)。由此可見(jiàn)，一個(gè)程序設(shè)計(jì)離不開(kāi)對(duì)問(wèn)題的分析、程序設(shè)計(jì)的基本方法和程序設(shè)計(jì)語(yǔ)言C C程序設(shè)計(jì)程序設(shè)計(jì)分析問(wèn)題為了能編寫(xiě)出解決問(wèn)題的程序，首先應(yīng)該分析問(wèn)題，然后設(shè)計(jì)算法，組織數(shù)據(jù)并用高級(jí)語(yǔ)言編寫(xiě)程序指令。分析問(wèn)題是第一步，也是最重要的步驟，這一步需要做以下幾方面的工作。1明確問(wèn)題的性質(zhì)計(jì)算機(jī)能夠解決的問(wèn)題不外乎兩類(lèi)：一類(lèi)是數(shù)值計(jì)算問(wèn)題，一類(lèi)是非數(shù)值計(jì)算問(wèn)題。不管是哪類(lèi)問(wèn)題其所用的方法、工具以及輸入/輸出的形式都會(huì)有所不同，因此明確問(wèn)題的性質(zhì)是分析問(wèn)題的基礎(chǔ)。C

13、 C程序設(shè)計(jì)程序設(shè)計(jì)分析問(wèn)題2了解解決問(wèn)題的必要條件這些必要條件包括：程序是否需要與用戶建立聯(lián)系，程序是否要處理數(shù)據(jù)，程序是否有輸出，需要什么樣的結(jié)果。如果程序要對(duì)數(shù)據(jù)進(jìn)行操作，那么還必須知道數(shù)據(jù)是什么以及這些數(shù)據(jù)代表什么。如果程序產(chǎn)生輸出結(jié)果，還應(yīng)該知道怎樣產(chǎn)生結(jié)果以及以何種形式來(lái)輸出結(jié)果。3合理分解問(wèn)題如果問(wèn)題比較復(fù)雜，應(yīng)該把復(fù)雜問(wèn)題分解為若干子問(wèn)題，每個(gè)子問(wèn)題只完成一項(xiàng)簡(jiǎn)單的功能，并且每個(gè)子問(wèn)題都重復(fù)步驟1和2。C C程序設(shè)計(jì)程序設(shè)計(jì)C程序設(shè)計(jì)的基本方法C程序設(shè)計(jì)的基本方法就是結(jié)構(gòu)化程序設(shè)計(jì)法。結(jié)構(gòu)化程序設(shè)計(jì)法也稱(chēng)為自上而下的設(shè)計(jì)、逐步細(xì)化和模塊化編程，即把問(wèn)題分解為若干個(gè)子問(wèn)題的方法。

14、在結(jié)構(gòu)化程序設(shè)計(jì)中，問(wèn)題被分解為若干較小的問(wèn)題，然后把所有子問(wèn)題的解決方法結(jié)合在一起來(lái)解決整個(gè)問(wèn)題。執(zhí)行結(jié)構(gòu)化程度設(shè)計(jì)的過(guò)程稱(chēng)為結(jié)構(gòu)化編程。結(jié)構(gòu)化程序設(shè)計(jì)要求把程序的結(jié)構(gòu)限制為順序、選擇和循環(huán)3種基本控制結(jié)構(gòu)，以便于提高程序的可讀性。采用這種結(jié)構(gòu)開(kāi)發(fā)出來(lái)的程序具有清晰的結(jié)構(gòu)層次，易于理解并便于修改調(diào)試。C C程序設(shè)計(jì)程序設(shè)計(jì)C程序設(shè)計(jì)的基本方法1按功能劃分模塊按功能劃分模塊的基本原則是：按照人們解決復(fù)雜問(wèn)題的普遍規(guī)律，使每個(gè)模塊都易于理解，同時(shí)各模塊的功能盡可能單一，各模塊之間的聯(lián)系盡量少，從而保證各模塊的可讀性和可理解性。2按層次組織模塊按層次組織模塊是劃分模塊的最好形式之一。在按層次組織模

15、塊時(shí)，一般上層模塊只指出“做什么”，具體“怎么做”由下層模塊精確描述。在圖1.9所示的層次結(jié)構(gòu)中，上層模塊給出任務(wù)，最后一層模塊才精確描述“怎么做”。C C程序設(shè)計(jì)程序設(shè)計(jì)C語(yǔ)言程序的構(gòu)成和基本格式1一個(gè)簡(jiǎn)單的C語(yǔ)言程序案例【案例1.5】 求半徑為2的圓的面積#include stdio.hmain( ) float r，s； /*定義變量r，s*/ r=2； /*給半徑r賦值*/ s=3.14*r*r； /*求出圓面積并放入變量s*/ printf(s=%f，s)； /*輸出圓面積的值*/C C程序設(shè)計(jì)程序設(shè)計(jì)C語(yǔ)言程序的構(gòu)成和基本格式2C語(yǔ)言程序的構(gòu)成和基本格式C語(yǔ)言程序是由函數(shù)構(gòu)成的。一

16、個(gè)C語(yǔ)言程序可以包含若干函數(shù)，但必須有且只有一個(gè)名為main的主函數(shù)，任何一個(gè)C語(yǔ)言程序都是從主函數(shù)開(kāi)始執(zhí)行的，即沒(méi)有主函數(shù)main( )，C語(yǔ)言程序?qū)⒉荒軋?zhí)行。C語(yǔ)言程序的每個(gè)函數(shù)均由函數(shù)頭部（如以上程序的main( )）和函數(shù)體“ ”組成，函數(shù)頭部的圓括號(hào)中間可以為空，但這對(duì)圓括號(hào)不能缺省。C語(yǔ)言的函數(shù)體由左花括號(hào)“”開(kāi)始，由右花括號(hào)“”結(jié)束。函數(shù)體包括數(shù)據(jù)定義部分和執(zhí)行部分。以上程序的第4行是定義部分，第57行是執(zhí)行部分。程序通過(guò)執(zhí)行部分向計(jì)算機(jī)系統(tǒng)發(fā)出操作指令。C C程序設(shè)計(jì)程序設(shè)計(jì)C語(yǔ)言程序的構(gòu)成和基本格式2C語(yǔ)言程序的構(gòu)成和基本格式不管是定義部分還是執(zhí)行部分，其組成成分均是語(yǔ)句，語(yǔ)句以分號(hào)“；”結(jié)束，特別要注意：分號(hào)“；”是C語(yǔ)句的一個(gè)組成成分，不能缺省。定義部分的語(yǔ)句叫做定義語(yǔ)句，在上述程序中只有一個(gè)定義語(yǔ)句，該語(yǔ)句的作用就是對(duì)程序中所需要的r、s定義并說(shuō)明它們是float類(lèi)型。程序的第5行是一條給半徑r賦值的語(yǔ)句，第6行是計(jì)算圓面積的值并賦給s的語(yǔ)句，第7行是按照定義的數(shù)據(jù)格式將s輸出到終端屏幕上的語(yǔ)句。C C程序設(shè)計(jì)程序設(shè)計(jì)C語(yǔ)言程序的構(gòu)成和基本格式2C