（本题取 $n=\lfloor \text{fib}^{-1}(4000000) \rfloor=33$）
【思路】运用斐波那契数列递推公式 $a_i=a_{i-1}+a_{i-2}$ 进行递推，超过 $4000000$ 就中断。最后统计其中偶数的和即可。时空复杂度均为 $\mathcal O(n)$。
【优化 $1$】采用滚动变量，将空间复杂度优化到 $\mathcal O(1)$：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<stdio.h>
#include<stdbool.h>
int last,now,ans;
int main()
{
last=now=1;
while(true)
{
int t=last;
last=now;
now+=t;
if(now>4000000)break;
if(now%2==0)ans+=now;
}
printf("%d",ans);
return 0;
}
|
【优化 $2$】采用矩阵乘法，构造初始矩阵为：
$$\begin{bmatrix}
1 & 1 \cr
0 & 0 \cr
\end{bmatrix}$$
每次需要乘上的矩阵为：
$$\begin{bmatrix}
1 & 1 \cr
1 & 0 \cr
\end{bmatrix}$$
这样不停地累乘，只要矩阵第 $1$ 行第 $1$ 列的元素（即数列的值）超过 $4000000$，就直接中断：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<bits/stdc++.h>
int ans;
struct matrix
{
long long a[3][3];
matrix operator*(const matrix &x)const
{
matrix res;
memset(res.a,0,sizeof(res.a));
for(int k=1;k<=2;++k)
{
for(int i=1;i<=2;++i)
{
for(int j=1;j<=2;++j)
{
res.a[i][j]+=a[i][k]*x.a[k][j];
}
}
}
return res;
}
}m,base;
int main()
{
m.a[1][1]=m.a[1][2]=1;
base.a[1][1]=base.a[1][2]=base.a[2][1]=1;
while(m.a[1][1]<=4000000)
{
if(m.a[1][1]%2==0)ans+=m.a[1][1];
m=m*base;
}
printf("%d",ans);
return 0;
}
|
做一次矩阵乘法的时间复杂度为 $\mathcal O(1)$，需要做 $n$ 次，因此时间复杂度仍为 $\mathcal O(n)$。矩阵的大小为常数，因此空间复杂度为 $\mathcal O(1)$。
由于没有要求具体求出数列中一个元素的值，因此矩阵并没有真正起到优化作用。