如何有效地将整数转换为Fibonacci编码？

Question

通过从0和1开始然后添加最后两个数字以获得下一个数来获得斐波那契序列.

所有正整数都可以表示为一组Fibonacci数的总和而不重复.例如:13可以是集合{13},{5,8}或{2,3,8}的总和.但是,正如我们所看到的,一些数字有多个集合,其总和是数字.如果我们添加约束集不能有两个连续的Fibonacci数,那么我们每个数都有一个唯一的表示.

我们将使用二进制序列(只有零和1)来做到这一点.例如,17 = 1 + 3 + 13.然后,17 = 100101.详细说明见图2.

我想将一些整数转换为这种表示,但整数可能非常大.如何有效地做到这一点.

Answer 1

首先我想告诉你，我真的很喜欢这个问题，我不知道所有正整数都可以表示为一组不重复的斐波那契数之和，我看到了归纳证明，非常棒。
为了回答你的问题，我认为我们必须弄清楚演示文稿是如何创建的。我认为找到这个的简单方法是从我们找到最接近的小斐波那契项目的数字中。
例如，如果我们想呈现 40：
我们有 Fib(9)=34 和 Fib(10)=55，因此呈现中的第一个元素是 Fib(9)，
因为 40 - Fib(9) = 6 和 (Fib(5) ) =5 且 Fib(6) =8) 下一个元素是 Fib(5)。
所以我们有 40 = Fib(9) + Fib(5)+ Fib(2)
请允许我用 C# 写这个

 class Program
    {
        static void Main(string[] args)
        {
            List<int> fibPresentation = new List<int>();
            int numberToPresent = Convert.ToInt32(Console.ReadLine());
            while (numberToPresent > 0)
            {
                int k =1;
                while (CalculateFib(k) <= numberToPresent)
                {
                    k++;
                }
                numberToPresent = numberToPresent - CalculateFib(k-1);
                fibPresentation.Add(k-1);
            }
        }
        static int CalculateFib(int n)
        {
            if (n == 1)
                return 1;

            int a = 0;
            int b = 1;
            // In N steps compute Fibonacci sequence iteratively.
            for (int i = 0; i < n; i++)
            {
                int temp = a;
                a = b;
                b = temp + b;
            }
            return a;
        }
    }

您的结果将在 fibPresentation 中