算法与分析与设计平时作业

《算法与分析与设计平时作业》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、平时作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。a)intBinarySearch(Typea[],constType&x,intl,intr){while(r>=l){intm=(l+r)/2;if(x==a[m])returnm;if(x=l){intm=(l+r)/2;if(x==a[m])returnm;if(x

2、=m+1;elsel=m-1;}return-1;}c)intBinarySearch(Typea[],constType&x,intl,intr){while(r>l){intm=(l+r)/2;if(x==a[m])returnm;if(x

3、：给定一个自然数n，由n开始依次产生半数集set(n)中的元素如下：1）；2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；3）按此规则进行处理，直至不能再添加新的自然数为止。例如。其中共有6个元素。半数集问题：对于给定的n，求半数集set(n)中元素的个数。4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。5、会场安排问题：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的n个待安排的活动，计算使用最少会场的个数。每个活动i都有一个开始时间和结束时间

4、，分别表示为b(i)，f(i)。6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。分析：我们知道如果a+b=常数，则

5、a-b

6、越小，a*b越大。贪心策略：将n分成从2开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。7、子集和问题：设是n个正整数的集合，c是一个正整数。那么是否存在S的一个子集S1，使得子集中元素之和等于c，即。8、设序列是序列和的最长公共子序列。a)请说明最长公共子序列具有最优子结构性质。b)设c[i

7、][j]记录序列i和的最长公共子序列的长度。由最长公共子序列问题的最优子结构性质建立子问题最优值c[i][j]的递归关系。a)写出寻找最长公共子序列的算法。9、记矩阵连乘积。确定计算A[1:n]的最优计算次序，使得所需数乘的次数最少。1、说明矩阵连乘计算次序问题的最优解包含着其子问题的最优解，即最优子结构性质。2、该问题具备子问题的重叠性质。3、说明采用动态规划方法可以解决该问题。4、设计该算法，分析算法的复杂性。10、考虑分数背包问题，定义如下：给出n个大小为s1,s2,…,sn,价值为v1,v2,…,vn的物品，并设背包容量为C,要找到

8、非负实数x1,x2,…,xn,使和在约束下最大。写出求解问题的贪心算法，估计算法的时间复杂性。