算法設(shè)計與分析a卷及答案

1、算法設(shè)計與分析試題A及答案一 .填空題：（每題4分，共20分）算法是指（解決問題的）一種方法或一個過程，是（若干指令的）有窮序列。程序是（算法用某種程序設(shè)計語言的）具體實現(xiàn)。程序可以不滿足算法的（有限性）性 質(zhì)。貪心選擇性質(zhì)是指所求問題的 整體最優(yōu)解 可以通過一系列局部最優(yōu)的選擇 來達(dá) 到。遞歸函數(shù)的兩大基本要素是 遞歸方程 和 邊界條件 在回溯法中，一個問題的解空間是指一個大的解決方案可以看作是由若干個小的決策組 成。很多時候它們構(gòu)成一個決策序列。解決一個問題的所有可能的決策序列構(gòu)成該問題的 解空間.二簡答題：（每題5分，共20分）簡述分治法所能解決的問題一般應(yīng)具有的特征。）該問題的規(guī)模縮小

2、到一定的程度就可以容易地解決；）該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；）利用該問題分解出的子問題的解可以合并為該問題的解；）該問題所分解出的各個子問題是相互獨(dú)立的。2.設(shè)有待安排的8個活動的開始時間和結(jié)束時間如下表。請采用貪心算法給出活動安排序 列，要求安排盡可能多的活動。12345678Si451028571fi6715410993解：將待安排的8個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下:i12345678Si124557810fi3467991015用貪心算法給出活動安排序列：1, 3, 6,8。貪心選擇的意義是使剩余的可安排時間段極 大化，以便安排盡可能多的相容活動。請描述分治法的具體過

3、程。將原問題劃分成k個子問題。對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠 小，則再劃分為k個子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其 解為止。將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解，自底向上逐步求出 原來問題的解。Fibonacci數(shù)列如下定義：1 n =0F (n) =1n = 1F (n -1) + F (n - 2) n 11、請設(shè)計一個遞歸算法，計算F(n)。2、分析算法的時間復(fù)雜性。解 1、 int fibonacci(int n) if (n = 1) return 1;return fibonacci(n-1)+fibonacci(n-2)

4、;2、T(n)=T(n-1)+T(n-2)。三.算法分析解答題：(每小題20分，共60分)1.考慮金錢兌換問題：有一個貨幣系統(tǒng)，它有n種硬幣，它們的面值為 v,v,v，其中v=1.我們想這樣來兌換價值為y的錢，要讓硬幣的數(shù)目最 農(nóng)2更形式地，我們要讓下面的量i=1在約束條件Exv =yiii=1下達(dá)到最小.其中x1，x2，x是非負(fù)整數(shù).用貪心算法求解該問題；n如果硬幣的面值有1分，5分，7分和11分，給出反例說明用貪心算法并不總是有 效的。1)貪心偽代碼為：Greedy_exchange ( int v, int y, int num, int n)int i=0；for( i=0;i0)nu

5、mi=y/vi;y=y % numi+；return num;2)反例：假如要給顧客找15分錢，按照上述貪心策略，則應(yīng)將15分分解為：11分+1 分+1分+1分+1分。而事實上15分可分解為：5分+5分+5分。顯然后者的張數(shù)更少。假設(shè)有n(neN且n1)個硬幣，已知其中有一個是假幣且假幣較真幣輕.請設(shè)計分治算法 求解該問題.并給出其復(fù)雜度分析.Feit_money(low, high) /假定偽幣較真幣輕float mid;if ( high-low=1 )if (AlowAhigh) return Ahigh;else mid=(low+high)/2;if (high-low+1)%2)=

6、0 sum1=sum(low, mid);sum2=sum(mid+1, high);elsesum1=sum(low, mid-1);sum2=sum(mid+1, high);if sum1=sum2 return Amid;else if (sum1 0;氣=y.maxci j-1,ci-1j i, j 0;X。、1i jc、 void LCSLength(int m，int n，char *x，char *y，int *c，int *b) int i，j;for (i = 1; i = m; i+) ci0 = 0;for (i = 1; i = n; i+) c0i = 0;for (i = 1; i = m; i+)for (j = 1; j =cij-1) cij=ci-1j; bij=2; else cij=cij-1; bij=3; 構(gòu)造最長公共子序列void LCS(int i，int j，char *x，int *b)if (i =0 | j=