第三章 作业答案

3．

void GetNext(char T[ ], int next[ ])

{

next[1]=0;

next[2]=1;

j=T[0],k=0;

for(;j>2;j--){

for(n=j-2;n>=1;n--){//n为要比较的前缀的最后一个字符的下标

m=j-n;//m为要比较的后缀的第一个字符的下标

for(i=1;i<=n;i++)

{

if(T[i]!=T[m+i-1])break;

}

if(i==n+1){next[j]=n+1;break;}

}

if(n==0)next[j]=1;

}

}

4．解：BF算法：

第一趟 a b a b c a b c c a b c c a c b a b

a b c

第二趟 a b a b c a b c c a b c c a c b a b

a

第三趟 a b a b c a b c c a b c c a c b a b

a b c c

第四趟 a b a b c a b c c a b c c a c b a b

a

第五趟 a b a b c a b c c a b c c a c b a b

a

第六趟 a b a b c a b c c a b c c a c b a b

a b c c a c

第七趟 a b a b c a b c c a b c c a c b a b

a

第八趟 a b a b c a b c c a b c c a c b a b

a

第九趟 a b a b c a b c c a b c c a c b a b

a

第十趟 a b a b c a b c c a b c c a c b a b

a b c c a c

由此可知，用BF算法一共要进行3+1+4+1+1+6+1+1+1+6=25次比较方能匹配出

KMP算法：next[]={,0,1,1,1,1,2};

第一趟 a b a b c a b c c a b c c a c b a b

a b c

第二趟 a b a b c a b c c a b c c a c b a b

a b c c

第三趟 a b a b c a b c c a b c c a c b a b

a b c c a c

第四趟 a b a b c a b c c a b c c a c b a b

a b c c a c

由此可知，用KMP算法一共要进行3+4+6+5=18次比较方能匹配出

6. 参考代码如下：

排列最终存储在长度为n的阶乘，元素类型为指针的数组中，数组指向一个排列，具体的排列数据存储在数组中。

int fabs(int n)

{

int r=1;

for(int i=n;i>1;i--)

r=r*i;

return r;

}

//排列存储在数组中

void getArrangement(int* *&s,int n)

{

int * p,*q;

int * *s1;

int i,j,k,l,m,o;

s=new int *[1];

s[0]=new int[1];

s[0][0]=1;

for(i=2;i<=n;i++)

{

j=0;

o=0;

m=fabs(i-1);

s1=new int *[fabs(i)];

while(o

{

q=p=s[o];

for(k=i-1;k>=0;k--)

{

s1[j]=new int[i];

for(l=0;l

{

if(l==k){s1[j][l]=i;}

else {

s1[j][l]=*p;

p++;}

}

j++;

p=q;

}

o++;

delete[] q;

}

delete[] s;

s=s1;

}

}

8、

点集合中最左边或者最右边的点一定是凸包的一个极点，则求凸包的极点的问题转化为求点的x坐标最大或最小的点

int getPole(int x[],int y[],int n)

{

int r=0;

for(int i=0;i

{

if(x[i]>x[r])r=i;

}

return r;

}

11、

两种思路：

1、 生成所有的组合，在组合中找元素个数为k个的组合。

伪代码：

1．初始化一个长度为n的比特串s=00…0并将对应的子集输出；

2．for (i=1; i<2n; i++) //注意不能书写成i<=2n

2.1 s++；

2.2 判断s中1的个数，若为k，则将s对应的子集输出；

2、 使用k层嵌套循环生成元素个数为k个的组合。

设k=3；n个元素存储在数组a[]中；

伪代码：

for (i=1; i

for (j=i+1; i

for (k=j+1; i

输出a[i]a[j]a[k]构成的组合。

13.

参考代码：

#include

#include

int main()

{

long i,j,k,m;

for (i=1; i <=711/4 ; i++)

{

for (j=i; j <=711/3 ; j++)

{

for (k=j; k <=711/2 ; k++)

{

m=711-i-j-k;

if (i*j*k*m==711*1000000)

{

cout<

}

}

}

}

return 0;

}

输出结果为：价格分别是1.2 1.25 1.5 3.16