题解 P1720 【月落乌啼算钱】

这题是一个求斐波那契数列的题。

提供5种解法。

解法1

递归。

代码

cpp

#include <bits/stdc++.h>
using namespace std;
long long f(int n) {
    if(n == 1||n == 2)return 1;
    return f(n - 1) + f(n - 2);
}

int main() {
    int n;
    cin >> n;
    cout << f(n) <<".00"<< endl;
    return 0;
}

可是，超时。

在洛谷，似乎没有无限栈，还爆空间了。

那么，有什么办法可以解决这个问题呢？

于是，就有了解法2.

解法2

可以记录已经算过的值，避免重复计算，大大提升效率。

代码

cpp

#include <bits/stdc++.h>
using namespace std;
long long fa[100] = { 0, 1, 1 };//前几个写进去
long long f(int n) {
    if (!fa[n]) {//算过的直接返回，没算过的计算
        fa[n] = f(n - 1) + f(n - 2);
    }
    return fa[n];
}

int main() {
    int n;
    cin >> n;
    cout << f(n) <<".00"<< endl;
    return 0;
}

但是，WA，80.

为什么呢？

问题出在if (!fa[n])这边。当输入是0时，$f(0)=0$,因此会又递归，所以WA了。

那么，应该加个特判，或用其他方法解决问题，代码这里不贴了，大家自己想想吧。

但是，有没有更好理解的办法呢？

解法3

递推。

代码

cpp

#include <bits/stdc++.h>
using namespace std;
int f[50] = { 0, 1, 1 };
int main() {
    int n;
    cin >> n;
    for (int i = 3; i <= n; ++i) {
        f[i] = f[i - 1] + f[i - 2];//按照斐波那契的公式算。
    }
    cout << f[n] << ".00";
    return 0;
}

额外提供两种解法。

解法4

三变量法。

cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
	long long a,b,c=0,num=0;
	cin>>num;
	a=b=1;//初始值为1
	for(int i=3;i<=num;++i){
		c=b+a;//算第个数
		a=b;//b的值赋给a
		b=c;//c的值赋给b 
	} 
	cout<<c<<".00";
	return 0;
}

能理解的尽量理解吧。

解法5

公式法。