《習(xí)題課1》ppt課件

《《習(xí)題課1》ppt課件》由會員分享，可在線閱讀，更多相關(guān)《《習(xí)題課1》ppt課件（20頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、習(xí)題課1 第一章 算法及基礎(chǔ)知識1-6 請對冒泡排序算法進(jìn)行描述，并對其復(fù)雜性進(jìn)行分析。算法描述：Void BubbleSort(int score ) int i,j,temp; for(i=0;i=n-2;i+) for(j=0;jscorej+1) temp=scorej; scorej=scorej+1; scorej+1=temp; 該算法的時(shí)間復(fù)雜性為O(n 2),算法為穩(wěn)定的排序方法。 1-7 給出求解漢諾塔問題的算法描述，并對其復(fù)雜性進(jìn)行分析。 Hanoi Tower問題是印度的一個(gè)古老的傳說。開天辟地的神勃拉瑪在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大

2、的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面。計(jì)算結(jié)果非?？植?移動(dòng)圓片的次數(shù))18446744073709551615，眾僧們即便是耗盡畢生精力也不可能完成金片的移動(dòng)了。 1-7 給出求解漢諾塔問題的算法描述，并對其復(fù)雜性進(jìn)行分析。算法思想： 將n個(gè)盤子從A座移動(dòng)到C座上可以分解為三個(gè)步驟： （1）將A座上的n-1個(gè)盤子移動(dòng)到座上（借助C座）（2）將A座上剩下的一個(gè)盤子移動(dòng)到C座上。（3）將n-1個(gè)盤子從B座移動(dòng)到C座上（借助A座）Void hanio(int n,

3、 char a, char b, char c) if(n=1) move(a,c) else hanio(n-1,a,c,b); move(a,c);hanio(n-1,b,a,c); void move(char x, int n, char y) /漢諾塔的遞歸算法 cout 把編號為 n 的盤從 x 移到 y endl; void hanoi(int N, char A, char C, char B) if(N = 1) move(A, 1, B); else hanoi(N-1, A, B, C); move(A, N, B); hanoi(N-1, C, A ,B); int m

4、ain() cout -漢諾塔遞歸實(shí)現(xiàn)-n endl; cout 說明：利用C塔將盤子從A塔移到B塔n endl; cout n; cout 移動(dòng)步驟： endl; hanoi(n, A, C, B); system(PAUSE); return 0; 該算法的時(shí)間復(fù)雜性為O(2n) using namespace std; static void hanoi(int n) /漢諾塔的非遞歸算法 int fromPole, toPole, Disk; int *BitStr = new intn,*Hold = new intn; char Place = A, B, C; int i, j,

5、 temp; for(i=0; i n; i+) BitStri = 0; Holdi = 1; temp = 3 - (n % 2); int TotalMoves = (1 n) - 1; for (i=1; i = TotalMoves; i+) for (j=0 ; BitStrj != 0; j+) BitStrj = 0; BitStrj = 1; Disk = j+1; if (Disk = 1) fromPole = Hold0; toPole = 6 - fromPole - temp; temp = fromPole; else fromPole = HoldDisk-1;

6、 toPole = 6 - Hold0 - HoldDisk-1; cout 把編號為 Disk 的盤子從 PlacefromPole-1 移到 PlacetoPole-1 endl; HoldDisk-1 = toPole; int main() cout -漢諾塔非遞歸實(shí)現(xiàn)-: n endl 說明：利用塔C將盤子從塔A移到塔Bn endl; cout n; hanoi(n); system(PAUSE); return 0; 該算法的時(shí)間復(fù)雜性為O(n) 第二章 貪心法2-4 給定n位正整數(shù)a，去掉其中任意k(kb1 可知有：ab 2. n=2時(shí)，設(shè)有a=a2a1和b=b2b1, 當(dāng)a2=

7、b2,a1b1 ，可知有：ab 當(dāng)a2b2，可知有：ab 3. n=k時(shí)，設(shè)有a=aka1和b=bkb1 當(dāng)a k=bk,ak-1bk-1 ，可知有：ab 當(dāng)akbk，可知有：ab 算法思想：1.當(dāng)anan-1an-1a1時(shí)，刪除從anan-k+1的k個(gè)數(shù)字。3.當(dāng)anan-1a1序列，包含aiai-1時(shí)， 從最高位向低位掃描，碰見aiai-1，則刪除ai-1; 重復(fù)步驟，k次，刪除k個(gè)數(shù)字。 #include char min(string str, int* pos) char min = str0; *pos = 0; for(unsigned int i=1; i str.length

8、(); i+) if(stri min) min = stri; *pos = i; return min; int main() cout -刪除數(shù)問題- endl; cout 之貪心算法解決n endl; string number; unsigned int delNumber; cout number; cout delNumber; if(delNumber = number.length() cout 輸入的數(shù)字太大 0) temp = number.substr(0, number.length()-digit+1); ch = min(temp, result += ch; n

9、umber = number.substr(pos+1, number.length()-pos-1); digit-; cout n刪除 delNumber 位數(shù)字后得到的最小整數(shù)為： result endl; system(PAUSE); return 0 ; 2-5數(shù)列極差問題。在黑板上寫了N(N2000)個(gè)正數(shù)組成的一個(gè)數(shù)列，進(jìn)行如下操作：每一次擦去其中兩個(gè)數(shù)(設(shè)為a和b)，然后在數(shù)列中加入一個(gè)數(shù)a*b+1，如此下去，直至黑板上只剩下一個(gè)數(shù)。在所有按這種操作方式后得到的數(shù)中，最大的記為max，最小的記為min，則該數(shù)列的極差M=max-min。設(shè)計(jì)一個(gè)有效算法計(jì)算極差M。并說明算法的正

10、確性。 分析：舉例：設(shè)N=2，N個(gè)正數(shù)組成的數(shù)列為：7 ，6計(jì)算只有一種情況：7*6+1=43，max=min=43設(shè)N=3，N個(gè)正數(shù)組成的數(shù)列為：5，7 ，6計(jì)算有三種情況： （5,7,6）=217，（5,6,7）=218，（7,6,5）=216max=218,min=216, M=218-216=2 設(shè)N=4，N個(gè)正數(shù)組成的數(shù)列為：5，7 ，4，6計(jì)算有？種情況：4個(gè)數(shù)相乘有6中情況： （5,7）（4,6），（6,4）（5,4）（7,6），（6,7）（5,6）（7,4），（4,7）3個(gè)數(shù)相乘有2中情況：4,6，（57），4，（57），6 18* 222324 ccc最大值出自：（4,5）,

11、6,7 6,7,（4,5） 最小值出自：7,6,5,4 （7,6）,5,4 第四章 貪心算法算法描述：public class max_min static void sort1(int n,int a)int t;for(int i=0;in-1 ;i+)for(int j=i;jaj) t=ai;ai=aj;aj=t; static void sort2(int n,int b) int t; for(int i=0;in-1 ;i+) for(int j=i;jn ;j+) if(bi1;i-)sort1(i,a);a0=a0*a1+1;a1=a2;a2=a3;System.out.pr

12、intln(a0,a1,a2,a3=+a0+,+a1+,+a2+,+a3);max=a0;System.out.println(max=+max);for(int i=n;i1;i-)sort2(i,b);b0=b0*b1+1;b1=b2;b2=b3;System.out.println(b0,b1,b2,b3=+b0+,+b1+,+b2+,+b3);min=b0;System.out.println(min=+min);max=max-min;System.out.println(極差=+max); 第四章 貪心算法1、最有子結(jié)構(gòu)性質(zhì)： 從上面的分析可知，問題的最優(yōu)解來自子問題的最優(yōu)解。故該

13、問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2、貪心選擇性質(zhì)： （用數(shù)學(xué)歸納法證明） 當(dāng)n=3時(shí)，已排序數(shù)列為：x1x2x3 max=(x1*x2+1)*x3+1=x1*x2*x3+x3+1; min=(x 2*x3+1)*x1+1=x1*x2*x3+x1+1; mid=(x1*x3+1)*x2+1=x1*x2*x3+x2+1; 第四章 貪心算法因?yàn)椋簒1x2x3所以：minmidmax 極差M=max-min當(dāng)n=k時(shí)，有x1x2xk 反復(fù)執(zhí)行三個(gè)數(shù)的情況，max=x1*x2*xk+xk+1;min=x1*x2*xk+x1+1;極差M=max-min 第三章 分治法3-9 應(yīng)用分治法完成下面的整數(shù)乘法計(jì)算：23

14、48*3825 1、將兩個(gè)四位數(shù)乘法轉(zhuǎn)換成4個(gè)兩位數(shù)乘法； 2、將兩個(gè)兩位數(shù)乘法轉(zhuǎn)換成4個(gè)一位數(shù)乘法。 3-10 在一個(gè)由元素組成的表中，出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。試寫一個(gè)尋找眾數(shù)的算法，并分析其計(jì)算復(fù)雜性。解：1. 選取一個(gè)基準(zhǔn)元素； 2. 按基準(zhǔn)元素將表中的元素一分為二，左邊小于基準(zhǔn)元素，右邊大于基準(zhǔn)元素，并統(tǒng)計(jì)等于基準(zhǔn)元素的個(gè)數(shù)，記在si中，基準(zhǔn)元素記在k中。 3. 如果左邊的元素個(gè)數(shù)小于基準(zhǔn)元素的個(gè)數(shù)，右邊的元素個(gè)數(shù)也小于基準(zhǔn)元素的個(gè)數(shù)，則該基準(zhǔn)元素為眾數(shù)，程序結(jié)束。 4. 如果左邊的元素個(gè)數(shù)大于基準(zhǔn)元素的個(gè)數(shù)，則執(zhí)行1-3步，并將新的基準(zhǔn)元素個(gè)數(shù)，與前一個(gè)基準(zhǔn)元素個(gè)數(shù)進(jìn)行比較，si

15、保存較大者，k保存該基準(zhǔn)元素。 5.如果右邊的元素個(gè)數(shù)大于基準(zhǔn)元素的個(gè)數(shù)，則執(zhí)行1-3步，并將新的基準(zhǔn)元素個(gè)數(shù)，與前一個(gè)基準(zhǔn)元素個(gè)數(shù)進(jìn)行比較，si保存較大者，k保存該基準(zhǔn)元素。 4-4 在一個(gè)圓形操場的四周擺放著n堆石子?，F(xiàn)要將石子有次序的合并成一堆。規(guī)定每次只能選相鄰的兩堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分，試設(shè)計(jì)一個(gè)算法計(jì)算出將n堆石子合并成一堆的最小得分和最大得分。 答案見p297第四章 動(dòng)態(tài)規(guī)劃 4-6旅行商問題是指旅行n個(gè)城市，要求各個(gè)城市經(jīng)歷且經(jīng)歷一次，最后回到出發(fā)城市，并求所走的最短路徑。該問題可用無向帶權(quán)圖G=(V，E)來表示，圖中各個(gè)頂點(diǎn)表示城市，城市間的距離用帶權(quán)矩陣C來表示，如果兩個(gè)城市沒有邊相連，則C i j =。 給定帶權(quán)矩陣為： 要求設(shè)計(jì)一個(gè)算法來求出該實(shí)例的最短路徑及其長度。 答案見P298