本文共 1767 字，大约阅读时间需要 5 分钟。

题目描述

众所周知，Fibonacci 数列是从 0 和 1 开始，然后，将最后两个数字相加得到下一个数字；即 f(n)=f(n−1)+f(n−2)，n≥2。例如，数列中的第 2 个数字是 1（1＝1+0），第 3 个数字是 2（2＝1+1），第 4 个数字是 3（3＝2+1），依此类推。图 1 给出 Fibonacci 数列 n≤9 的情形。

图 1

Fibonacci 数列在我们生活中出现在许多事情上，有着重要的意义。所有的正整数都可以表示为 Fibonacci 数列中的数字的和；而且，对于每个正整数，存在若干个不同的集合，每个集合由 Fibonacci 数列中的数字组成，集合中的数字的和等于该正整数。例如：13 可以表示为集合 {13}，{5, 8} 或 {2, 3, 8} 中数字的和，17 可以表示为集合 {1, 3, 13} 或 {1, 3, 5, 8} 中的数字的和。

一个正整数可以表示成 Fibonacci 二进制数 an​an−1​…a2​，其数值为 an​×f(n)+an−1​×f(n−1)+……+a2​×f(2)，其中，an​=1，而 {

一个正整数可以有多个 Fibonacci 二进制数表达，例如，6=5+1=1001(fib)，而 6 又可以表示成 6=3+2+1=111(fib)。因为任何两个连续的 Fibonacci 数的和就是下一个的 Fibonacci 数。为此，本题设定在集合中不能有两个连续的 Fibonacci 数，即 Fibonacci 二进制数中没有连续的 1；这样，每个正整数就有一个唯一的 Fibonacci 二进制数表示。如上例，6 被唯一地被表示为 1001(fib)。再例如，17 = 100101 (fib)，如图 2 所示。

图 2

给出一个正整数的集合，请您将这些数表示成 Fibonacci 二进制数。

输入输出格式

输入格式 输入的第一行给出一个数字 n，表示后面的给出多少个正整数（1≤n≤500）。 然后给出 n 行，每行给出一个小于 100 000 000 的正整数。

输出格式 请您对输入中的 n 个整数中的每一个数输出一行，格式为 DEC BASE=FIB BASE(fib)，其中，DEC BASE 是给出的十进制的数，FIB BASE 是以 Fibonacci 二进制数表示的数字。请参见样例输出。

#include 
   
    using namespace std;int main(){    int f[40]={0, 1}, B[40], n, m, i; //f为斐波那契数列 b为二进制数的权值        for (int i = 2; i < 40; ++ i)//计算前40为的斐波那契数列         f[i] = f[i-1] + f[i-2];       cin >> n;   //输入测试用例数n    while (n --) {   //每次循环处理一个测试用例        cin >> m;   //测试用例正整数m        cout << m << " = ";        for (i = 39; i > 1; -- i) {  //从高到低，找不大于m的Fibonacci数f[i]            if (f[i] <= m) {   //当前Fibonacci数不大于m 第一次小于的数 必选的                 B[i] = 1;   // Fibonacci二进制数位赋值1                m -= f[i];            }else B[i] = 0;         }        i = 39;        while (!B[i]) -- i;        while (i > 1) cout<
    
     <<" "<
     
      <
     
    
   

转载地址：https://blog.csdn.net/m0_74282945/article/details/131532417 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！