0
已解决
新手天翼
3501 整数的分解--斐波拉契经验值：1600
题目描述 Description
已知任意一个正整数都可以拆分为若干个斐波拉契数之和，让你求出n的拆分方法。
输入描述 Input Description
一个数t，表示有t组数据
接下来t行，每行一个数n
输出描述 Output Description
t行，每行一个字符串，表示拆分方法（格式:n=a1+a2+a3+…+an），要求从小到大输出
样例输入 Sample Input
1 10
样例输出 Sample Output
10=2+8
数据范围及提示 Data Size & Hint
若有多组数据，以个数最小的为准，若仍有多组，输出右边尽量大的一组
对于100%的数据 t<=1000 1<=n<=10^9
求大佬思路
0
已采纳
高级守护
- #include <stdio.h> #include <string.h> int main() { int a[50], b[50] = {0}, i, x, y, cnt, n, t; a[1] = 1, a[2] = 1; for (i = 3; i <= 45; i++) a[i] = a[i - 1] + a[i - 2]; scanf("%d", &n); while (n--) { cnt = 0; scanf("%d", &t); x = t; memset(b, 0, sizeof(b)); (while循环)(t > 0) { for (y 等于 45; y 大于 0; y--) { if (a[y] <= t) { 计数++; b[cnt]=a[y]; t=t-a[y]; } } } printf("%d=",x); for(cnt;cnt>0;cnt--) { if(计数==1) printf("%d\n",b[cnt]); else printf("%d+",b[cnt]); } } return 0; }
0
中级启示者
贪心思路：从最大的fibonacci数开始选
能选就一直选，直到选不了了
从小到大输出，可以通过stack来实现
0
新手启示者
stack
0
中级天翼
贪心
0
新手天翼
ding
0
缔造者
stack,贪心结合
0
高级守护
stack和贪心结合即可。
0
高级守护
顶
