C語言-遞推遞歸.ppt

1、2020/8/15,1,第二講,基礎(chǔ)算法,計(jì)算機(jī)科學(xué)與技術(shù) 陳葉芳,2020/8/15,2,目錄,遞推 遞歸 排序與檢索,2020/8/15,3,遞推,指一個(gè)序列u1,u2,u3,un-1,un，后面的每一項(xiàng)都能按公式由前面的一項(xiàng)或連續(xù)的幾項(xiàng)推算出來，或者前面的每一項(xiàng)都能按公式由后面的一項(xiàng)或連續(xù)的幾項(xiàng)推算出來。前者叫“順推”，后者叫“逆推”。,遞推關(guān)系可用它前面1項(xiàng)表示的叫一階遞推數(shù)列，可用它前面2項(xiàng)表示的叫二階遞推數(shù)列。,2020/8/15,4,有5人坐在一起，當(dāng)問第5個(gè)人多少歲,他說比第4個(gè)人大2歲，問第4個(gè)人多少歲,他說比第3個(gè)人大2歲，依此下去，問第一個(gè)人多少歲，他說他10歲，最后求第

2、5個(gè)人多少歲？,如果所坐的不是5人而是n人，寫出第n個(gè)人的年齡表達(dá)式。,遞推,x,x+2,2020/8/15,5,顯然可以得到如下公式:,化簡(jiǎn)后的公式: F(n)=10+(n-1)*2,2020/8/15,6,斐波那契級(jí)數(shù)-遞推的經(jīng)典問題,一對(duì)新生小兔，一個(gè)月后長(zhǎng)成中兔，從第三個(gè)月開始長(zhǎng)成大兔并每個(gè)月生一對(duì)小兔。按此規(guī)律，一年后共有多少對(duì)兔子。,2020/8/15,7,Fibnacci 數(shù)列,即：1、1、2、3、5、8、13、21、34,關(guān)鍵：確定問題的遞歸特性,關(guān)鍵：分析出遞歸公式,關(guān)鍵：分析出初始條件,2020/8/15,8,例-巧妙推算走樓梯,樓梯有n級(jí)臺(tái)階，如果一步走1級(jí)或2級(jí)，試問：

3、共有多少種不同的走法？,1,2,3,n,走上第1級(jí)臺(tái)階，只有“一步1級(jí)”1種走法，u1=1；,走上第2級(jí)臺(tái)階，從平地起步，有“一步1級(jí)”走2步和“一步2級(jí)”走1步這兩種走法，u2=2；,走上第3級(jí)臺(tái)階，或者從臺(tái)階2“一步1級(jí)”走1步上來，或者從臺(tái)階1“一步2級(jí)”走1步上來，u3=u2+u1=2+1=3；,走上第n級(jí)臺(tái)階，只能從第n-1級(jí)“一步1級(jí)”走1步上來，或者從第n-2級(jí)臺(tái)階“一步2級(jí)”走1步上來，un=un-1+un-2 (n2)；,2020/8/15,9,例-巧妙推算走樓梯,1,2,3,n,初始條件：u1=1；u2=2;,1、2、3、5、8、13、21、34、55,斐波那契序列,202

4、0/8/15,10,總結(jié)：遞推求解的基本方法：,首先，確認(rèn)：能否容易的得到簡(jiǎn)單情況的解？,然后，假設(shè)：規(guī)模為N-1的情況已經(jīng)得到解決。,最后，重點(diǎn)分析：當(dāng)規(guī)模擴(kuò)大到N時(shí)，如何枚舉出所有的情況，并且要確保對(duì)于每一種子情況都能用已經(jīng)得到的數(shù)據(jù)解決。,2020/8/15,11,在2n的長(zhǎng)方形方格中,用n個(gè)12的骨牌鋪滿方格, 例如n=3時(shí),為23方格，骨牌的鋪放方案有三種(如圖), 輸入n ,輸出鋪放方案的總數(shù),思考題（NBU OJ 1196）：,2020/8/15,12,骨牌鋪放,1、如果用一個(gè)骨牌直接覆蓋最左邊一列，則剩下的2(n-1)個(gè)方格有f(n-1)種鋪法；,2、如果用兩個(gè)骨牌橫向覆蓋，則

5、剩下的2(n-2)個(gè)方格有f(n-2)種鋪法；,2(n-1),2(n-2),3、第1列沒有其他鋪法，因此，f(n)=f(n-1)+f(n-2)；,2020/8/15,13,某人給不同地址不同姓名的n位朋友寫信，信箋、信封都分別寫好了。請(qǐng)問：所有信箋、信封全都裝錯(cuò)的情況有多少種？,伯努利裝錯(cuò)信封問題,信封：A B C D E F 信箋：a b c d e f ,伯努利問題：求n個(gè)元素的排列，要求在排列中沒有一個(gè)元素處于它應(yīng)當(dāng)占有的位置。,2020/8/15,14,伯努利裝錯(cuò)信封問題,信封：A B C D E F 信箋：a b c d e f ,錯(cuò)誤1： 信封：A B C D E F 信箋：b a

6、 (后n-2封也都裝錯(cuò)),錯(cuò)誤2： 信封：A B C D E F 信箋：b 非a (后n-2封也都裝錯(cuò)),裝錯(cuò)情況種數(shù)Sn-2,裝錯(cuò)情況種數(shù)Sn-1,Sn= （n-1)(Sn-1+ Sn-2),2020/8/15,15,分析思路：,S1=0, 只1封信，不會(huì)裝錯(cuò),S4=3(S3+S2)=9,S3=2(S2+S1)=2, 3封信，a-B,b-C,c-A或a-C,c-B,b-A,S2=1, 2封信，互相裝錯(cuò),2020/8/15,16,得到如下遞推公式：,基本形式：d1=0; d2=1遞歸式：dn= (n-1)*( dn-1 + dn-2),這就是著名的錯(cuò)排公式,2020/8/15,17,遞歸,in

7、t fact(int n) /*遞歸函數(shù)*/ int r; if(n=0) r=1; else r=n*fact(n-1); /*遞歸*/ return r; ,printf(%d!=%dn,5,fact(5);,2020/8/15,18,遞歸,fact(5) =5*fact(4),院長(zhǎng),設(shè)計(jì)遞歸程序的重點(diǎn)是給下級(jí)安排工作,2020/8/15,19,遞歸,int SearchBin(int *r,int k,int low,int high) /遞歸 if(rowhigh) return 0; /failed mid=(low+high)/2; if(k=rmid) return mid; /

8、success else if(krmid) return SearchBin(*r,k,mid+1,high); else return SearchBin(*r,k,low,mid-1); ,2020/8/15,20,遞歸,int func(int n) /*求斐波那契數(shù)列的第n個(gè)數(shù)*/ int result; if(n=1) result=1; else if(n=2) result=1; else result=func(n-1)+func(n-2); /*遞歸*/ return result; ,2020/8/15,21,遞歸,Hanoi（漢諾塔）問題：三根柱子A、B、C，其中A柱上

9、有64個(gè)大小不等的圓盤，并且大的在下，小的在上。要求把這64個(gè)圓盤從A柱移動(dòng)到C柱上，每次只能移動(dòng)一個(gè)圓盤，移動(dòng)時(shí)可以借助B來進(jìn)行，但在任何時(shí)候，任何柱上的圓盤都必須保持大盤在下，小盤在上。求移動(dòng)的過程。,A,B,C,2020/8/15,22,遞歸,(1)假如只有一個(gè)盤子的話，可以直接將盤子從A柱移動(dòng)到C柱，即AC。,A,B,C,2020/8/15,23,遞歸,(2)假如有兩個(gè)盤子，則： AB AC BC,A,B,C,2020/8/15,24,遞歸,(3)假如有三個(gè)盤子，則情況開始復(fù)雜，移動(dòng)順序?yàn)椋?AC AB CB AC BA BC AC,A,B,C,2020/8/15,25,遞歸,當(dāng)有n個(gè)

10、盤子需要移動(dòng)時(shí)，通常的方法如下： （1）把A柱上n-1個(gè)盤子借助C柱移動(dòng)到B柱上。只有這樣，C柱才能為空，則A柱上的第n個(gè)盤子（最大的那個(gè)）才能直接移動(dòng)到C柱上。 （2）將A柱上的剩下的第n個(gè)盤子移動(dòng)到C柱上。這個(gè)盤子已最后到位，不需要再移動(dòng)了。 （3）再將B柱上的n-1個(gè)盤子借助A柱移動(dòng)到C柱。,A,B,C,2020/8/15,26,遞歸,void hanoi(int n,char A,char B,char C) /*借助B，把n個(gè)盤子從A移動(dòng)到C*/ if(n=1) move(A,C); else hanoi(n-1,A,C,B); /*借助C，把n-1個(gè)盤子從A移動(dòng)到B*/ move(

11、A,C); /*把第n個(gè)盤子從A移動(dòng)到C*/ hanoi(n-1,B,A,C); /*借助A，再把n-1個(gè)盤子從B移動(dòng)到C*/ ,A,B,C,scanf(%d,2020/8/15,27,排序與檢索,查找表:用于查找的數(shù)據(jù)集合,由同一類型數(shù)據(jù)元素構(gòu)成.,2020/8/15,28,排序與查找,A B C Z,banana Basketball ,列表：同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合?？衫萌魏螖?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。 關(guān)鍵字 ：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值。 查找：根據(jù)給定的關(guān)鍵字，在特定列表中確定與與之相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。,2020/8/15,29,順序查找法,int se

12、qListn+1; /n號(hào)單元用作監(jiān)視哨 int Order_Search(int array ,int n,int key) int i; arrayn=key; /設(shè)置監(jiān)視哨，不用判斷越界 for(i=0;arrayi!=key;i+) ; return (in?i:-1); /找不到為-1,找到則為0n-1的數(shù)值 ,1.每一步驟中省去了對(duì)是否越界的判斷，如i1000時(shí),可以節(jié)省一半以上的查找時(shí)間.,特點(diǎn)：用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗為止。,特點(diǎn)：從前到后，或從后到前。,for(i=0;in;i+) if(arrayi=key) return i; retu

13、rn -1;,2020/8/15,30,順序查找法,int seqListn+1; /0號(hào)單元用作監(jiān)視哨 int Order_Search(int *array,int n,int key) r0=key; /設(shè)置監(jiān)視哨，不用判斷越界 for(i=n;arrayi!=key;i-) ; return i; /找不到為0,找到則為1n的數(shù)值 ,2020/8/15,31,折半查找法(二分查找）,A在心里想一個(gè)不超過1000的正整數(shù), 由B來猜,請(qǐng)問可以在多少次以內(nèi)猜到該數(shù)?,特點(diǎn)：利用元素間的次序關(guān)系（要求數(shù)據(jù)集合有序）。采用了分治策略。,2020/8/15,32,折半查找法,3 10 15 19

14、 25 28 40 55 83,low,high,mid,要求:查找關(guān)鍵字為55的數(shù)據(jù)元素 (1) mid=(low+high)/2 (2)55rmid,則查找mid+1,high區(qū)間,既low=mid+1,mid=(low+high)/2,3 10 15 19 25 28 40 55 83,low,high,mid,二分查找(Binary Search),要求：要查找的列表是按關(guān)鍵字大小有序排列的。,2020/8/15,33,折半查找法,3 10 15 19 25 28 40 55 83,low,high,mid,要求:查找關(guān)鍵字為18的數(shù)據(jù)元素 (1) mid=(low+high)/2 (

15、2)18rmid,則查找low,mid-1區(qū)間,既high=mid-1,mid=(low+high)/2,3 10 15 19 25 28 40 55 83,low,high,mid,若出現(xiàn)lowhigh情況,則查找失敗,2020/8/15,34,折半查找法,int SearchBin(int *r,int k) low=1;high=n; while(lowrmid) low=mid+1; else high=mid-1; return 0; /failed ,2020/8/15,35,折半查找法,int SearchBin(int *r,int k,int low,int high) /遞

16、歸 if(rowhigh) return 0; /failed mid=(low+high)/2; if(k=rmid) return mid; /success else if(krmid) return SearchBin(*r,k,mid+1,high); else return SearchBin(*r,k,low,mid-1); ,2020/8/15,36,插入排序,在一個(gè)已經(jīng)排好序的記錄子集的基礎(chǔ)上,每一步將下一個(gè)待排序的記錄有序地插入到排好序的記錄子集中.（撲克牌的抓牌操作） 直接插入排序 折半插入排序 希爾排序,2020/8/15,37,直接插入排序,初始序列：51 33 62

17、 96 87 17 28 51 區(qū)別相同關(guān)鍵字，內(nèi)為有序序列 i=2(33) 33 51 62 96 87 17 28 51 i=3(62) 33 51 62 96 87 17 28 51 i=4(96) 33 51 62 96 87 17 28 51 i=5(87) 33 51 62 87 96 17 28 51 i=6(17) 17 33 51 62 87 96 28 51 i=7(28) 17 28 33 51 62 87 96 51 i=8(51) 17 28 33 51 51 62 87 96,2020/8/15,38,直接插入排序,void StrInsSort(int r,int

18、 n) for(i=2;i=n;i+) /假定第一個(gè)記錄有序 r0=ri; j=i-1; /將待排序記錄放入監(jiān)視哨r0 /從后向前查找插入位置，同時(shí)將已排序記錄向后移動(dòng) while(r0rj) /查找與移動(dòng)在同一循環(huán)中 rj+1=rj; j-; /記錄后移 rj+1=r0; /待排記錄放到合適位置 ,主要耗費(fèi)時(shí)間在關(guān)鍵字比較和移動(dòng)元素上,33,51,33,51,33,62,62,2020/8/15,39,折半插入排序,void BinsSort(RecType r,int n) for(i=2;i=low; j-) rj+1=rj; /記錄后移 rlow=r0; /插入 ,2020/8/15,40,交換類排序,交換類排序:通過交換逆序元素進(jìn)行排序. 冒泡排序 快速排序,2020/8/15,41,冒泡排序,冒泡排序(Bubble Sort):從頭掃描