算法分析复习题.doc

一、阅读以下说明和图，填补流程图中的空缺，将解答填入答题纸的对应栏内。 说明 在一条农村公路的一边稀疏地分布着房子，其分布如下图所示。某电信公司需要在某些位置放置蜂窝电话基站，由于基站的覆盖范围是6公里，因此必须使得每栋房子到某个基站的直线距离不超过 6 公里。为简化问题，假设所有房子在同一直线上，并且基站沿该直线放置。现采用贪心策略实现用尽可能少的基站覆盖所有的房子。实现贪心算法的流程如下图所示，请填充其中空白并计算该算法的时间复杂度，其中：1di(1i N)表示第i个房子到公路A端的距离，N表示房子的总数，房子编号按照房子到公路A端的距离从小到大进行编号。2sk表示第 k（k 1）个基站到公路 A 端的距离，算法结束后 k 的值为基站的总数。该算法的时间复杂度为 （5）。二、阅读下列说明，回答问题 1 至问题 3，将解答填入答题纸的对应栏内。 【说明】某餐厅供应各种标准的营养套餐。假设菜单上共有 n 项食物 m1，m2，mn，每项食物 mi的营养价值为 vi，价格为 pi，其中 i=1,2,n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M 的营养价值最大的套餐。【问题 1】下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)处。伪代码中的主要变量说明如下：n：总的食物项数；v：营养价值数组，下标从 1 到 n，对应第 1 到第 n 项食物的营养价值；p：价格数组，下标从 1 到 n，对应第 1 到第 n 项食物的价格；M：总价格标准，即套餐的价格不超过 M；x： 解向量（数组），下标从 1 到 n，其元素值为 0 或 1，其中元素值为 0 表示对应的食物不出现在套餐中，元素值为 1 表示对应的食物出现在套餐中；nv：n+1 行 M+1 列的二维数组，其中行和列的下标均从 0 开始，nvij表示由前 i 项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为nvnM。伪代码如下：MaxNutrientValue(n, v, p, M, x) 1 for i = 0 to n2 nvi0 = 03 for j = 1 to M 4 nv0j = 05 for i = 1 to n6 for j = 1 to M 7 if j pi /若食物 mi不能加入到套餐中8 nvij = nvi - 1j 9 else if （1） 10 nvij = nvi - 1j 11 else 12 nvij = nvi - 1j pi + vi 13 j = M 14 for i = n downto 115 if （2） 16 xi = 0 17 else 18 xi = 119 （3） 20 return x and nvnM 【问题 2】 现有 5 项食物，每项食物的营养价值和价格如表1 所示。表 1 食物营养价值及价格表编 码营养价值价 格m120050m218030m322545m420025m5505若要求总价格不超过 100 的营养价值最大的套餐，则套餐应包含的食物有 （4） （用食物项的编码表示），对应的最大营养价值为（5）。【问题 3】 【问题 1】中伪代码的时间复杂度为（6）（用 符号表示）。三、算法填空1.背包问题的贪心算法void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; for (i=1;i=n;i+) xi=0; float c=M; for (i=1;ic) break; xi=1; _; _;2.最大子段和: 动态规划算法int MaxSum(int n, int a) int sum=0, b=0； /sum存储当前最大的bj, b存储bj for(int j=1； j0) b+= aj ； _； /一旦某个区段和为负，则从下一个位置累和 if(bsum) _; return sum； 3.贪心算法求装载问题templatevoid Loading(int x, Type w, Type c, int n) int *t = new int n+1; ; for (int i = 1; i = n; i+) xi = 0; for (int i = 1; i = n & wti = c; i+) xti = 1; ;4.贪心算法求活动安排问题templatevoid GreedySelector(int n, Type s, Type f, bool A) _; int j=1; for (int i=2;i=fj) _; j=i; else Ai=false; 5.快速排序templatevoid QuickSort (Type a, int p, int r) if (pr) int q=Partition(a,p,r); _; /对左半段排序 _; /对右半段排序 6.排列问题Template void perm(Type list, int k, int m ) /产生listk:m的所有排列 if(k=m) /只剩下一个元素 for (int i=0;i=m;i+) coutlisti; coutendl; else /还有多个元素待排列，递归产生排列 for (int i=k; i=m; i+) swap(listk，listi); perm(list,k+1;m); swap(listk,listi); 四、问答题1.分治法的基本思想是什么？2. 设计动态规划算法的主要步骤是什么3. 分治法与动态规划法的异同有哪些4. 分支限界法与回溯法的异同有哪些5. 分支限界法的搜索策略什么6. 分治法所能解决的问题一般具有的几个特征是：7. 用分支限界法设计算法的步骤是：8. 常见的两种分支限界法的算法框架9. 回溯法中常见的两类典型的解空间树是子集树和排列树。