斐波那契数列
解法
用数组来一个一个寸
为什么不用递归？
递归层数太多，容易爆栈
系统栈：2mb
一般的递归层数：2 * \(10^4\)
//正常解法
for(int i = 3; i <= n; i++)
a[i] = a[i - 1] + a[i - 2];
时间复杂度：O(n).
//递归解法
int f(int x)
{
if(x == 1 || x == 2)
return 1;
return f(x - 1) + f(x - 2);
}
f(10)
| |
f(9) f(8)
| | | |
f(8) f(7) f(7) f(6)
......
会计算多次一个值
pow的误差
pow有浮点数的差，最好直接乘。
P9825 [ICPC2020 Shanghai R] Fibonacci
选取两个数字，假装现在斐波那契数列之中是偶数的有x个，\(x=floor(n/3)\)。
如果选取的两个数字，没有顺序关系，\(x*(x-1)\)。
有顺序，\(x(x-1)/2\)。解释：每位同学都需要找其他同学握手\(x-1\)，总共有x名同学，一共需要\(x(x-1)\)。
//重要代码
ll n=x/3;
cout<<n*(x-n)+n*(n-1)/2<<'\n';