算法分析与设计复习题及参考答案 下载本文

x=615×x=625543××x=24433???? 即有4个可行解:

(6,6,2),(6,5,3),(6,4,4,)(5,5,4)。 11、设数组A有n个元素,需要找出其中的最大最小值。 (1) 请给出一个解决方法,并分析其复杂性。 (2) 把n个元素等分为两组A1和A2,分别求这两组的最大值和最小值,然后分别将这两组的最大值和最小值相比较,求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个,则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想?请给出该方法的算法描述,并分析其复杂性。 解:(1)基本思想:从头到尾逐个扫描,纪录最大和最小元素。 输入:具有n个元素的数组 输出:最大值和最小值 步骤:

void FindMaxMin(int A[], int n, int max, int min) { max=min=A[0]; for (i=1;imax) max=A[i]; if (A[i]

max=(A[left]

}

A[left]

else{ mid=(left+right)/2; FindMaxMin(left,mid,gmax,gmin); FindMaxMin(mid+1,right,hmax,hmin); max=(gmax

min=(gmin

12、有n个程序

和长度为L的磁带,程序i的长度为a,已知 ,求最优解(x,x ,...,x,…,ii2i

1

n

x),x =0,1, x =1,表示程序i

存入磁带,x =0,表示程序i不存入磁带,满足,且存放

niii

的程序数目最多。 解:由于目标是存放的程序数目最

多,所以最优量度应该是 min{a| a为程序i的长度}, i i即每次选入的程序都是当前最短的。我们可以将n个程序按a[1]≤a[2]≤…≤a[n]顺序排序,然后从i=1开始依次选择。算法如下: procedure programming(L,n, a, x) begin //n个程序按a[1]≤a[2]≤…≤a[n]顺序排序 x←0; i=1; while (a[i] ≤L and i≤n) do { x[i] ←1; L←L-a[i];i←i+ 1; } end.

13、试用分治

法实现有重复元素的排列问题:设是要进行排列的个元素,其中元素

12nr,r,...,rR可能相同,试设计计算的所有不同排列的

算法。 12n

解:解答如下: Template void Perm(Type list[],int k,int m) { if(k= =m){ for(int i=0;i<=m;i++) cout< int ok(Type list[],int k,int i) { if(i>k) for(int t=k;t

动态规划算法实现0-1闭包问题,请写出该算法。 解:解答如下: Template void Knapsack(Type v,int w,int c,int n,Type **m) { Int jMax=min(w[n]-1,c); for(int j=0;j<=jMax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i--){ jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) m[i][j]=m[i+1][j];

for(int

j=w[i];j<=c;j++)

m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); }; m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } Template Void Traceback(Type **m,int w,int c,int n,int x) { for(int i=1;i

15、试用贪心算法求解下列问题:将正整数n分解为若干个互不相同的自然数之和,使这些自然数的乘积最大,请写出该算法。 解:解答如下: void dicomp(int n,int a[]) { k=1; if(n<3){ a[1]=0;return;}; if(n<5){ a[k]=1;a[++k]=n-1;return;}; a[1]=2;n-=2; while(n>a[k]){ k++; a[k]=a[k-1]+1; n-=a[k]; }; if(n= =a[k]){ a[k]++;n--;}; for(int i=0;i int BinarySearch(Type a[],const Type& x,int n) {//假定数组a[]已按非递减有序排列,本算法找到x后返回其在数组a[]中的位置,//否则返回-1 int left=0,right=n-1; while(left<=right){ int middle=(left+right)/2;

if(x= =a[middle]) return middle+1; if(x>a[middle]) left=middle+1; else right=middle-1; } return -1; } 17、试用动态规划算法实现最长公共子序列问题,请写出该算法。 解:用动态规划算法求解的算法代码如下: int lcs_len(char *a,char *b,int c[][N]) { int m=strlen(a),n=strlen(b),i,j; for(i=0;i<=m;i++) c[i][0]=0; for(j=1;j<=n;j++) c[0][j]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(a[i-1]=

=b[j-1]) c[i][j]=c[i-1][j-1]+1; else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j]; else c[i][j]=c[i][j-1]; return c[m][n]; }; char *build_lcs(char s[],char *a,char *b)

{ int k,i=strlen(a),j=strlen(b),c[N][N]; k=lcs_len(a,b,c); s[k]=’\\0’; while(k>0){ if(c[i][j]=

=c[i-1][j]) i--; else if(c[i][j]= =c[i][j-1]) j--; else{ s[--k]=a[i-1]; i--,j--; } } return s; } 18、假设有7个物品,它们的重量和价值如下表所示。若这些物品均不能被分割,且背包容量M=150,使用回溯方法求解此背包问题,请写出状态空间搜索树。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 解:按照单位效益从大到小依次排列这7个物品为:FBGDECA。将它们的序号分别记为1~7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下