算法与分析平时作业答案.doc

平时作业
1、给定下述二分搜索算法，请判断算法正确性，指犯错误算法产生原因。
a) int BinarySearch(Type a[], const Type& x, int l, int r){
while (r >= l){
int m = (l+r)/2;
if (x == a[m]) return m;
if (x < a[m]) r = m-1;
else l = m+1;
}
return -1;
}
答：正确

b) int BinarySearch(Type a[], const Type& x, int l, int r){
while (r >= l){
int m = (l+r)/2;
if (x == a[m]) return m;
if (x < a[m]) r = m+1;
else l = m-1;
}
return -1;
}
答：错误
if (x < a[m]) r = m+1; 当查找元素在中间元素左边时，右指针应该为m-1位置，修改成if (x < a[m]) r = m+1; else l = m+l

c) int BinarySearch(Type a[], const Type& x, int l, int r){
while (r > l){
int m = (l+r)/2;
if (x == a[m]) return m;
if (x < a[m]) r = m-1;
else l = m+1;
}
return -1;
}
答：错误。
while (r > l) 要考虑到 数组只有一个元素情况 所以应该是 r>=l ;

2、O(1)空间子数组环卫算法：设a[0:n-1]是一个n维数组，k（1≤ k ≤n-1）是一个非负整数。试设计一个算法将子数组a[0 : k-1]与a[k+1 : n-1]换位。要求算法在最坏情况下耗时O(n)，且只用O(1)辅助空间。
答：最简单方法就是循环(n-k-1)次，将a数组末尾数字插入到a[0]之前。
详细做法：
(1) 首先开辟一个额外空间temp用于存放每一次a数组末尾数据。
(2) temp <- a[n-1]
(3) 将a[0: n-2] 每个数据都依次向后移动一位赋值给a[1: n-1]。
(4) a[0] <- temp
(5) 循环执行(2) -(4) 步 (n-k+1)次。
代价分析： 时间代价—— O((n-1)*(n-k+1)) 即O(n^2)数量级；空间代价： O（1）
3、定义： 给定一个自然数n，由n开始依次产生半数集set(n)中元素以下：
1）；
2）在n左边加上一个自然数，但该自然数不能超出最近添加数二分之一；
3）按此规则进行处理，直至不能再添加新自然数为止。
比如 。其中共有6个元素。
半数集问题：对于给定n，求半数集set(n) 中元素个数。
答：半数集set(n)中元素个数求解是个递归过程。设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<stdio.h>
#include<stdlib.h>
int main(){
int n;
int i,j,s;
int buf[106];
char *in="input.txt",*out="output.txt";
FILE *ip,*op;
if((ip=fopen(in,"r"))==NULL)return 1;
if((op=fopen(out,"w"))==NULL)return 2;
fscanf(ip,"%d",&n);
fclose(ip);
buf[1]=1;
buf[2]=2;
buf[3]=2;
for(i=4;i*2<=n;i++){
s=1;
for(j=1;j<=i/2;j++){
s+=buf[j];
}
buf[i]=s;
}
s=1;
for(j=1;j<=n/2;j++){
s+=buf[j];
}
fprintf(op,"%d",s);
fclose(op);
/* system("pause");*/
return 0;
}

4、设计一个算法，找出由n个数组成序列最长单调递增子序列长度。
答： #include<iostream.h> #define m 10
//快速排序
void QuickSort(int R[],int s,int t) {
int i=s,j=t; int tmp;
if(s<t) {
tmp=R[s];
while(i!=j) {
while(j>i&&R[j]>=tmp) j--;
R[i]=R[j];
while(i<j&&R[i]<=tmp) i++;
R[j]=R[i];
}
R[i]=tmp;
QuickSort(R,s,i-1);
QuickSort(R,i+1,t); }
}
//找出最长公共子序列
void LCSLength(int x[],int y[],int n,int c[m][m],int b[m][m]) {
int i,j; for(i=0;i<n;i++) {
c[0][i]=0; c[i][0]=0;
}
for(i=0;i<n;i++) for(j=0;j<n;j++) {
if(x[i]==y[j]) {
c[i][j]=c[i-1][j-1]+1; b[i][j]=1;
} else if(c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j];
b[i][j]=2;
} else {
c[i][j]=c[i][j-1]; b[i][j]=3;
}
}
}
void LCS(int i,int j,int *x,int b[m][m]) {
if(i<0||j<0) return; if(b[i][j]==1) {
LCS(i-1,j-1,x,b); cout<<x[i]<<" ";
} else if(b[i][j]==2) LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}
void main() {
int x[m],y[m],d;
cout<<"请输入元素个数"<<endl; cin>>d;
cout<<"请输入元素"<<endl;
for(int i=0;i<d;i++) {
cin>>x[i]; y[i]=x[i];
}
int c[m][m]={0},b[m][m]={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)。
答：
#include<iostream>
using namespace std;
#define M 50//最大活动数
struct Active {
int b;//开始时间
int f;//结束时间
int no;//预安排会场号
}a[M];
//两元素交换位置
void swap(Active &a,Active &b){
Active t=a; a=b; b=t;
}
void main(){
int k, i,j;
cout<<"输入待安排活动数:"<<endl;
cin>>k;
cout<<"输入待安排活动开始时间和结束时间:"<<endl; //输入活动时间
//活动时间排序
for(i=1;i<=k;i++) {
{ for(j=i;j<=k;j++) {
if(a[i].b>a[j].b) swap(a[i],a[j]);
if(a[i].b==a[j].b){
if(a[i].f>a[j].f) swap(a[i],a[j]);
}
}
}
int int sum=1;//使用会场数初始化
int n; a[1].no=sum;
for(i=2;i<=k;i++) {
for(n=1;n<i;n++) {
if(a[n].no!=0&&a[n].f<=a[i].b) {
a[i].no=a[n].no;
a[n].no=0;//已经安排过活动就不再比较 break;
}
}
if(n==i)
{
sum+=1; a[i].no=sum;
}
}
cout<<"输出最少会场数:\n"<<sum<<endl;
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) { 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 < n; i++) a[k - i]++;
}
7、子集和问题：设是n个正整数集合，c是一个正整数。那么是否存在S一个子集S1，使得子集中元素之和等于c，即。
答：
#include<stdio.h>
int n,c; int a[100];
int current[100]; //存放当前选择情况
int best[100]; //存放最终选择子集合，best[i]=1，表示包含，反之即不包含。
int d=1; //判断有没有满足情况
int d2=0; //是否已经选出子集和
void Back(int m,int count);
int main() {
int i,j;
scanf("%d %d",&n,&c);
for(i=0;i<n;i++) {
scanf("%d",&a[i]); current[i]=best[i]=0;
}
Back(0,0);
if(d) printf("no solution\n");
for(j=0;j<n;j++) //输出满足情况子集和
{
if(best[j]==1) printf("%d\t\t",a[j]);
}
}
void Back(int m,int count) {
int k; if(m>n)return;
if(count==c) {
d=0; //有满足子集和
if(d2) return 0;
for(k=0;k<=m;k++) best[k]=current[k];
d2=1; return 0;
} else {
current[m]=1; //选入子集和
count+=a[m];
Back(m+1,count);
current[m]=0; //不选入子集和
count=count-a[m]; Back(m+1,count);
}
}
8、设序列是序列和最长公共子序列。
a) 请说明最长公共子序列具备最优子结构性质。
b) 设c[i][j]统计序列i和最长公共子序列长度。由最长公共子序列问题最优子结构性质建立子问题最优值c[i][j]递归关系。
c) 写出寻找最长公共子序列算法。
答： 最长公共子序列问题具备最优子结构性质：
1、若 xm = yn ， 则 zk = xm = yn，且 Z[k-1] 是 X[m-1] 和 Y[n-1] 最长公共子序列
2、若 xm != yn ，且 zk != xm , 则 Z 是 X[m-1] 和 Y 最长公共子序列
3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 最长公共子序列 由性质导出子问题递归结构：
当 i = 0 , j = 0 时 , c[i][j] = 0
当 i , j > 0 xi = yi 时 , c[i][j] = c[i-1][j-1] + 1
当 i , j > 0 xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }
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 int[m+1][n+1];
b=new int[m+1][n+1];
for(int i=0;i<n+1;i++) {
c[0][i]=0;
}
for(int j=0;j<m+1;j++) {
c[j][0]=0;
}
}
public LSC() {}
public int LSCLength() {
for(int i=1;i<m+1;i++) {
for(int j=1;j<n+1;j++) { /
** 假如 A[i-1]和Ｂ[j-1]是相等话*/
if(A[i-1]==B[j-1]) {
c[i][j]=c[i-1][j-1]+1;
b[i][j]='0';
}
/* * 情况１ */
else if(c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; b[i][j]='1';
}
/* * 情况２ */
else {
c[i][j]=c[i][j-1]; b[i][j]='2';
}
}
}
return c[m][n];
}
public void print(int i,int j) {
if(i<=0||j<=0) { return; }
else if(b[i][j]=='0') {
print(i-1,j-1);
System.out.print(A[i-1]);
} else if(b[i][j]=='1') {
print(i-1,j);
} else {
print(i,j-1);
}
} public int LSCLength2(int i,int j) {
if(i<0||j<0) { return 0; }
else {
if(A[i]==B[j]) {
return 1+LSCLength2(i-1,j-1);
}
else {
int a1=LSCLength2(i,j-1);
int a2=LSCLength2(i-1,j);
return a1>a2?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、记矩阵连乘积 。 确定计算A[1:n]最优计算次序，使得所需数乘次数最少。
1、说明矩阵连乘计算次序问题最优解包含着其子问题最优解，即最优子结构性质。
2、该问题具备子问题重合性质。
3、说明采取动态规划方法能够处理该问题。
4、设计该算法，分析算法复杂性。
答：计算 A[i:j]最优次序所包含计算矩阵子链 A[i:k]和 A[k+1:j]次序也是最优。 设计算 A[i:j]，1≤i≤j≤n，所需要最少数乘次数 m[i,j]，则原问 题最优值为 m[1,n] 当 i=j 时，A[i:j]=Ai，无需计算，所以，m[i,j]=0，i=1,2,…,n
当 i<j 时，利用最优子结构性质计算 m[i,j] . 设 A[i:j]最优次序在 Ak 和 Ak＋1 之间断开，则
ｍ［ｉ，ｊ］＝ｍ［ｉ，ｋ］＋ｍ［ｋ＋１，ｊ］＋ｐi-1ｐkｐj
其中 Ai 维数为 pi-1×pj k 位置只有 j-i 种可能, {i, i+1, …, j-1}，其中使计算量最小那个位置 为最优解，数乘次数 m[i,j]最小值为问题最优值能够递归地定义 m[i,j]为：
ｍ［ｉ，ｊ］= { min｛ｍ[i，k] + 0ｍ[k +1, j] +ｐi-1ｐkｐj ｝i=ji<j }

将最优值 m[i j]对应断开位置记为 s[i j]，则可递归由 s[i j]结构出对应最优 解 对于 1≤i≤j≤n 不一样有序对(i,j)对应于不一样子问题。所以，不一样子问题 个数最多只有

由此可见，在递归计算时，许多子问题被重复计算数次。这也是该问题可用动态 规划算法求解又一显著特征。 用动态规划算法解此问题， 可依据其递归式以自底向上方式进行计算。在计算 过程中，保留已处理子问题答案。每个子问题只计算一次，而在后面需要时只 要简单查一下，从而防止大量重复计算最终得到多项式时间算法 matrixChain 已经统计了结构最优解所需全部信息。从 s[1][n] 可知，计算 A[1:n]最优加括号方式为 ( A[ 1 : s[1][n] ]) (A[s[1][n]+1: n] ) 计算 A[ 1 : s[1][n] ]最优加括号方式为 (A[ 1 : s[1][s[1][n] ] ])(A[ s[1][s[1][n] ]+1 : s[1][n] ])

10、考虑分数背包问题，定义以下：给出n 个大小为 s1, s2, …, sn , 价值为v1, v2, …, vn 物品， 并设背包容量为C, 要找到非负实数x1, x2, …, xn, 使和 在约束下最大。写出求解问题贪心算法，估量算法时间复杂性。
答：从问题某一初始解出发；while 能朝给定总目标前深入 do 求出可行解 一个解元素； 由全部解元素组合成问题一个可行解；从问题某一个初始解出 发逐步迫近给定目标， 以尽可能快地求得愈加好解。当达成某算法中某一 步不能再继续前进时，算法停顿。 #include <stdio.h> #define total 10 float p[total],w[total],t[total]; void greedy_knaPsack(int x,int c) { int note,i; float max; while(1) { note=0; max=0; for(i=0;i<x;i++) if((max<p[i]/w[i]) && (t[i]==0)) { max=p[i]/w[i]; note=i; } if(w[note]<c) { t[note]=1; c-=w[note]; } else { t[note]=c/w[note]; break; } } } int main() { int i=0,n=0; float cu; printf("请输入物品总数（小于%d）与背包容量：",total); while(1) { scanf("%d%f",&n,&cu); if(n<total) break; else printf("物品总数超出范围，请重新输入："); } printf("请输入每个物品价值与重量：\n"); for(i=0;i<n;i++) { scanf("%f%f",&p[i],&w[i]); t[i]=0; } greedy_knaPsack(n,cu); printf("由贪心算法所得最优解是：\n"); for(i=0;i<n;i++) printf("%f ",t[i]); return 0; } 时间复杂度分析： 算法中用到三个 for 循环，故计算时间复杂度： O(n)=n+n+n=3n 即此算法时间复杂度为： O(n)=n