算法与分析平时作业-答案

平时作业

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、0(1)空间子数组环卫算法：设a[0:n-1]是一个n维数组，k ( K k < n-1 )是一个非负

整数。试设计一个算法将子数组a[0 : k-1] 与a[k+1 : n-1] 换位。要求算法在最坏情况下耗时0(n),

且只用0(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) 次。

代价分析：时间代价 --- 0((n-1)*(n-k+1)) 即0(n A2)数量级；空间代价： 0 (1)

3、定义：给定一个自然数 n,由n开始依次产生半数集set(n)中的元素如下：

1 ) n set(n) ；

2 )在 n 的左边加上一个自然数,但该自然数不能超过最近添加的数的一半；

3 )按此规则进行处理,直至不能再添加新的自然数为止。

例如set(n) {6,16,26,126,36,136} 。其中共有 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(s

tmp=R[s];

while(i!=j) { while(j>i&&R[j]>=tmp) j--; R[i]=R[j]; while(i

R[j]=R[i];

}

R[i]=tmp;

QuickSort(R,s,i-1);

QuickSort(R,i+1,t);