1、1,算法基本工具,2,2.1 循環(huán)與遞歸,設計算法重復處理大量數(shù)據(jù)的思路：以不變應萬變； 兩種思路：循環(huán)、遞歸。,1 循環(huán)設計要點 例2.1 求完數(shù) 例2.2 打印數(shù)字圖形 例2.3 求級數(shù) 2 遞歸設計思路(運行機制、復雜度分析) 例2.4 累加求和 3 遞歸設計要點 例2.5 hanoi塔 4 非遞歸(循環(huán))/遞歸比較,3,1 循環(huán)設計要點,循環(huán)控制-熟悉； 設計要點： “自頂向下”的設計方法 由具體到抽象設計循環(huán)結構 注意算法的效率,4,1 循環(huán)設計要點-例2.1,例2.1 編算法找出1000以內(nèi)所有完數(shù)。 如：28的因子為1、2、4、7，14，而28=1+2+4+7+14。因此28是“

2、完數(shù)”。編算法找出1000之內(nèi)的所有完數(shù)，并按下面格式輸出其因子：28 its factors are 1，2，4，7，14。,問題分析： 1、這里不是要質(zhì)因數(shù)，所以找到因數(shù)后也無需將其從數(shù)據(jù)中“除掉”。 2、每個因數(shù)只記一次，如8的因數(shù)為1，2，4而不是1，2，2，2，4。(注：本題限定因數(shù)不包括這個數(shù)本身),5,1 循環(huán)設計要點-例2.1,核心算法設計 for(i=0;in;i=i+1) 判斷i是否是完數(shù); if是“完數(shù)”則按規(guī)則輸出; ,自頂向下，逐步求精,判斷i是否是完數(shù) for(j=2;ji;j=j+1) 找i的因子，并累加； if 累加值等于i，則i是完數(shù)；,判斷i是否是完數(shù) s=

3、1； for(j=2;ji;j=j+1) if (i % j=0) s=s+j; if (s=i) i是“完數(shù)”;,判斷是否是完數(shù)的方法是“不變”，被判斷的數(shù)是“萬變”。,6,輸出數(shù)據(jù)的方法是“不變”，被輸出的數(shù)是“萬變”。,1 循環(huán)設計要點-例2.1,考慮到要按格式輸出結果，應該開辟數(shù)組存儲數(shù)據(jù)i的所有因子，并記錄其因子的個數(shù)，因此算法細化如下：,int a100，s=1, k=0; for(j=2;ji;j=j+1) if (i % j=0) s=s+j; ak=j; k=k+1; ,if(s=i) print(s, “its factors are :”,1); for(j=0;jk;j

4、+) print(“,”,ak) ,7,1 循環(huán)設計要點-例2.2,對于不太熟悉的問題，其“不變”不易抽象；,1 6 2 10 7 3 13 11 8 4 15 14 12 9 5 n=5,例2.2 編寫算法：根據(jù)參數(shù)n打印具有下面規(guī)律的圖形，如，當n=4時，圖形如下： 1 5 2 8 6 3 10 9 7 4,8,1 循環(huán)設計要點-例2.2,1 5 2 8 6 3 10 9 7 4,問題分析： 容易發(fā)現(xiàn)圖形中數(shù)據(jù)排列的規(guī)律。,另一種思路 先用一個數(shù)組按此順序存儲數(shù)據(jù)， 再正常輸出；,1 5 2 8 6 3 10 9 7 4,可不可以從1最大數(shù)，通過循環(huán)，直接輸出？,printf是按照從左至右

5、、從上至下的順序；若想直接輸出，只有找出公式，循環(huán)計算得到序列：1-n-5-2-n-8-6-3-n-10-9-7-4.,為數(shù)組賦值，也要用循環(huán)，如何循環(huán)？ 又要回到找規(guī)律公式的路上嗎？,斜著能循環(huán)嗎？讓循環(huán)潑辣一點。,9,1 循環(huán)設計要點-例2.2,用斜行、列描述新的循環(huán)方向。,1 5 2 8 6 3 10 9 7 4,斜1，1a1,1 斜1，2a2,2 斜1，3a3,3 斜1，4a4,4,斜2，1a2,1 斜2，2a3,2 斜2，3a4,3,列號相同； 行號(顯然行號與列號有關) 第1斜行，對應行號1n，行號與列號j同； 第2斜行，對應行號2n，行號比列號j大1； 第3斜行，對應行號3n，行

6、號比列號j大2；,斜3，1a3,1 斜3，2a4,2,斜行i取值(1n) 列j取值(1n+1-i),ai-1+jj,這樣可以描述循環(huán)。但數(shù)組元素的存取還是基于“行列”，能否簡單轉(zhuǎn)換？,關鍵問題：第i斜行、j列的數(shù)據(jù)對應于第幾行第幾列的元素？,斜4，1a4,1,10,1 循環(huán)設計要點-例2.2,main( ) int i,j,a100100,n,k; input(n); k=1; for(i=1;i=n;i=i+1) for( j=1;j=n+1-i;j=j+1) ai-1+jj=k; k=k+1; for(i=1;i=n;i=i+1) print( “換行符”); for( j=1;j=i;j

7、=j+1) print(aij); ,斜行i取值(1n) 列j取值(1n+1-i),1 5 2 8 6 3 10 9 7 4,11,1 循環(huán)設計要點-例2.3,例2.3 求級數(shù) 求：1/1!-1/3!+1/5!-1/7!+(-1)n+1/(2n-1)!,問題分析：此問題中既有累加又有累乘，累加的對象是累乘的結果。數(shù)學模型1：Sn=Sn-1+(-1)n+1/(2n-1)!算法設計1：直接利用題目中累加項通式，構造出循環(huán)體不變式為： S=S+(-1)n+1/(2n-1)!需要用二重循環(huán)來完成算法。,算法設計1： 外層循環(huán)求累加S=S+A; 內(nèi)層循環(huán)求累乘A= (-1)n+1/(2n-1)! 。,1

8、2,1 循環(huán)設計要點-例2.3,算法分析： 以上算法是二重循環(huán)來完成 ，但算法的效率卻太低O(n2)。,數(shù)學模型2：Sn=Sn-1+(-1)n+1An； An=An-1 *1/(2*n-2)*(2*n-1),其原因是，當前一次循環(huán)已求出7！，當這次要想求9！時，沒必要再從1去累乘到9，只需要充分利用前一次的結果，用7！*8*9即可得到9！，模型為An=An-1*1/(2*n-2)*(2*n-1)。,算法分析：按照數(shù)學模型2，只需一重循環(huán)就能解決問題算法的時間復雜性為O(n)。,13,2 遞歸設計思路-例2.4,程序結構化設計的三種基本結構，順序、選擇、循環(huán)是不是必須的？,例2.4根據(jù)參數(shù)n，計

9、算1+2+n。,void sum_loop(int n) int i,sum=0; for (i=1;i=n;i+) sum = sum + i; printf(nsum = %d,sum); ,回答：在很多高級語言中，不是?？梢話仐壵l呢？,遞歸能取代循環(huán)的作用 。,14,2 遞歸設計思路-例2.4,例2.4 根據(jù)參數(shù)n，計算1+2+n。,int sum_recursive(int n) int sum=0; if (n = 1) sum = 1; else sum = sum_recursive(n-1) + n; printf(nsum = %d,sum); return sum; ,su

10、m(n),遞歸算法是一個模塊(函數(shù)、過程)除了可調(diào)用其它模 塊(函數(shù)、過程)外，還可以直接或間接地調(diào)用自身的算法。直接/間接遞歸調(diào)用。,代入n=4，走一遍。,遞歸樹！,15,2 遞歸設計思路-例2.4,例2.4 根據(jù)參數(shù)n，計算1+2+n。,int sum_recursive(int n) int sum=0; if (n = 1) sum = 1; else sum = sum_recursive(n-1) + n; printf(nsum = %d,sum); return sum; ,棧頂 (top),棧底 (bottom),出棧,進棧,棧底元素,棧頂元素,表面上是一個變量，實際上是一個

11、棧,16,2 遞歸設計思路-例2.4,例2.4 根據(jù)參數(shù)n，計算1+2+n。,int sum_recursive(int n) int sum=0; if (n = 1) sum = 1; else sum = sum_recursive(n-1) + n; printf(nsum = %d,sum); return sum; ,T(n) = T(n-1)+O(1),= T(n-2)+O(1)+O(1),= .,= n*O(1)=O(n),17,“收斂”,3 遞歸設計要點,遞歸的關鍵在于找出遞歸方程式和遞歸終止條件。 遞歸定義：使問題向邊界條件轉(zhuǎn)化的規(guī)則。遞歸定義必須能使問題越來越簡單。 遞歸

12、邊界條件：也就是所描述問題的最簡單情況，它本身不再使用遞歸的定義。,int sum_recursive(int n) int sum=0; if (n = 1) sum = 1; else sum = sum_recursive(n-1) + n; printf(nsum = %d,sum); return sum; ,18,例1.1 歐幾里德算法,gcd ( m, n ) = gcd ( n, m mod n ) 輸入 正整數(shù)m和n 輸出 m和n的最大公因子 如果n = 0, 計算停止返回m, m即為結果；否則繼續(xù)2。 記r為m除以n的余數(shù)，即r=m mod n。 把n賦值給m，把r賦值給n

13、，繼續(xù)1。 偽代碼如下(循環(huán))： Euclid(m, n) while n 0 r = m n; m = n; n = r; ,遞歸代碼： GCD(m,n) / 約定mn / if n=0 return(m) else return (GCD(n,m mod n) ,19,GCD(22,8),GCD(8,6),GCD(6,2),GCD(2,0),2,遞推,遞推,遞推,遞推,回歸,回歸,回歸,回歸,結果為GCD(22,8)=2,例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2;,20,3 遞歸設計要點-hanoi塔,Hanoi塔 hanoi河內(nèi)越

14、南首都 古代有一個梵塔，塔內(nèi)有3個基座A、B、C， 開始時A基座上有64個盤子，盤子大小不等，大的在下，小的在上。 有一個老和尚想把這64個盤子從A座移到B座，但每次只允許移動一個盤子，且在移動過程中在3個基座上的盤子都始終保持大盤在下，小盤在上。 在移動過程中可以利用C基座做輔助。 請編程打印出移動過程 。 約定盤子自上而下的編號為1，2，3，n。,21,3 遞歸設計要點-hanoi塔,首先看一下2階漢諾塔問題的解，不難理解以下移動過程： 初始狀態(tài)為 A(1,2) B() C() 第一步后 A(2) B() C(1) 第二步后 A() B(2) C(1) 第三步后 A() B(1,2) C(

15、),用遞歸思路考慮,22,3 遞歸設計要點-hanoi塔,把n個盤子抽象地看作“兩個盤子”，上面“一個”由1n-1號組成，下面“一個”就是n號盤子。移動過程如下： 第一步：先把上面“一個”盤子以a基座為起點借助b基座移到c基座。 第二步：把下面“一個”盤子從a基座移到b基座。 第三步：再把c基座上的n-1盤子借助a基座移到b基座。,遞歸：領導的藝術,23,3 遞歸設計要點-hanoi塔,把n階的漢諾塔問題的模塊記作hanoi(n,a,b,c) a代表每一次移動的起始基座； b代表每一次移動的終點基座； c代表每一次移動的輔助基座 ； 則hanoi(n,a,c,b)，表示把n個盤子從a搬到c，可

16、以借助b； hanoi(5,c,a,b)，表示把5個盤子從c搬到a，可以借助b。,則漢諾塔問題hanoi(n,a,b,c)等價于以下三步： 第一步，hanoi(n-1,a,c,b)； 第二步，把下面“一個”盤子從a基座移到b基座； 第三步， hanoi(n-1,c,b,a)。 至此找出了大規(guī)模問題與小規(guī)模問題的關系。,24,3 遞歸設計要點-hanoi塔,hanoi(n,a,b,c) a：起始基座 b：終點基座 c：輔助基座,hanoi(n,a,b,c),hanoi(n-1,a,c,b),hanoi(n-1,c,b,a),移,hanoi(n-2,a,b,c),hanoi(n-2,b,c,a),

17、移,hanoi(2,.,.,.),hanoi(2,.,.,.),移,hanoi(1,.,.,.),移,hanoi(1,.,.,.),hanoi(0,.,.,.),/,hanoi(0,.,.,.),O(2n),25,3 遞歸設計要點-hanoi塔,hanoi (int n,char a,char b,char c) /* a,b,c 初值為”A”,”B”,”C”*/ if(n0) /*0階的漢諾塔問題當作停止條件*/ hanoi(n-1,a,c,b); 輸出 “ Move dish” ,n.”from pile”,a,” to”b); hanoi(n-1,c,b,a); ,26,4 非遞歸(循環(huán)

18、)/遞歸比較-非遞歸hanoi塔,遞歸思路不適合人類使用：人腦的逆推深度是有限的，而計算機要比人腦深很多，論記憶的準確性，計算機要比人腦強很多。,你用遞歸的程序，用n=10，試試看？,通過分析可以找到非遞歸的思路，而這種思路是未學過遞歸思想的人常用的。,27,4 非遞歸(循環(huán))/遞歸比較-轉(zhuǎn)化,設計算法重復處理大量數(shù)據(jù)的思路：以不變應萬變； 兩種思路：非遞歸(循環(huán))、遞歸。,1、有些問題可以方便的用循環(huán)/遞歸兩種思路處理； 如例2.4 累加求和；,在后面的課程中，會常遇到遞歸算法，以及同一問題的遞歸、非遞歸算法。,2、有些問題用遞歸比較方便；轉(zhuǎn)換成非遞歸過程可通過模擬遞歸過程的執(zhí)行過程來實現(xiàn)；

19、其基本思想是在程序中設置一個棧； 如例2.5 hanoi塔。,同一個問題干嘛要學兩種方法？,28,從算法設計的角度,遞歸函數(shù)調(diào)用引起的棧操作,4 非遞歸(循環(huán))/遞歸比較,并不是每一門語言都支持/很好的支持遞歸； 有助于理解遞歸的本質(zhì)； 有助于理解棧,樹等數(shù)據(jù)結構； 兩者各有利弊：,29,1 數(shù)據(jù)結構的選擇很重要 例2.6 大整數(shù)存儲及運算 2 算法和數(shù)據(jù)結構不分離 例2.7 線性表的實現(xiàn) 3 數(shù)組與指針 例2.7 線性表的實現(xiàn) 一聚，一散 一靜，一動 靜中有動 高級語言的支持,2.2 算法與基本數(shù)據(jù)結構,30,1 數(shù)據(jù)結構的選擇很重要,計算機解決問題是對“數(shù)據(jù)”加工處理。,例2.6 編程求當

20、N=100時，N！的準確值。,問題分析： 例如： 9！=362880 100！ = 93 326215 443944 152681 699263 856266 700490 715968 264381 621468 592963 895217 599993 229915 608914 463976 156578 286253 697920 827223 758251 185210 916864 000000 000000 000000 000000,處理對象的情況嚴重影響處理過程、效果。,數(shù)值問題/非數(shù)值問題。,31,1 DS選擇-例2.6-問題分析,計算機存儲數(shù)據(jù)是按類型分配空間的。在PC上

21、： 整型：2個字節(jié)16位，則整型數(shù)據(jù)的范圍為-3276832767； 長整型：4個字節(jié)32位，則長整型數(shù)據(jù)的范圍為 -21474836482147483647； 實型：4個字節(jié)32位，但非精確存儲數(shù)據(jù)，只有六位精度，數(shù)據(jù)的范圍(3.4e-383.4e+38) ； 雙精度型：8個字節(jié)64位的存儲空間，數(shù)據(jù)的范圍(1.7e-3081.7e+308)，其精確位數(shù)是17位。,這些類型無法存儲100！這樣的“大整數(shù)”。,需要使用更復雜、更有針對性的數(shù)據(jù)結構。,32,1 DS選擇-例2.6-算法設計,每一位數(shù)，都是一個10以內(nèi)數(shù)字。多個，相同屬性的，,數(shù)組是有頭有尾的：a1an。高位、低位誰頭誰尾？,低位

22、固定，而高位不定。最低位為a1，且在高端要為問題最大存儲數(shù)據(jù)留夠空位。,基于存儲的考慮,int an,33,1 DS選擇-例2.6-算法設計,100！=1*2*3*99*100。 按此方法計算，最困難的操作是： 大整數(shù)*乘數(shù)，其中乘數(shù)=100。,基于功能的考慮,原來一個元素存一位，現(xiàn)在是否要改變？改變是否有用？,問題出在哪里？,當?shù)臀辉赜嬎愫蟮闹党^9時，需向高位元素進位。,如何進位？,34,1 DS選擇-例2.6-算法設計,int an中的數(shù)組元素可以存放更大的數(shù)。如，每個存3位。,基于性能的考慮,進位4次。,進位幾次？,進位需要特殊的處理；減少進位的處理，可以提高效率。,每個元素處理的位

23、數(shù)越多，進位次數(shù)越少。,在前面提到的四種數(shù)據(jù)類型的基礎上，粗略估計一下，本問題中，每個元素最多可以存儲幾位數(shù)據(jù)？,35,1 DS選擇-例2.6-算法實現(xiàn),main( ) long ab256,b,d; int m,n,i,j,r; input(n); m=log(n)*n/6+2; ab1=1; for( i=2; i=m;i+) abi=0; d=0; for( i=2; i=n;i+) for (j=1;j=m;j+) b=abj*i+d; abj=b%1000000; d=b/1000000;,for (i=m ;i=1;i-) if( abi=0) continue; else r=i

24、; break; print(n,“!=”); print(abr); for(i=r-1;i=1;i-) if (abi99999) print(abi); continue; if (abi9999) print( “0”,abi); continue; if (abi 999) print( “00”,abi); continue; if (abi99 ) print( “000”,abi); continue; if (abi9) print( “0000”,abi); continue; print( “00000”,abi); /for ,36,1 數(shù)據(jù)結構的選擇很重要-總結,基于

25、存儲的考慮 基于功能的考慮 基于性能的考慮,37,2算法和數(shù)據(jù)結構不分離,例2.6僅有一個main()函數(shù)。這樣寫的代碼僅能用于階乘的精確結果。如果有其他大整數(shù)的計算，需要重新設計？,怎樣寫出來的程序可以具有更強的通用性？,理想的情況：設計出大整數(shù)的數(shù)據(jù)結構，并且也提供該數(shù)據(jù)結構的元素操作。,數(shù)據(jù)結構課程中的各種ADT,程序 = (數(shù)據(jù)結構) + (算法),兩者看似糾纏，實則無親密關系：再寫類似代碼要重新設計數(shù)據(jù)結構。,38,2 算法和數(shù)據(jù)結構不分離-C 線性表,#define LIST_INIT_SIZE 100/ 線性表存儲空間的初始分配量 #define LISTINCREMENT 10

26、 / 線性表存儲空間的分配增量 typedef struct ElemType *elem; / 指針，指示線性表的基地址 int length; / 當前長度 int listsize; / 當前分配的存儲容量(以sizeof(ElemType)為單位) SqList;,InitList ( private Node Tail=null; private Node Pointer=null; private int Length=0; public void deleteAll() /清空整個鏈表/ public void reset() /鏈表復位/ public boolean isEm

27、pty() /判斷鏈表是否為空/ public boolean isEnd() /判斷當前結點是否為最后一個結點/ public Object nextNode() /返回當前結點的下一個結點的值，并使其成為當前結點/ ,對象/類 = (數(shù)據(jù)結構 + 算法),程序 = 對象+對象+.+對象,二者合一,張白一ch8,程序是許多對象相繼表現(xiàn)自己。,40,2 算法和數(shù)據(jù)結構不分離-總結,程序 = (數(shù)據(jù)結構) + (算法),程序 = (數(shù)據(jù)結構 + 算法),對象/類 = (數(shù)據(jù)結構 + 算法),程序 = 對象+對象+.+對象,不適應大規(guī)模軟件開發(fā),結構化開發(fā)尚存一息,OO開發(fā)已普及， 向更高要求發(fā)展

28、中,本課程中的算法實現(xiàn)風格：以簡單明了、體現(xiàn)算法思想為原則。,41,3 數(shù)組與指針,一聚，一散 一動，一靜 靜中有動 高級語言的支持,數(shù)組和指針在程序設計、數(shù)據(jù)結構中占重要角色。 在基礎類型上的擴展； 構成復雜數(shù)據(jù)類型的基礎和重要方式。,數(shù)據(jù)的邏輯結構常分為四大類： 集合結構 線性結構 樹形結構 圖結構（網(wǎng)結構）,數(shù)組和指針均可實現(xiàn),42,3 數(shù)組與指針一聚，一散,連續(xù)存儲 可隨機存取(通過數(shù)組名、下標便可以訪問) ；,鏈式存儲 在內(nèi)存中方便利用碎片存儲。,例2.7 線性表的實現(xiàn),無需多余存儲單元，空間效率高。,43,3數(shù)組與指針一動，一靜,例2.7 線性表的實現(xiàn),連續(xù)存儲 數(shù)組的空間在分配后相對固定；,鏈式存儲 可以方