题目描述
知道斐波那契数吗？下面是它的一个定义： F1 = 1 F2 = 2 Fn+1 = Fn+Fn-1 ，这里n>1
每个正整数x 可写为不同斐波那契数的总和，因而意味着存在数k 和数 b1, b2, …, bk，使得x=b1*F1+ …+ bi*Fi+ … +bk*Fk, 其中bk = 1，bi (1≤i < k)为0或1。简言之，我们可写为： b(x) = (bk, bk-1, …, b1)。 为使表示唯一，我们要求对所有i > 1，bi * bi-1 = 0。 利用斐波那契数，我们可以将公里单位距离 x 转换为相应的英里单位距离 y，首先，以斐波那契系统表示b(x)写下x。其次，将b(x)中数字右移一位（最后一位删除），得到b(y)。第三，从b(y)中计算总数来算出 y。 例如，，数42以斐波那契系统表示为：(1,0,0,1,0,0,0,0)。第二步，我们通过右移得到 (1,0,0,1,0,0,0)。第三步，我们计算0*1 + 0*2 + 0*3 + 1*5 + 0*8 + 0*13 + 1*21 = 26. 下面请你写一个程序，根据上述算法将公里转换为英里。
输入
输入第一行包含t，需要转换的距离数目 (0
输出
对于每个距离x 公里，输出算出的y 英里。
样例输入
5 42 100 180 300 360
样例输出
26 62 111 185 222
思路
模拟….本来想直接拿换算公式过来套，发现和题目有误差 = = 大水题
代码;const int maxn = 23;int f[maxn];int n;bool used[maxn];int main(){f[1] = 1; f[2] = 2;for(int i = 3 ; i < maxn ; i ++) f[i] = f[i-1]+f[i-2];int t;scanf(“%d”,&t);while(t–) {scanf(“%d”,&n);int pt;fill(used,used+maxn,false);for(pt = 1 ; pt < maxn ; pt ++) {if(f[pt] > n) break;}used[pt-1] = true;int tmp = f[pt-1];for(int i = pt-2 ; i >= 1 ; i –) {if(tmp == n) break;if(used[i+1]) {continue;}else {if(f[i]+tmp <= n) {tmp += f[i];used[i] = true;}}}int ans = 0;for(int i = 2 ; i < maxn ; i ++) {if(used[i]) ans += f[i-1];}printf(“%d\n”,ans);}return 0;}
做自己的决定。然后准备好承担后果。
