算法与分析平时作业-答案

1、平时作业1、给定下述二分搜索算法，请判断算法的正确性，指出错误算法的产生原因。a) int BinarySearch(Type a, const Type& x, int l, int r) while (r = l)int m = (l+r)/2;if (x = am) return m;if (x = l)int m = (l+r)/2;if (x = am) return m;if (x am) r = m+1;else l = m-1;return -1;答：错误if (x am) r = m+1; 当查找的元素在中间元素的左边时，右指针应该为 m-1 位置，修 改成 if (x l)

2、int m = (l+r)/2;if (x = am) return m;if (x l) 要考虑到 数组只有一个元素的情况 所以应该是 r=l2、0(1)空间子数组环卫算法：设a0:n-1是一个n维数组，k (1 k n-1)是一个非负整数。试设计一个算法将子数组a0 : k-1与ak+1 : n-1换位。要求算法在最坏情况下耗时0(n),且只用 0(1)的辅助空间。答：最简单的方法就是循环(n-k-1)次，将a数组的末尾数字插入到a0之前。具体做法：(1) 首先开辟一个额外空间 temp 用于存放每一次 a 数组的末尾数据。(2) temp - an-1(3) 将 a0: n-2 每个数据

3、都依次向后移动一位赋值给 a1: n-1。(4) a0 - temp循环执行-(4)步(n-k+1)次。代价分析：时间代价0(n-1)*(n-k+1)即0(nA2)数量级；空间代价：0( 1)3、定义：给定一个自然数 n,由n开始依次产生半数集 set(n)中的元素如下：1 ) n set(n) ；2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；3) 按此规则进行处理,直至不能再添加新的自然数为止。例如 set(n) 6,16,26,126,36,136 。其中共有 6 个元素。半数集问题：对于给定的 n，求半数集set(n)中元素的个数。答：半数集set(n)中元素个数

4、的求解是个递归的过程。设set(n)中的元素个数为f(n),则显然有递归表达式：f(n)=1+刀f(i) ,i=1,2 n/2。即半数集 set(n)元素个数f(n)=1+f(1)+f(2)+.+f(floor(n/ 2). 用递推法求解。 C 语言代码如下：#include#includeint main()int n;int i,j,s;int buf106;char *in=,*out=;FILE *ip,*op;if(ip=fopen(in,r)=NULL)return 1;if(op=fopen(out,w)=NULL)return 2;fscanf(ip,%d,&n);fclose

5、(ip);buf1=1;buf2=2;buf3=2;for(i=4;i*2=n;i+)s=1;for(j=1;j=i/2;j+)s+=bufj;bufi=s;s=1;for(j=1;j=n/ 2;j+)s+=bufj; fprintf(op,%d,s); fclose(op);/* system(pause);*/return 0;4、设计一个算法，找出由 n 个数组成的序列的最长单调递增子序列的长度。 答： #include #define m 10aj.b) swap(ai,aj);if(ai.b=aj.b)if(ai.faj.f) swap(ai,aj);int int sum=1;o=

6、sum;for(i=2;i=k;i+) for(n=1;ni;n+) if(an.no!=0&an.f=ai.b) ai.no=an.no;an.no=0;o=sum;cout 输出最少会场数 :nsumendl; system(pause);6、最优分解问题：设n 是一个正整数。现要求将 n 分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。分析：我们知道如果玄+匕=常数，则|a-b|越小，a*b越大。贪心策略：将 n 分成从 2 开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。答：void dicomp(int

7、 n, int a)int k = 1;if (n 3) a1 = 0; return; if (n ak) k+;ak = ak - 1 + 1;n -= ak;if (n = ak) ak+; n-;for (int i = 0; i n; i+) ak - i+;7、子集和问题：设 S Xi,X2丄,xn是n个正整数的集合，c是一个正整数。那么是否存 在S的一个子集S1,使得子集中元素之和等于C,即 X c。X 答：#in cludeint n,c; int a100;in t curre nt100;ZZ1,Z2,L,ZkXX!,X2丄，XmYy1,y2 丄，ynXi X1,X2 丄，

8、XiYj%2丄，yj Ai,j%AiA 1Aj, i j设Ai:j的最优次序在 Ak和Ak+ 1之间断开，则mm ：i,k：+ m “+1,门+ p i-1 p k p j其中Ai的维数为pi-1 x pj k的位置只有j-i种可能，i, i+1,j-1，其中使计算量最小的 那个位置 为最优解，数乘次数mi,j最小值为问题的最优值可以递归地定义mi,j为：m i.= min m i, k + 0m k +1, j + p i-1 p k p j i jij 将最优值 mi j对应的断开位置记为 si j，则可递归的由 si j构造出相应的最优解 对于1 ij n不同的有序对(i,j)对应于不同

9、的子问题。因此，不同子问题的个数最多只有守 | -F M =)由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态 规划算法求解的又一显着特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算最终得到多项式时间的算法matrixchain已经记录了构造最优解所需的全部信息。从s1n可知，计算A1:n的最优加括号方式为(A 1 : s1n)(As1n+1: n)计算A 1 : s1n的最优加括号方式为(A 1 :s1s1n )(A s1s1n +1 :

10、 s1n)10、考虑分数背包问题，定义如下：给出n个大小为S1,龟,Sn ,价值为V1, V2,Vn的物nn品， 并设背包容量为 C, 要找到非负实数 x1, x2, , xn, 使和xiVi 在约束 xiSi C 下i 1i 1最大。写出求解问题的贪心算法，估计算法的时间复杂性。i 1i 1答：从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解 的 一个解元素； 由所有解元素组合成问题的一个可行解； 从问题的某一个初始 解出 发逐步逼近给定的目标， 以尽可能快的地求得更好的解。 当达到某算法中 的某一 步不能再继续前进时，算法停止。 #include #defin

11、e total 10 float ptotal,wtotal,ttotal; Void greedy_knaPSack(int x,int c) int note,i; float max; while(1) note=0; max=0; for(i=0;ix;i+) if(maxpi/wi) & (ti=0) max=pi/wi; note=i; if(wnotec) tnote=1; c-=wnote; elSe tnote=c/wnote; break; int main() int i=0,n=0; float cu; printf( 请输入物品 总数(不大于d)与背包的容量：”,total); while(1) scanf(%d%f,&n,&cu); if(ntotal) break; else printf( 物品总数超出范围， 请重新输 入 ： ); printf( 请 输 入 每 个 物 品 的 价 值 与 重 量 ： n); for(i=0;in;i+) scanf