算法分析题：
1.1求下列函数的渐近表达式：
?(n)=3n2. T(n)=3n2?10n的渐近表达式T?(n)=2n. T(n)=n2/10?2n的渐近表达式为T?(n)=21. T(n)=21+1/n的渐近表达式为T?(n)=3logn. T(n)=logn3的渐近表达式为T?(n)=log3?10n. T(n)=10log3n的渐近表达式为T1.2试论O(1),O(2)的区别。
因为: O(1)+O(1)=O(1?1)=O(2) O(1)+O(1)==O(1). 所以，O(1)，O(2)应该是相等的。
2n2/31.3 按照渐近阶从低到高的顺序排列以下表达式：4n,logn,3,20n, 2,n.又
n!应该排在哪一位？
从低到高：2，logn，20n，n2/3，4n，3，n!
2n2.2 下面的7个算法与本章中的二分搜索算法Binary Search略有不同。请判断这7个算法的正确性。如果算法不正确，请说明产生错误的原因。如果算法正确，请给出算法的正确性证明
1. while(left<=right)
{ int middle=(left+right)/2;
if(x==a[middle])return middle; if(x>a[middle])left=middle; else right=middle; }return -1;
不正确，当循环进行到只有两个元素的时候，int middle=(left+right)/2,就等于那个较
小的元素位置。这时如果X大于较小的元素的时候，即if(x>a[middle])left=middle;就造成了下次循环还是两个元素，这就形成了死循环。
当循环进行只有一个元素的时候，若X不等于这个元素，无论是大还是小，left，
middle，right的值都一样，都会继续进行循环，这也是死循环。
页 6
2. while(left 是while(left 元素的时候，middle=(left+right)/2为第二个元素,left=middle,则下一步是三个元素)，则 不正确，当x等于最后一个最大的此次循环执行完毕时，只有最后两个元素， 元素的时候，循环中的if(x ******************************************************************************* 3. while(left+1!=right) 不正确，当x=最大元素的时候，因 { int middle=(left+right)/2; if(x }if(x==a[left])return left; return -1; { int middle=(left+right)/2; if(x>=a[middle])left=middle; else right=middle; } if(x==a[left])return left; return -1; 为循环的条件是left+1!=right,循环到最大的两个元素的时候跳出，但接下来只拿这两个元素的左元素和X做比较，做出了误判。 ******************************************************************************* 4. if(n>0&&x>=a[0]) 不正确，当循环至两个元素时， { int left=0,right=n-1; middle=(left+right)/2为左元素，若x=右元素， while(left { int middle=(left+right)/2; 则执行left=middle，陷入死循环。 if(x } if(x==a[left])return left; } return -1; ******************************************************************************* 5. if(n>0&&x>=a[0]) { int left=0,right=n-1; s1?s2?s，其中s1s2为s的子集。那么 while(left { int middle=(left+right+1)/2; if(x } if(x==a[left])return left; }return -1； x?s?x?s1或者x?s2。若有方法判定x?s1还是x?s2，就能够进行循环，直到 这个是正确的，正确性证明：x是集合s中的一个元素，s中有n个元素， 找到该元素为止。算法中正是此情况，所以是正确的。 *******************************************************************************6. if(n>0&&x>=a[0]) 不正确，因为这个算法实际上是把s { int left=0,right=n-1; while(left { int middle=(left+right+1)/2; if(x if(x==a[left])return left; } return -1； 分为了3部分，s1，a[middle],s2.当x< a[middle]时，它属于s1是正确的，但x>=a[middle]时，它不一定属于s2 ******************************************************************************* 7. if(n>0&&x>=a[0]) 不正确，只有两个元素的时候， { int left=0,right=n-1; middle为第二个元素。If语句成立的时候， while(left { int middle=(left+right+1)/2; right=middle，相当于没有变化，这就陷入 if(x else left=middle; 了死循环。 } if(x==a[left])return left; } return -1； 页 7 2.26试说明如何修改快速排序算法，使它在最坏情况下的计算时间为O(nlogn)。 答：完全保证使快速排序算法在最坏情况下的计算时间为O(nlogn)是很困难的，但可以采用一些办法来消除算法的退化结构，比如课本上的随机选择策略，以及我要说的平衡快速排序。 鉴于在平时生活中的数据排序，其数据往往带有规律性。在中值的选择策略上，我们比较一下第一个，最后一个，以及中间一个的值，以这3个值中位于中间的那个来进行划分，这样就能使快速排序避免了大多数的最坏情况，即使是对于两边小中间大的特殊情况，这个方法也有其作用——在第一遍排序时打乱这个特殊情况。因此，这个算法在实际运用中是比较好的一种快速排序。 算法如下： template int partition (Type a[],int p,int r) { int i=p,j=r+1; } int BalancePartion(Type a[],int p,int r) { int i,m; m=(p+r)/2; switch(1) Type x=a[p]; while(1) { while(a[++i] while(a[--j]>x); if(i>=j)break; Swap(a[i],a[j]); } void BalanceQuickSort(Type a[],int p,int r) { if(p { int q=BalancePartition(a,p,r); } BalanceQuickSort(a,p,q-1); BalanceQuickSort(a,q+1,r); } Swap(a[i],a[p]); return Partition(a,p,r); { case(a[p]<=a[m]&&a[p]>=a[r]) ||(a[p]>=a[m]&&a[p]<=a[r]):i=p;break; case(a[m]<=a[p]&&a[m]>=a[r]) ||(a[m]>=a[p]&&a[m]<=a[r]):i=m;break; case(a[r]<=a[m]&&a[r]>=a[p]) ||(a[r]>=a[m]&&a[r]<=a[p]):i=r;break; 3.5给定n种物品和一背包。物品i的重量是wi，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包时，对每种物品i只有两种选择，即装入背包或者不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。试设计一个解此问题的动态规划算法，并分析算法的计算复杂性。 算法如下： 页 8 int MaxValue(int n,int c,int *w,int d,int *b,int *v,int ***m) { int t = max(w[n],b[n]); for(int i = 1;i for( int j = 1;j else{x[i]=1;c-=w[i];d-=b[i];} for(int j = t;j } t = max(w[i],b[i]); for(int j1 = 1;j1 for(int k1 = 1;k1 m[i][j1][k1] = m[i+1][j1][k1]; for(int j1 = t;j1<=c;j1++) for(int k1 = t;k1<=d;k1++) m[i][j1][k1] = max(m[i+1][j1][k1], m[i+1][j1-w[i]][k1-b[i]]+v[i]); } m[1][c][d] =max( m[2][c][d], m[2][c-w[1]][d-b[1]]+v[1]); return m[1][c][d]; } 5.4试设计一个解最大团问题的迭代回溯法。 我设计的算法如下： int n=1,k;//n放的是最大团的点个数，k放的不同最大团的个数。 int q[MAX][MAX]; int backtrack(int *p,int a,int b); {//p[]中存放的是图中各点的序号 if(b-a<1)return 0; if(b-a=1){ if(p[a]p[b]无边相连)return 0； else {if(n=1)n++;return 1;} } for(int i=a;i<=b;i++) { swap(p[a],p[i]); if(backtrack(p,a+1,b)) { if(判断p[a]和p[a+1~b]都有边)//************************* { if(b-a+1>n;) { n++; k=0; for(int j=0;j<=n;j++)q[0][j]=p[a+j]; } else if(b-a+1=n)//&&&&&&&&&&& { for(int j=0;j 页 9 算法实现题： 2.2 众数问题。 给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称之为众数。 算法设计：对于给定的由n个自然数组成的多重集S，计算S的众数及其重数。 数据输入：输入数据由文件名为input.txt的文本文件提供。文件的第一行为多重集S中元素个数n；在接下来的n行中，每行有一个自然数。 结果输出：将计算结果输出到文件output.txt。输出文件有2行，第1行是众数，第2行是重数。 我的递归算法实现如下： #include int mode(int *p,int a) { int i,j,k[MAX],m=0,n=0; //m为删除的个数，n为保留的个数，k[a]为删除的数的记录。 } if(a==0)return p[0]; x++; if(a==1)return p[0]; for(i=0;i { for(j=0;j return mode(p,n); if(j==m) {m++;k[m-1]=p[i];} //在已删除个数字里找不到p[i]，则删除它。 else{n++;p[n-1]=p[i];} int main(void) { } int i,a,b[MAX]; FILE *fp1,*fp2; fp1=fopen(\,\); fp2=fopen(\,\); fscanf(fp1,\,&a); for(i=0;i 3.2最小硬币问题。 算法设计：对于给定的1<=n<=10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0<=m<=20001,计算找钱的最少硬币数。硬币的面值存于T[]中，个数存于Coins[]中。 数据输入：input.txt提供输入数据，文件的第1行中只有1个整数给出的n的值，第2行起每行2个数，分别是T[j]和Coins[j]。最后1行使要找的钱数m。 结果输出：将计算出的最少硬币数输出到文件output.txt。问题无解时输出-1。 答：由于硬币的面值其实是一组特殊值，(10)>=2*(5)>=2*2*(2)>=2*2*2*(1).因此，使用贪心算法可以很简便的算出问题答案。但是我们要考虑的是，假设硬币的面值可以为任何值，比如，7,16，等等，这时就不能使用贪心算法，我采用动态规划来解决这个问题。令T[]的值有序排列，当只用面值小于等于T[i]的硬币时，可找钱j的最少硬币数为n[i][j],则p[i][j]满足递归p[i][j]= min(p[i-1][j], p[i-1][j-k*T[i]]+k), 其中递归在K的循环for(k=1;k<=Coins[i];k--)中，来判别是否有足够的该面值的硬币可以使用。 页 10