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