吃糖果

题目 吃糖果

思路分析

斐波那契数列的一个应用。对于给定的N块巧克力，名名可以选择在第一天吃1块或2块，剩下的巧克力可以按照同样的方式继续选择。因此，如果我们将吃掉N块巧克力的方案数定义为F(N)，那么可以得到：

• 当N = 1时，有F(1) = 1种方案。
• 当N = 2时，有F(2) = 2种方案（第一天吃1块，第二天吃1块；或者第一天吃2块）。
• 对于N > 2，名名第一天有两种选择：
• 如果第一天吃1块，剩下N-1块，有F(N-1)种方案。
• 如果第一天吃2块，剩下N-2块，有F(N-2)种方案。

因此，对于N > 2，有F(N) = F(N-1) + F(N-2)。

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N = 1001;

int fn[N];

int n;

int main() {

    cin >> n;

    fn[1] = 1;

    fn[2] = 2;

    for(int i = 3; i <= n; i++)

        fn[i] = fn[i-1] + fn[i-2];

    cout << fn[n] << endl;

    return 0;

}

#include<bits/stdc++.h>

using namespace std;

int n;

int main()

{

    cin>>n;

    int a,b,fn;

    a=1,b=2;

    for(int i=1;i<=n;i++){

        if(i==n)

            cout<<a<<endl;

        fn=a+b;

        a=b,b=fn;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 递归与递推模型 🏠 00-刷题理模型 ➡️ 圆圈中最后剩下的数字