1、 / 5算法設(shè)計、填空題1、衡量算法的兩個指標(biāo)：時間復(fù)雜度、空間復(fù)雜度 。2、回溯算法的基本思想：按照深度優(yōu)先的策略,從根節(jié)點出發(fā)搜索解空間樹。3、動態(tài)規(guī)劃算法適合解決的問題： 最優(yōu)化問題。4、分治算法的典型應(yīng)用：二分法。5、時間復(fù)雜度T (n)中。的定義；判斷時間復(fù)雜度等價于什么？定義：用來表示解決問題算法所需的時間總量f (n)的上界。是數(shù)量級的符號，用來表示時間復(fù)雜度。6、分支限界法的基本思想：以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹。7、貪婪算法適合解決什么問題：局部最優(yōu)化問題。8、遞歸算法的定義：定義：一歸是一個過程或函數(shù)在其定義或說明中又直接或間接調(diào)用自身的方法。算法定義：就是

2、把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題想死的規(guī)模較小的問 題，在逐步求解小問題后，再返回(回溯)得到大問題的解。、選擇題1、算法時間復(fù)雜度密集度高低判斷？O O (log2n) O (n) O (nAt) O (t?)O(n!)2、最大效益優(yōu)先是哪種算法的首選方式？分支限界法。3、P、NP類問題及關(guān)系？存在多項式時間的算法的一類問題為P類問題，沒有找到多項式時間的算法的一類問題為NP類問題。NP類中的所有問題都是 P類。4、設(shè)計循環(huán)賽日程表采用什么算法？二分策略遞歸算法、二分策略非遞歸算法、利用數(shù)據(jù)間的規(guī)律構(gòu)造算法、二維遞推算法。5、動態(tài)規(guī)劃的步驟有：劃分階段、選擇狀態(tài)、確定決策并寫出狀態(tài)

3、轉(zhuǎn)移方程。6、貪婪算法的基本要素：最優(yōu)子結(jié)構(gòu)設(shè)計、貪婪選擇性質(zhì)。7、分治算法解決問題必須滿足的條件：1)能將這幾個數(shù)據(jù)分解成 k個不同子集合，且得到 k個子集合是可以獨(dú)立求解的子問 題，其中1k=32)上樓梯問題為什么適合用斐波那契數(shù)列求解？上樓梯問題通過反向思考，到第n 階有兩種情況：從第 n-1 階到第 n 階；從第 n-2 階到第 n 階。記 n 階臺階的走法數(shù)為 f(n), 則 f(n)=1 n=1;2n=2;f(n-1)+f(n-2)n2反向分析法和遞歸設(shè)計一樣， 就是找出大規(guī)模問題與小規(guī)模問題之間的關(guān)系， 而這個關(guān)系正好符合斐波那契數(shù)列的規(guī)律。4、寫出算法設(shè)計思路并分析。( 1)遞

4、歸(漢諾塔問題)設(shè)計思路：找出大規(guī)模問題與小規(guī)模問題的遞歸關(guān)系。1)將A基座上面的n-1個盤子借助B基座移到C基座上。2)將A 基座剩余的一個n 號盤子移到 B 基座上。3)將C基座的n-1個盤子借助A基座移到B基座上。分析： 遞歸算法執(zhí)行中有遞歸調(diào)用的過程和回溯的過程， 遞歸法就是通過調(diào)用把問題從大規(guī)模歸結(jié)到小規(guī)模，當(dāng)小規(guī)模得到解決后又把小規(guī)模的結(jié)果回溯，從而退出大規(guī)模的解。( 2)上樓梯問題設(shè)計思路：通過反向分析法考慮到第n 階有兩種情況：從第n-1 階到第 n 階；從第 n-2階到第 n 階。記 n 階臺階的走法數(shù)為 f(n), 則 f(n)=1 n=1;2n=2;f(n-1)+f(n-

5、2)n2分析：反向分析法和遞歸設(shè)計一樣，就是找出大規(guī)模問題與小規(guī)模問題之間的關(guān)系。5、分析某一個程序的執(zhí)行結(jié)果包括執(zhí)行過程(test() )執(zhí)行結(jié)果：當(dāng) n=3 時： 32100123執(zhí)行過程： test (int n)print n;if( n0)test(n-1) ;elseprint“ ;print n四、證明題1、證明時間復(fù)雜度的線性/ 非線性。假設(shè)n=2，有迭代方程 T(n)=2T(n/2)+2,計算O (n)。T(n)=2T(n/2)+2=2(T(n/2A2)+2)+2=4+n/2A2+4+2=4(2T(n/2A3)+2)+4+2所以：O(n)=2A(k-1)+(2Ak-2)=3/

6、2*2Ak-2=(3/2)n-2,所以此時間復(fù)雜度為線性級。11)n=22、遞歸調(diào)用的迭代方程(原式 =1+11+111+11-不變式： Sn=0n=0;=1n=1;(Sn-1-Sn-2)*10+1+Sn-1=11Sn-1-10Sn-2+1#includestdio.hint main()int f(int n),n;printf( 請輸入 n:);scanf(%d,&n);printf(%d,f(n);int f(int n)if(n=1)return 1;else if(n=0)return 0;elsereturn f(n-1)+(f(n-1)-f(n-2)*10+1);3、證明數(shù)列稽查

7、適合用貪婪算法求解2個人輪流取2n個書中的n個數(shù)，所取數(shù)之和大者為勝，請編寫算法，讓先取數(shù)者為 勝，模擬取數(shù)過程。數(shù)學(xué)模型建立：n個數(shù)排成一排，給這n個數(shù)從左到右編號的數(shù)計算機(jī)只能取到另一種 編號的數(shù)。算法設(shè)計：分別計算一組數(shù)的基數(shù)為和偶數(shù)位的數(shù)據(jù)之和，然后就有了先取數(shù)者為勝的取數(shù)方案了。以下面排數(shù)為例：1,2,3,10,5,6,7,8,9,4,奇編號數(shù)之和為25,小于偶編號數(shù)之和30,第一次取出以后，計算機(jī)取哪邊的數(shù)，取數(shù)者就取哪邊的數(shù)，這樣就可以保證取數(shù) 者自始至終取代歐編號的數(shù)，而計算機(jī)自始至終取到奇編號的數(shù)。算法：(1) (a*b+1)*c+1=a*a*a+(2k1+k2)a*a+k1

8、(k1+k2)+1*a+k1+k2+1(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+1所以此問題應(yīng)用貪婪算法。五、算法設(shè)計1、假設(shè)有八個人，畫由循環(huán)日程表，并寫由算法。1234567821436587341278564321876556781234658721437856341287654321int a5050;table1()int k,n=1,i,j;input(k);for(i=1;i=k;i+) n=n*2;dimi(1,n,n);for(i=1;i=n;i+) print(/n);for(j=1;jn/2;k1-)for(k2=i;k2=i-1+n/2;k2+) ak2k1=ak2+n/ 2k1-n/2;for(k2=i+n/ 2;k2=i-1+n;k2+) ak2k1=ak2-n/ 2k1-n/ 2;#includeint main()int a,d;long x,y;for(a=3;a10;a+) for(d=1;d10;d+) x=d*100