算法与分析平时作业答案.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
#include
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 #define m 10
//快速排序
void QuickSort(int R[],int s,int t) {
int i=s,j=t; int tmp;
if(si&&R[j]>=tmp) j--;
R[i]=R[j];
while(ij=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<>d;
cout<<"请输入元素"<>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<<"最长单调递增子序列为："<
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<<"输入待安排活动数:"<>k;
cout<<"输入待安排活动开始时间和结束时间:"<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;ncout<<"输出最少会场数:\n"<
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，即。
答：
#includeh>
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
}
Back(0,0);
if(d) printf("no solution\n");
for(j=0;jn)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 j=0;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
当 i1}，其中使计算量最小那个位置 为最优解，数乘次数 m[i,j]最小值为问题最优值能够递归地定义 m[i,j]为：
ｍ［ｉ，ｊ］= { min｛ｍ[i，k] + 0ｍ[k +1, j] +ｐi-1ｐkｐj ｝i=ji计算。在计算 过程中，保留已处理子问题答案。每个子问题只计算一次，而在后面需要时只 要简单查一下，从而防止大量重复计算最终得到多项式时间算法 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 #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;iile(1) { scanf("%d%f",&n,&cu); if(n