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

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

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

3、程。將原問題劃分成k個(gè)子問題。對(duì)這k個(gè)子問題分別求解。如果子問題的規(guī)模仍然不夠 小，則再劃分為k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其 解為止。將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出 原來問題的解。Fibonacci數(shù)列如下定義：1 n =0F (n) =1n = 1F (n -1) + F (n - 2) n 11、請(qǐng)?jiān)O(shè)計(jì)一個(gè)遞歸算法，計(jì)算F(n)。2、分析算法的時(shí)間復(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.考慮金錢兌換問題：有一個(gè)貨幣系統(tǒng)，它有n種硬幣，它們的面值為 v,v,v，其中v=1.我們想這樣來兌換價(jià)值為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分。而事實(shí)上15分可分解為：5分+5分+5分。顯然后者的張數(shù)更少。假設(shè)有n(neN且n1)個(gè)硬幣，已知其中有一個(gè)是假幣且假幣較真幣輕.請(qǐng)?jiān)O(shè)計(jì)分治算法 求解該問題.并給出其復(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=