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;
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议