algorithm - 计算斐波那契数系统中设置的位数？

Question

我们知道，每个非负十进制数都可以由斐波那契数的和唯一地表示(这里我们关心的是最小表示，即在数字的表示中不采用连续的斐波那契数，而且每个斐波那契数最多采用一个在表示中)。

例如:

1->  1
2-> 10
3->100
4->101, here f1=1 , f2=2 and f(n)=f(n-1)+f(n-2);

所以每个十进制数都可以在斐波那契系统中表示为一个二进制序列。如果我们在斐波那契系统中依次写出所有自然数，我们将得到这样的序列:110100101……这被称为“自然数的斐波那契比特序列”。

我的任务是计算第 1 位出现在此序列的前 N ​​位中的次数。由于 N 的值可以从 1 到 10^15，我可以在不存储斐波那契数列的情况下执行此操作吗？

例如:如果 N 为 5，则答案为 3。

Answer 1

所以这只是算法的初步草图。当上限本身是斐波那契数时，它有效，但我不确定如何将其调整为一般上限。希望有人可以改进这一点。

总体思路是查看斐波那契编码的结构。以下是前几个数字:

     0
     1
    10
   100
   101
  1000
  1001
  1010
 10000
 10001
 10010
 10100
 10101
100000

这些数字中的每一个的不变性是永远不会有一对连续的 1。鉴于此不变量，我们可以使用以下模式从一个数字递增到下一个数字:

如果最后一位为 0，则将其设置为 1。

如果最后一位是 1，那么由于没有任何连续的 1，将最后一位设置为 0，下一位设置为 1。

通过将它们都设置为 0 并将下一个数字设置为 1 来消除任何加倍的 1，重复直到消除所有加倍的 1。

这很重要的原因是性质(3)告诉我们一些关于这些数字结构的信息。让我们再次回顾前几个斐波那契编码的数字。例如，看看前三个数字:

  00
  01
  10

现在，查看所有四位数字:

1000
1001
1010

下一个数字将有五位数字，如下所示:

1011 → 1100 → 10000

需要注意的有趣细节是四位数字的数量等于最多两位数字的值的数量。事实上，我们只需在最多两位数字前加上 10 就可以得到四位数字。

现在，看看三位数:

000
001
010
100
101

看看五位数:

10000
10001
10010
10100
10101

请注意，五位数只是带有 10 前缀的三位数。

这为我们提供了一种非常有趣的方法来计算有多少个 1。具体来说，如果您查看 (k+2) 位数字，它们中的每一个都只是一个带有 10 前缀的 k 位数字。这意味着如果所有 k 位数字中总共有 B 个 1，那么 k+2 位数字中的 B 总数等于 B 加上 k 位数字的数量，因为我们只是在每个数字前面加上一个额外的 1 重播序列。

我们可以利用它来计算斐波那契编码中最多包含 k 个数字的 1 的数量。诀窍如下 - 如果我们跟踪每个数字

多少个数字最多有这么多位数(称为 N(d))，以及

有多少个 1 表示最多 d 位的数字(称为 B(d))。

我们可以使用此信息来计算这两条信息的多一位。这是一个美丽的DP复发。最初，我们按如下方式播种。对于一位数，N(d) = 2，B(d) 为 1，因为对于一位数，数字是 0 和 1。对于两位数，N(d) = 3(只有一个两位数，10，和两个一位数0和1)和B(d)是2(一个来自1，一个来自10)。从那里，我们有

N(d + 2) = N(d) + N(d + 1)。这是因为d+2位数以内的数是d+1位数以内的数(N(d+1))加上d位数前加10后的数(N(d+1)) d))

B(d + 2) = B(d + 1) + B(d) + N(d) (长度最多为1比特的个数为d + 2为长度个数的1比特的总个数最多 d + 1，加上我们从 d + 2 位数字中得到的额外值)

例如，我们得到以下信息:

 d     N(d)      B(d)
---------------------
 1       2          1
 2       3          2
 3       5          5
 4       8         10
 5      13         20

我们实际上可以检查一下。对于 1 位数字，总共使用 1 个一位。对于 2 位数字，有两个 1(1 和 10)。对于 3 位数字，有五个 1(1、10、100、101)。对于四位数字，有 10 个一(前五个加上 1000、1001、1010)。将其向外扩展为我们提供了我们想要的序列。

这非常容易计算——如果我们重用之前的空间，我们可以在 O(k) 时间内计算 k 位数字的值，只需 O(1) 内存使用量。由于斐波那契数以指数方式快速增长，这意味着如果我们有一些数字 N 并且想要找到所有 1 位的总和到小于 N 的最大斐波那契数，我们可以在时间 O(log N) 和空间 O (1).

也就是说，我不确定如何调整它以适用于一般上限。但是，我很乐观地认为有办法做到这一点。这是一个美丽的重复，必须有一个很好的方法来概括它。

希望这可以帮助!感谢一个很棒的问题!