算法设计与分析复习题(5)

{

int sum[money+1]; sum[0]=0;

for (int i=1;i<=money;i++) sum[i]=-1;

for (int i=1;i<=money;i++) {

for(int j=0;j

if(i-a[j]>=0) {

if(sum[i-a[j]]==-1) // continue; if(sum[i]==-1)

sum[i]=sum[i-a[j]]+1; else

sum[i]=(sum[i]>sum[i-a[j]]+1)?sum[i-a[j]]+1:sum[i];

//最优解为本身或者sum[i-a[j]]+1 } }

if(sum[money]==-1) return -1; else

return sum[money]; }

}

22、 考虑一个“模糊”的算法查找T的子串P，先快速找到与P相似的子串，再

进一步确认之。

int new_get_index(char *T,char *P) {

int a,b,c;

a=0;b=strlen(p);c=(a+b)/2; int k=0; while(){

if(P[a]!=T[k+a]||P[b]!=T[k+b]||P[c]!=T[k+c]){k++;continue;} for(int j=0;j

} }

23、 设计一个算法确定K个矩阵相乘的最优次序，并分析该算法的时间复杂性。

int dynamic_cross(int i,int j,int m[M][M],int p[M][3]) { if(i==j) { }

for(int k=i;k

m[i][k]=dynamic_cross(i,k,m,p); m[k+1][j]=dynamic_cross(k+1,j,m,p);

int sum=m[i][k]+m[k+1][j]+p[i][0]*p[k][1]*p[j][1]; if(sum

if(j==b)return k;

}

m[i][j]=sum;

return m[i][j]; }

24、 设计一个算法从数A[1：n]中同时找出最大元素和最小元素，只需要不超过

1．5n－2次比较。

void divid(int abegin,int aend,double & maxd,double & mind,double a[]) {

if(aend-abegin<=1) //规模足够小的时候，直接2个数比较 { }

int mid=(abegin+aend)/2; //二分处理 divid(abegin,mid,maxd,mind,a); divid(mid+1,aend,maxd,mind,a);

if(a[abegin]

if(a[aend]

mind=a[aend]; if(a[abegin]>maxd)

if(a[aend]>maxd) maxd=a[aend]; if(a[abegin]

maxd=a[abegin]; }

return ; //关键 一定要退出了 因为已经是递归出口

}

25、 用分治法一个算法从数A[1：n]中同时找出最大元素，分析算法的时间复杂

性，并思考为什么是这样的结果。

采用分治法 T（n）=2T（n/2）+2 T（2）=1 解这递归方程 得 T（n）=1.5n-2 得到优化。

26、 在一个数组中出现次数最多的元素称为“众数”，编写一个找出众数的算法，

并分析算法时间复杂性。

先排序，然后遍历一遍寻找最长的相同元素序列。算法默认出现2次及2次以上才为众数。快排时间复杂度为O(nlogn)，遍历一遍复杂度为O(n)，故算法总时间复杂度为O(nlogn) int number(Array, Len) { //快排

QSort(Array, Len); max=1;num=-1; i=0;j=1 while(i

//遍历 找最长的相同元素序列 while((jmax) { max=j-i; num=Array[i]; } i=j; j=i+1 }

return num; }

27、 设计一个使用Hash法的算法在数组中找出“众数”，并分析时间复杂性。

Hash的方法很关键，不知道有什么简单的方法??这里假设数组中数据范围为0~max，max为数组中最大元素，先找到max，确定了Hash的范围，再使用一对一Hash(direct addressing)。时间复杂性为O(n)（查找最大元时间复杂度为O(n)，遍历一遍数组为O(n)，Hash的时间复杂度为O(1)，故算法时间复杂度为O(n)，当然这里使用的方法受限制极强，不是通用的解答，时间复杂度也不可能有这么好，但是代码容易编写与理解）

//Hash函数 有点假 hash(Brray, i) { Brray[i]++; } //返回-1则未找到众数 默认出现2次及2次以上才为众数 int number(Array, Len) { //找到最大数 max=find_max(Array, Len); //新建一个数组 Brray=new int[max+1]; //初始化其中数据为0 for(i=0;inax) { nax=Brray[i]; num=i; } } //删除Brray数组 delete[] Brray; //返回找到的众数