栈
一、Ackerman函数
Ackerman函数有$A(n,m)$有两个独立的整变量$m\ge0,n\ge0$,其定义如下
$A(1,0)=2$
$A(0,m)=1 ,m\ge0$
$A(n,0)=n+2, n\ge2$
$A(n,m)=A(A(n-1,m),m-1), n\ge1且m\ge1$
根据定义式可以简单地写出它的递归代码:
int Ackerman(int n,int m){
if(n<0 || m<0)return -1; //无定义
if(n==1 && m==0)return 2;
if(n==0)return 1;
if(m==0)return n+2;
return Ackerman(Ackerman(n-1,m),m-1);
}
字符串
一、子串定位:KMP算法
1、算法思路
定义主串串为目标串S,子串为模式串P。在朴素模式匹配算法中,每次匹配不成功之后,模式串只是向后移动1位,即存在大量回溯;我们可以利用部分匹配的结果,让模式串在不匹配时可以往后移动尽量远的距离,减少匹配次数。
KMP算法只针对模式串进行分析,对模式串求出数组Next[j],在模式串第j位比较失败之后利用Next[j]得到往后移几位。
Next数组的实质是找模式串中的最长相同的前缀和后缀(前缀不包括最后一个字符,后缀不包括第一个字符),实际意义为k=模式串第j位前的子串最长相同的前缀和后缀的长度+1,即将子串移动至第k位再次进行比较,如图所示。
\(Next[j] =\begin{cases}
0, j=1时 \\
Max \{ k | 1<k<j \ and\ p_1p_2…p_{k-1}= p_{j-k+1}…p_{j-1} \} \\
1,其它情况
\end{cases}\)
j | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
S | a | b | a | c | a | b | c |
Next[j] | 0 | 1 | 1 | 2 | 1 | 2 | 3 |
NextVal[j] | 0 | 1 | 0 | 2 | 0 | 1 | 3 |
根据上式,假设我们已经求出了next[j]数组,再将下标j按照C++的规则从0开始,就可以得到KMP算法的基本代码:
int KMP(string s,string t){
int i=0,j=0;
int n=s.size(),m=t.size();
while(i<n && j<m){
if(j==-1 || s[i]==t[j]){
i++;
j++;
}
else{
j=next[j];
}
}
if(j==m)return i-j;
else return -1;
}
2、Next数组
我们的代码依赖了数组next[j],next数组的定义上面已经说明,但它的求法更加精妙,首先我们贴出它的代码:
/*
这个算法得出的next[i]为最长前后缀的长度,即代表最长前缀的下一个字符的位置
*/
void getNext(string s){
next[0]=-1;
next[1]=0;
int i=2;//i代表填充next数组的i位置
int cn=0;//cn始终代表字符串i-1位置前面的字符串的最长前缀的下一个字符的位置
while (i<s.size()){
if(s[i-1]==s[cn])//如果字符串i-1位置上的字符等于字符串cn位置上的字符的话,直接在next[i]的基础上加1即可
next[i++]=++cn;
else if(cn>0)//这个条件满足,说明可以往前跳,让cn往前跳
cn=next[cn];
else
next[i++]=0;//字符串i位置前面的字符串没有前缀
}
}
以abacabc为例:
- next[0]=-1
- next[1]=0
- i=2,cn=0,s[1]!=s[0],且cn==0,next[2]=0
- i=3,cn=0,s[2]==s[0],next[3]=++cn=1
- i=4,cn=1,s[3]!=s[1],且cn>0,cn=next[1]=0,重复一次循环,i=4,cn=0,s[3]!=s[0],next[4]=0
- i=5,cn=0,s[4]==s[0],next[4]=++cn=1
- i=6,cn=0,s[5]==s[0],next[5]=++cn=2
比较难理解的为cn=next[cn]
这段代码,实际为将当前前缀长度跳回到cn这一字符的最长前缀,由于next[cn]的前后缀必相同,只需继续再次比较cn与i-1的字符即可,如图:
3、NextVal数组
观察s[4],当它不匹配时,按照next行回溯到s[1]也为字母a,这时再匹配a是徒劳的,因为已知a不匹配,所以就继续退回到s[1]字母a的next[1]=0。为了进行优化,就有了nextval:
若要求nextval[i],将next[i]的值对应的位的值与i的值进行比较: 若相等,nextval[i]=nextval[ next[i] ]; 若不相等,则nextval[i]=next[i]。
代码如下:
int get_nextval(string T){
//求模式串T的next函数修正值并存入数组nextval。
for(int i=1;i<T.size();i++){
if(T[next[i]] == T[i])
nextval[i]=nextval[next[i]];
else nextval[i]=next[i];
}
}//get_nextval
数组
一、快速转置算法
1、稀疏矩阵的三元组存储
矩阵本身的数据:行、列、元素个数
矩阵元素的数据:行序号、列序号、元素值
struct Triple{
int I,j;
elementtype e;
}; //矩阵元素
struct TSMatrix{
Triple data[Max+1];
int mu,nu,tu;
}; //矩阵
而由于稀疏矩阵的数据排列是行对齐的(根据行的顺序排列),所以如果进行转置,需要重新对数据进行排列,快速转置则是在尽可能少次数地遍历矩阵的情况下完成转置。
2、算法思路
首先我们给出一个$5\times5$的稀疏矩阵:
数组data | 5/行 | 5/列 | 6/元素个数 |
---|---|---|---|
0 | 1 | 1 | 3 |
1 | 1 | 5 | 7 |
2 | 2 | 3 | -1 |
3 | 3 | 1 | -1 |
4 | 3 | 2 | -2 |
5 | 5 | 4 | 2 |
经过转置后,它的排列需要是这样:
数组data | 5/行 | 5/列 | 6/元素个数 |
---|---|---|---|
0 | 1 | 1 | 3 |
1 | 1 | 3 | -1 |
2 | 2 | 3 | -2 |
3 | 3 | 2 | -1 |
4 | 4 | 5 | 2 |
5 | 5 | 1 | 7 |
为了预先确定矩阵M中的每一列的第一个非零元素在数组中的位置,需要先求得矩阵M中的每一列中非零元素的个数。为此,需要设置两个一维数组num[n]和cpot[n],其中n为矩阵列数。
-
num[]:储存每一列非零元素的个数
-
cpot[]:储存每一列的第一个非零元素在数组中的位置
通过这两个数组,我们可以在仅遍历数组两次的情况下完成矩阵的转置:
- 在第一次遍历时,通过对列的遍历,我们可以得到num[]。
- cpot[1]=0 cpot[col]=cpot[col-1]+num[col-1]
- 第二次遍历即可根据cpot开始元素的转置:每读取一个元素,若列为i,则将行列调换,放入新的data[cpot[data[i].j]]]之中,并将cpot[i]+1。
- 完成第二次遍历,完成算法。
3、代码实现
TSMatrix trans(TSMatrix mat){
TSMatrix nmat;
nmat.mu=mat.nu;
nmat.nu=mat.mu;
nmat.tu=mat.tu;
int num[10]={0};
int cpot[mat.nu];
for(int i=0;i<mat.tu;i++){
num[mat.data[i].j]++;
}
cpot[0]=0;
for(int i=1;i<mat.nu;i++){
cpot[i]=cpot[i-1]+num[i-1];
}
for(int i=0;i<mat.tu;i++){
nmat.data[cpot[mat.data[i].j]].I=mat.data[i].j;
nmat.data[cpot[mat.data[i].j]].j=mat.data[i].I;
nmat.data[cpot[mat.data[i].j]].e=mat.data[i].e;
cpot[mat.data[i].j]++;
}
return nmat;
}
二、求杨辉三角系数
1、数学模型
杨辉三角是二项式系数在三角形中的一种几何排列,即我们熟知的二项式系数$(a+b)^n=C^0_na^n+C^1_na^{n-1}b^1+\dots+C^n_nb^n$中的$C^k_n$。
如图,对于n次二项式,设第一行为n=0的系数,则n次二项式共有n+1个系数,设为0~n。
那么,我们可以发现,对于每一个n,$a_n[0]=a_n[n]=1$,且对于$0<k<n$,$a_n[k]=a_{n-1}[k-1]+a_{n-1}[k]$。
2、代码实现
这样一来,建立一个数组进行递归计算,可以简单的求出n次二项式的二次项系数。
void coff(int *a,int n){ //arr的大小为n+1
if(n==1){
a[0]=a[1]=1;
}
else{
coff(a,n-1);
a[n]=1;
for(int i=n-1;i>0;i--){ //从最后一个开始,可以直接修改数组内容且不影响计算
a[i]=a[i]+a[i-1];
}
}
}
3、测试函数
#define N 10
int arr[N+1];
int main()
{
coff(arr,N);
for(int i=0;i<=N;i++){
cout<<arr[i]<<endl;
}
return 0;
}