1、第4章 算法基礎(chǔ)4.1 算法的基本概念4.2 算法的三種結(jié)構(gòu)4.3 算法的表示4.4 算法設(shè)計(jì)基本方法4.5 算法的評價(jià)4.1.1 算法的起源周髀算經(jīng)九章算術(shù)最早四則運(yùn)算、最大公約數(shù)、最小公倍數(shù)、開平方根、開立方根、求素?cái)?shù)的埃拉托斯特尼篩法（簡稱埃氏篩），線性方程組求解第一個(gè)算法歐幾里得算法（輾轉(zhuǎn)相除法）求兩個(gè)正整數(shù)A和B的最大公約數(shù)：Step 1: 比較A和B兩個(gè)數(shù)，將A設(shè)置為較大的數(shù)，B為較小的數(shù)；Step 2: A除以B，得到余數(shù)R；Step 3: 如果R等于0，則最大公約數(shù)就是B，否則將B賦值給A，R賦值給B，重復(fù)Step2、Step3。4.1.2 算法的定義和特性為解決問題采用的方法

2、和步驟。算法是一組明確步驟的有序集合，它產(chǎn)生結(jié)果并在有限時(shí)間內(nèi)終止。算法特性 有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。 確定性：算法的每一步驟都必須是確切定義的。 輸入：一個(gè)算法有0個(gè)、1個(gè)或多個(gè)輸入。 輸出：一個(gè)算法必須有1個(gè)或多個(gè)輸出值。 可行性：算法的每一步操作都應(yīng)該是可執(zhí)行的。 1.順序結(jié)構(gòu) 按照順序從上向下依次執(zhí)行A和B，A和B代表算法的步驟。2.選擇結(jié)構(gòu)根據(jù)給定的條件判斷選擇哪一條分支，執(zhí)行相應(yīng)的步驟。3.循環(huán)結(jié)構(gòu)在給定條件成立時(shí)，反復(fù)執(zhí)行某些步驟，直到條件不成立為止。AAA4.3.1 自然語言自然語言（Natural Language）人們?nèi)粘Ｊ褂玫恼Z言?！景咐?.1】求任意3

3、個(gè)正整數(shù)a、b、c中的最大者。用自然語言可將算法表示如下：Step 1：輸入3個(gè)正整數(shù) a，b，c。Step2：若a大于b，則將a放到max中，否則將b放到max中。Step 3：若c大于max，則將c放到max中。Step 4：輸出max。4.3.2 流程圖 常用傳統(tǒng)流程圖符號(hào)求任意3個(gè)正整數(shù)a、b、c中的最大者的流程圖4.2.3 偽代碼偽代碼（Pseudo-code）又稱程序設(shè)計(jì)語言PDL，是用介于自然語言和計(jì)算機(jī)語言之間的文字和符號(hào)來描述算法。read a, b, cif ab amaxelse bmaxif cmax cmaxprint max4.2.4 程序設(shè)計(jì)語言用程序設(shè)計(jì)語言（P

4、rogramming Language）表示算法就是用計(jì)算機(jī)高級(jí)語言編寫程序，程序是可以在計(jì)算機(jī)上經(jīng)過編譯、連接、運(yùn)行出結(jié)果的算法表示。int max( int a, int b, int c) int max; if(a b)max = a;elsemax = b;if(c max)max = c;return max; int main(void) int a, b, c,Imax;scanf(%d%d%d,&a,&b,&c);Imax=max(a, b, c);printf(max=%d, Imax);4.3.1 求和【案例4.2】計(jì)算1100的和。YN開始0=s

5、um1=kk100sum + k =sumk+1 = k結(jié)束思考1：如何計(jì)算mn之間的偶數(shù)或奇數(shù)之和。ns.3211.32112111思考2：如何計(jì)算下式：4.3.2 累乘【案例4.3】計(jì)算10！ 。思考1：如何計(jì)算 的流程圖。思考2：如何計(jì)算下式：nx!9!7!5!3)sin(9753xxxxxx4.3.3 窮舉【案例4.4】百錢買百雞。我國古代的張丘建算經(jīng)中有一個(gè)著名的百雞問題：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一。百錢買百雞，問雞翁、雞母、雞雛各幾何？假設(shè)雞翁、雞母、雞雛分別為a,b,c只，由題意可得如下兩個(gè)方程： a+b+c=100 （1） 5a+3b+c/3=100 （2）

6、采用窮舉法，依次對a,b,c取值范圍內(nèi)的各數(shù)一一試探，找出滿足方程（1）和（2）的組合。流程圖參見教材4.9。4.3.4 迭代【案例4.5】猴子吃桃問題。一只猴子第一天摘下若干桃子，當(dāng)即吃了一半，還不過癮，又多吃了一個(gè)，第二天早上又將剩下的桃子吃掉一半，又多吃了一個(gè)。以后每天早上都吃了前一天剩下的一半零一個(gè)。到第10天早上想再吃時(shí)，見只剩下一個(gè)桃子了。求猴子第一天共摘了多少個(gè)桃子？迭代法又稱遞推法，它是從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。4.3.4 迭代素?cái)?shù)是指只能被1和它自己整除的數(shù)?！景咐景咐?.6】給定一個(gè)數(shù)】給定一個(gè)數(shù)n，判，判斷斷n是不是素?cái)?shù)。是不是素?cái)?shù)?？?/p>

7、以證明，只需依次用2 或2 之間的各數(shù)去除n就可說明n是不是素?cái)?shù)。4.3.5 遞歸遞歸是把一個(gè)復(fù)雜的問題逐層分解為最簡單問題，再由最簡單問題逐層回代，直到求出問題的解?！景咐咐?.6】年齡問題。有5個(gè)人坐在一起，問第5個(gè)人多少歲？他說比第4個(gè)人大2歲。問第4個(gè)人的歲數(shù)，他說比第3個(gè)人大2歲。問第3個(gè)人的歲數(shù)，他說比第2個(gè)人大2歲。問第2個(gè)人，他說比第1個(gè)人大2歲。最后問第1個(gè)人，他說是10歲。請問第5個(gè)人多大？4.3.5 遞歸（續(xù)）【案例案例4.7】Fibonacci數(shù)列。“兔子繁殖問題”：假定一對小兔子一個(gè)月就可以長成大兔子（一雄一雌），而一對大兔子每個(gè)月都會(huì)生出一對小兔子。如果年初養(yǎng)了一

8、對小兔子，到年底時(shí)將有多少對兔子? （假設(shè)兔子沒有死亡而且嚴(yán)格按照上述規(guī)律長大與繁殖）月兔1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計(jì)1123581321345589144兔子繁殖的結(jié)果兔子繁殖的結(jié)果4.3.5 遞歸（續(xù)）假設(shè)第N個(gè)月的兔子數(shù)目是F(N)，可以得到如下公式：該公式遞歸地定義了Fibonacci數(shù)列。2N)2N(F)1N(F2N1)N(F4.3.5 遞歸（續(xù)）【案例案例4.8】給2個(gè)變量a和b分別輸入50和10，然后將大數(shù)50存放在b中，小數(shù)10存放在a中。4.3.6 兩個(gè)變量值的交換1順序查找順

9、序查找4.3.7 查找【案例【案例4.9】在給定的10個(gè)數(shù)23，45，62，12，33，87，90，55，13，79組成的列表中查找數(shù)12。2二分查找二分查找4.3.7 查找查找是從列表的中間位置開始，如果該位置上的數(shù)據(jù)和目標(biāo)數(shù)據(jù)（待查找的數(shù)據(jù)）相等，則查找成功；若目標(biāo)數(shù)據(jù)大于中間位置的數(shù)據(jù)，則在查找表的后半部分繼續(xù)進(jìn)行二分查找，否則在前半部分進(jìn)行二分查找。即先確定目標(biāo)數(shù)據(jù)所在區(qū)域，然后逐步縮小區(qū)域，直到查找成功或失敗為止?！景咐景咐?.10】在給定的10個(gè)數(shù)8，12，35，46，55，67，78，82，90，96的列表中查找數(shù)35。4.3.7 查找【案例【案例4.10】在給定的10個(gè)數(shù)8，

10、12，35，46，55，67，78，82，90，96的列表中查找數(shù)35。4.3.8 排序1冒泡排序冒泡排序?qū)⒋判虻臄?shù)據(jù)依次進(jìn)行相鄰兩個(gè)數(shù)據(jù)的比較，如不符合順序要求（由大到小或由小到大）就立即交換。這樣值大（或?。┑木蜁?huì)像冒氣泡一樣逐步升起。按此方法對數(shù)據(jù)經(jīng)過一輪比較移位后稱為一趟冒泡，第1趟冒泡的效果是將數(shù)據(jù)值最大（或最?。┑脑亟粨Q到了最后的位置，即該數(shù)據(jù)排序的最終位置。n個(gè)數(shù)據(jù)最多需要進(jìn)行n1趟冒泡。4.3.8 排序2選擇排序選擇排序從待排序的n個(gè)數(shù)據(jù)的列表（R1, R2, R3,., Rn）中選出最小的數(shù)（按升序）或最大的數(shù)（按降序），將它與R1交換；然后再從余下的n-1個(gè)數(shù)中選出次小

11、（或次?。┑脑嘏cR2進(jìn)行交換；第i趟排序時(shí)（R1, R2,., Ri-1）已排好序，在當(dāng)前無序的（Ri,., Rn）中再選出最?。ɑ蜃畲螅┑脑兀瑢⑺cRi元素交換，使（R1, R2,., Ri）成為有序。依此類推，經(jīng)過n-1趟排序后，全部數(shù)據(jù)就遞增（或遞減）有序了?！景咐?.12】用選擇排序法將N（N=7）個(gè)無序數(shù)據(jù)（9, 5, 7, 2, 4, 8, 3）其按升序排列。4.3.8 排序3插入排序插入排序把n個(gè)待排序的數(shù)據(jù)分為兩部分：R1，.，Ri1為已排好序的有序表，Ri，Ri+1，.，Rn為未排序的無序表（初始時(shí)，令i=2）。然后，把未排序部分的第1個(gè)數(shù)據(jù)Ri依次與R1，.，Ri-1比

12、較，并插入到有序表的適當(dāng)位置上，使得R1，.，Ri變?yōu)橐粋€(gè)新的有序表，直到未排序表中的數(shù)據(jù)元素全部插入到有序表中?！景咐?.13】用插入排序法將N（N=5）個(gè)無序數(shù)據(jù)（30, 16, 25, 17, 12）其按升序排列。初始數(shù)據(jù) 30 16 25 17 12第 1 步 16 30 25 17 12第 2 步 16 25 30 17 12第 3 步 16 17 25 30 12第 4 步 12 16 17 25 30 1時(shí)間復(fù)雜度時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度（Time Complexity）是指算法執(zhí)行所需要的計(jì)算工作量。 按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：常數(shù)階O(1)，對數(shù)階O(log2

13、n)，線性階O(n)等，線性對數(shù)階O(nlog2n)，平方階O(n2)，立方階O(n3)，.，k次方階O(nk)，指數(shù)階O(2n)。2空間空間復(fù)雜度復(fù)雜度 一個(gè)算法的空間復(fù)雜度（Space Complexity）是指算法運(yùn)行所需的內(nèi)存大小，包括輸入數(shù)據(jù)所占空間、程序本身所占空間以及算法執(zhí)行過程中所需要的輔助空間，其中輔助空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲(chǔ)空間。算法算法是為解決問題采用的方法和步驟，它具有5個(gè)重要特性：有窮性、確定性、輸入、輸出、可行性。算法有三種結(jié)構(gòu)算法有三種結(jié)構(gòu)：順序、選擇（分支）、循環(huán)。順序結(jié)構(gòu)按照順序從上向下依次執(zhí)行算法步驟；選擇結(jié)構(gòu)根據(jù)給定的條件判斷選擇執(zhí)行相應(yīng)的步驟；循環(huán)結(jié)構(gòu)在給定條件成立時(shí)，反復(fù)執(zhí)行某些算法步驟。算法的表示算法的表示有多種方法，常用的有：自然語言、流程圖、偽代碼、程序設(shè)計(jì)語言等。求和求和是對數(shù)相加時(shí)用到的一種基本方法。累乘累乘對一系列數(shù)的求乘積的方法。窮舉法窮舉法是依題目的部分條件確定答案的大致范圍，在此范圍內(nèi)