1350 斐波那契表示 题目来源： Project Euler 基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注 每一个正整数都可以表示为若干个斐波那契数的和，一个整数可能存在多种不同的表示方法，例如：14 = 13 + 1 = 8 + 5 + 1，其中13 + 1是最短的表示（只用了2个斐波那契数）。定义F(n) = n的最短表示中的数字个数，F(14) = 2，F(100) = 3（100 = 3 + 8 + 89），F(16) = 2（16 = 8 + 8 = 13 + 3）。定义G(n) = F(1) + F(2) + F(3) + ...... F(n)，G(6) = 1 + 1 + 1 + 2 + 1 + 2 = 8。给出若干个数字n，求对应的G(n)。 Input 第1行：一个数T，表示后面用作输入测试的数的数量（1 <= T <= 50000)。 第2 - T + 1行：每行1个数n(1 <= n <= 10^17)。 Output 输出共T行：对应每组数据G(n)的值。 Input示例 3 1 3 6 Output示例 1 3 8
找规律
F(n)：1,1,2,1,2,2,1,2,2,2,3,1,2,2,2,3,2,3,3,1,2,2,2,3,2,3,3,2,3,3,3,4
#include<stdio.h> using namespace std; #define LL long long LL n, fib[1005] = {0,1,1}, w[1005] = {0,1,1}; LL p(int i, LL j) { if(j==fib[i]) return w[i]; if(j<=fib[i-1]) return p(i-1, j); return p(i-1, fib[i-1])+p(i-2, j-fib[i-1])+j-fib[i-1]; } int main(void) { int T, i, id; LL sum, ans; for(i=3;i<=84;i++) { fib[i] = fib[i-1]+fib[i-2]; w[i] = w[i-1]+w[i-2]+fib[i-2]; //printf("%lld\n", w[i]); } scanf("%d", &T); while(T--) { sum = ans = 0; scanf("%I64d", &n); for(id=1;sum+fib[id]<n;id++) sum += fib[id]; for(i=1;i<=id-1;i++) ans += w[i]; ans += p(id+1, n-sum); printf("%I64d\n", ans); } return 0; }
