算法与分析平时作业.doc

平时作业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 l) int m = (l+r)/2; if (x = am) return m; if (x = l)2、O(1)空间子数组环卫算法：设a0:n-1是一个n维数组，k（1 k n-1）是一个非负整数。试设计一个算法将子数组a0 : k-1与ak+1 : n-1换位。要求算法在最坏情况下耗时O(n)，且只用O(1)的辅助空间。答：算法分析： 当vk左边子数组的长度等于右边的子数组长度时，直接将两个子数组对应的元素互换即可 当左边子数组长度小于右边子数组长度时，将左边子数组与右边子数组右边的等长子数组对换，再对结果递归调用对换函数 当右边子数组长度小于左边子数组长度时，将右边子数组与左边子数组左边的等长子数组对换，再对结果递归调用对换函数 通过分析，可知只需要利用保存元素对换时的交换空间即可，空间复杂度为O(1)，子数组对换时时间复杂度不会超过O(n)#include #include #include #include using namespace std; /对应互换v的left_low-left_high 和 right_low - right_high void Swap(vector & v,int left_low,int left_high,int right_low,int right_high) int temp; while(left_low = left_high) temp = vleft_low; vleft_low = vright_low; vright_low = temp; +left_low; +right_low; return; /分治算法，每次选最小的子数组对应交换 void Exchange(vector & v,int k,int low,int high) if(lowhigh) if(k-low+1)=(high-k)/vk左右两个子数组长度相等，直接互换 Swap(v,low,k,k+1,high); else if(k-low+1)(high-k)/vk左边子数组长度小于右边子数组，将左边的子数组互换到右边子数组的右边Swap(v,low,k,low+high-k,high); Exchange(v,k,low,low+high-k-1); else /vk右边子数组换到左边子数组前部分 Swap(v,low,high+low-k-1,k+1,high); Exchange(v,k,high+low-k,high); return; int main() vector v; int n,k; while(scanf(%d%d,&n,&k)=2) v.resize(n); for(int i=0;in;+i) scanf(%d,&vi); printf(Before exchange subarray:n); for(int j=0;jn;+j) printf(%d ,vj); printf(n); Exchange(v,k,0,n-1); printf(After exchange subarray:n); for(int k=0;kn;+k) printf(%d ,vk); printf(n); return 0; 3、定义： 给定一个自然数n，由n开始依次产生半数集set(n)中的元素如下： 1）； 2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半； 3）按此规则进行处理，直至不能再添加新的自然数为止。 例如 。其中共有6个元素。 半数集问题：对于给定的n，求半数集set(n) 中元素的个数。答：#includeusing namespace std;int a1001;int comp(int n) int i; for( i=2;i=n;i+) if(i%2=0) ai=ai/2+ai-1; else ai=ai-1; return an;int main() int n; coutn; for(int i=0;i=n;i+) ai=i; if(n1000) coutendl输入错误，请注意输入值n的范围.endl; else coutendl半数集set(n)中的元素个数为：; coutcomp(n)endl; return 0; 4、设计一个算法，找出由n个数组成的序列的最长单调递增子序列的长度。答：#include#definem10/快速排序voidQuickSort(intR,ints,intt)inti=s,j=t;inttmp;if(si&Rj=tmp)j-;Ri=Rj;while(ij&Ri=tmp)i+;Rj=Ri;Ri=tmp;QuickSort(R,s,i-1);QuickSort(R,i+1,t);/找出最长公共子序列voidLCSLength(intx,inty,intn,intcmm,intbmm)inti,j;for(i=0;in;i+)c0i=0;ci0=0;for(i=0;in;i+)for(j=0;j=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;voidLCS(inti,intj,int*x,intbmm)if(i0|j0)return;if(bij=1)LCS(i-1,j-1,x,b);coutxi;elseif(bij=2)LCS(i-1,j,x,b);elseLCS(i,j-1,x,b);voidmain()intxm,ym,d;cout请输入元素个数d;cout请输入元素endl;for(inti=0;ixi;yi=xi;intcmm=0,bmm=0;QuickSort(x,0,d-1);LCSLength(x,y,d,c,b);cout最长单调递增子序列为：endl;LCS(d-1,d-1,x,b); 5、会场安排问题：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。对于给定的n个待安排的活动，计算使用最少会场的个数。每个活动i都有一个开始时间和结束时间，分别表示为b(i)，f(i)。答：#includeusingnamespacestd;#defineM50/最大活动数structActiveintb;/开始时间intf;/结束时间intno;/预安排会场号aM;/两元素交换位置voidswap(Active&a,Active&b)Activet;t=a;a=b;b=t;voidmain()intk;inti,j;cout输入待安排活动数:k;cout输入待安排活动的开始时间和结束时间:endl;/输入活动时间for(i=1;iai.bai.f;ai.no=0;/活动时间排序for(i=1;i=k;i+)for(j=i;jaj.b)swap(ai,aj);if(ai.b=aj.b)if(ai.faj.f)swap(ai,aj);intsum=1;/使用的会场数初始化intn;a1.no=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;/已经安排过的活动就不再比较break;if(n=i)sum+=1;ai.no=sum;cout输出最少会场数:nsumendl;system(pause);6、最优分解问题：设n是一个正整数。现要求将n分解为若干个互不相同的自然数的和，使得这些自然数的乘积最大。设计一个算法，得到最优分解方案。 分析：我们知道如果a+b=常数，则|a-b|越小，a*b越大。 贪心策略：将n分成从2开始的连续自然数的和。如果最后剩下一个数，将此数在后项优先的方式下均匀地分给前面各项。答：void dicomp(int 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、子集和问题：设是n个正整数的集合，c是一个正整数。那么是否存在S的一个子集S1，使得子集中元素之和等于c，即。答：#includeintn,c;inta100;intcurrent100;/存放当前选择的情况intbest100;/存放最后选择的子集合，besti=1，表示包含，反之即不包含。intd=1;/判断有无满足的情况intd2=0;/是否已经选出子集和voidBack(intm,intcount);intmain()inti,j;scanf(%d%d,&n,&c);for(i=0;in;i+)scanf(%d,&ai);currenti=besti=0;Back(0,0);if(d)printf(nosolutionn);for(j=0;jn)return;if(count=c)d=0;/有满足的子集和if(d2)return0;for(k=0;k 0 xi = yi 时 , cij = ci-1j-1 + 1 当 i , j 0 xi != yi 时 , cij = max cij-1 , ci-1j public class LSC private int c,b;private int m,n;private char A,B;public LSC(char A,char B) this.A=A; this.B=B; m=A.length; n=B.length; c=new intm+1n+1; b=new intm+1n+1;for(inti=0;in+1;i+) c0i=0; for(intj=0;jm+1;j+)cj0=0;public LSC() public int LSCLength() for(int i=1;im+1;i+) for(int j=1;j=cij-1) cij=ci-1j; bij=1; /* * 情况 */ else cij=cij-1; bij=2; return cmn; public void print(int i,int j) if(i=0|j=0) return; else if(bij=0) print(i-1,j-1); System.out.print(Ai-1); else if(bij=1) print(i-1,j); else print(i,j-1); public int LSCLength2(int i,int j) if(i0|ja2?a1:a2; public static void main(String args) char A=g,f,d,a,s,d,a,c; char B=g,c,f,a,t,0,c,c; LSC lsc=new LSC(A,B); System.out.println(lsc.LSCLength2(7,7); 9、记矩阵连乘积 。 确定计算A1:n的最优计算次序，使得所需数乘的次数最少。 1、说明矩阵连乘计算次序问题的最优解包含着其子问题的最优解，即最优子结构性质。 2、该问题具备子问题的重叠性质。 3、说明采用动态规划方法可以解决该问题。 4、设计该算法，分析算法的复杂性。答：计算Ai:j的最优次序所包含的计算矩阵子链Ai:k和Ak+1:j的次序也是最优的。设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n当i=j时，Ai:j=Ai，无需计算，因此，mi,j=0，i=1,2,n当ij时，利用最优子结构性质计算mi,j . 设Ai:j的最优次序在Ak和Ak1之间断开，则其中Ai的维数为pi-1pjk的位置只有j-i 种可能, i, i+1, , j-1，其中使计算量最小的那个位置为最优解，数乘次数mi,j最小值为问题的最优值可以递归地定义mi,j为：将最优值mi j对应的断开位置记为si j，则可递归的由si j构造出相应的最优解对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算最终得到多项式时间的算法matrixChain 已经记录了构造最优解所需的全部信息。从s1n 可知，计算A1:n的最优加括号方式为( A 1 : s1n ) (As1n+1: n )计算A 1 : s1n 的最优加括号方式为(A 1 : s1s1n )(A s1s1n +1 : s1n )10、考虑分数背包问题，定义如下：给出n 个大小为 s1, s2, , sn , 价值为v1, v2, , vn 的物品， 并设背包容量为C, 要找到非负实数x1, x2, , xn, 使和 在约束下最大。写出求解问题的贪心算法，估计算法的时间复杂性。答：从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；