常用算法模板 2

素数筛打表

for(i=2;i<=1000;i++) prime[i]=1;
for(i=2;i*i<=1000;i++){
	if(prime[i]){
		for(j=i*i;j<=1000;j+=i) prime[j]=0;
	}
}

二叉树的静态链表存储

typedef struct{
    int data;
    int lchild,rchild;
}treenode;
treenode BSTstandard[123];

在此情况下判断两棵树是否相等

bool isSameTree(treenode *p,int root1,treenode *q,int root2)
{
    if(p[root1].data==0&&q[root2].data==0) return true;
    else if(p[root1].data==0||q[root2].data==0) return false;
    else if(p[root1].data != q[root2].data) return false;
    else return isSameTree(p,p[root1].lchild,q,q[root2].lchild) && isSameTree(p,p[root1].rchild,q,q[root2].rchild);
}

矩阵快速幂求斐波那契数列

设  为斐波那契数列第 n 项

利用矩阵乘法，可以得出

又因为

所以上式化为

而   

根据数学归纳法，有

由于矩阵的乘法满足结合律，矩阵的幂也满足，

可以套用我之前讲过的快速幂的方法，时间复杂度可以降低到，

比常规的递推求斐波那契数列更快。