第三章作业答案
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 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
由此可知，用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; ifor (j=i+1; ifor (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++)
