n拆分为斐波那契数

正整数n,n<1e8, 将n拆分为若干个不重复的斐波那契数的和,输出有多少种拆分方法

#include <iostream>
#include <cstdio>

using namespace std;

//2021-3-19

const int MAXN = 38;       //Fibo[37] = 63245986,1e以下最大的斐波那契数

int Fibo[MAXN];
int answer;

void GetFibo() {
    Fibo[0] = 1;
    Fibo[1] = 2;
    for (int i = 2; i < MAXN; ++i) {
        Fibo[i] = Fibo[i - 1] + Fibo[i - 2];
    }
}

void DFS(int n, int pos) {      //n为待拆分数,pos为待处理Fibo位置
    if (n == 0) {
        answer++;
        return;
    }
    if (pos < 0) {
        return;
    }
    while (Fibo[pos] > n) {
        pos--;
    }
    DFS(n - Fibo[pos], pos - 1);
    DFS(n, pos - 1);
    return;
}

int main() {
    GetFibo();
    int n;
    while (scanf("%d", &n) != EOF) {
        answer = 0;
        DFS(n, 37);
        printf("%d\n", answer);
    }
    return 0;
}
全部评论

相关推荐

头像
03-05 09:50
C++
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务