13計本算法分析與設(shè)計期末試卷B

1、PAGE 福建師范大學 數(shù)學與計算機科學學院 2015 2016 學年第 2 學期考試 B 卷考生信息欄學院系 專業(yè) 年級姓名 學號裝 訂 線 專 業(yè)： 計算機科學與技術(shù) 年 級： 2013 課程名稱: 算法設(shè)計與分析 任課教師： 翁 彬 試卷類別：開卷（ ）閉卷（ ） 考試用時： 120 分鐘考試時間: 年 月 日 午 點 分題號一二三四五總得分評卷人得分題號六七八九十得分一計算題（共15分）1. 解下列方程，并給出解的階。(共10分，每小題5分)(1)算法A的時間復雜性為，(2)算法B的時間復雜性為2. 計算下面算法中count=count+1的執(zhí)行次數(shù)。（5分）算法 COUNT3 輸入：

2、，k為正整數(shù) 輸出：count=count+1的執(zhí)行次數(shù) count=0 for i=1 to n j=2 while j=n j=j2 count=count+1 end while end for return count end COUNT3二簡答題（共25分）1. 分治算法由哪些基本步驟組成？分治算法的時間復雜性常滿足什么樣的遞歸方程，寫出該方程的一般形式，并指出其中各參數(shù)的意義。（12分）2. 使用動態(tài)規(guī)劃解最優(yōu)化問題的步驟是什么？（8分）3最大k乘積問題：設(shè)I是一個n位十進制整數(shù)。如果將I劃分為k段，則可得到k個整數(shù)。這k個整數(shù)的乘積稱為I的一個k乘積。對于給定的I和k，求出I的最

3、大k乘積。當用動態(tài)規(guī)劃求解該問題時，最優(yōu)子結(jié)構(gòu)是什么？遞歸關(guān)系式是什么？（5分）三算法填空題（共45分，每空3分） 1. 以下是計算xm的值的過程power ( x, m )if m=0 then y=_ (1)_else y=_ (2)_ y=y*y if m為奇數(shù) then y=x*y考生信息欄學院系 專業(yè) 年級姓名 學號裝 訂 線end if_ (3)_end power2. 以下是關(guān)于矩陣鏈乘的算法MATCHAIN1和MATCHAIN_PRODUCT算法 MATCHAIN1輸入：矩陣鏈長度n, n個矩陣的階r1.n+1, 其中r1.n為n個矩陣的行數(shù)，rn+1為第n個矩陣的列數(shù)。輸出：

4、n個矩陣相乘的數(shù)量乘法的最小次數(shù)，最優(yōu)順序的信息數(shù)組S1.n, 1.n。for i=1 to n Ci, i=0 /對角線d0置 for d=1 to n-1 /逐條計算對角線d0dn-1 for i=1 to n-d / 計算對角線dd的n-d個元素。 _ (1)_ Ci, j= for k=i+1 to j x= _ (2)_ if _ (3)_ then Ci, j=x; Si, j=k end if end for end for end for return C1, n, Send MATCHAIN1算法 MATCHAIN_PRODUCT輸入：矩陣鏈長度n, n個矩陣M1, M2,

5、, Mn , 最優(yōu)乘法順序的信息數(shù)組S1.n, 1.n。輸出：按最優(yōu)順序計算的矩陣鏈乘積M=M1M2Mn 。 M=matchain_product( 1, n ) return Mend MATCHAIN_PRODUCT 過程 matchain_product (i, j)if _ (4)_ then return Mi elseA=matchain_product _ (5)_ B=matchain_product _ (6)_ C=multiply( A , B) /計算兩個矩陣乘積C=AB。 return C end ifend matchain_product3. 以下是迷宮問題的算法

6、算法 MAZE 輸入：正整數(shù)m, n，表示迷宮的數(shù)組M0.m+1, 0.n+1 (迷宮數(shù)據(jù)存于M1.m, 1.n中)，迷宮的入口位置(ix, iy),出口位置(ox, oy)。 輸出：迷宮中入口至出口的一條通路，若無通路，則輸出no solution。 M0, 0.n+1=Mm+1, 0.n+1=1 M0.m+1, 0=M0.m+1, n+1=1 /設(shè)置迷宮邊界。 tag1.m, 1.n=0 為dx1.4, dy1.4置值 flag=false /flag表示是否存在通路。 x=ix; y=iy ; tagx, y=1 /進入入口, (x, y)表示當前位置。 i=1; ki=0 while

7、_ (1)_ and not flag while _ (2)_ and not flag _ (3)_ /試沿著下一個方向搜索。 x1= x+dxki; y1= y+dyki if Mx1, y1=0 and tagx1, y1=0 then /位置(x1,y1)可走 if x1=ox and y1=oy then _ (4)_ /找到一條通路 else x=x1; y=y1; tagx, y=1 /進入新位置。 i=i+1 ； ki= _ (5)_ /準備搜索下一個位置。 end if end if /否則，剪枝 end while_ (6)_; x=x-dxki; y=y-dyki/回溯 end while if flag then outputroute(k, i) /輸出由k1.i表示的通路。 else output “no solution”/輸出無解end MAZE四算法設(shè)計題（15分）1.設(shè)有n個活動a1, a2, , an , 每個活動