计算Fibonacci数系统中设置的位数？

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在这个sequence.Since的前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。有了这个不变量，我们可以使用以下模式从一个数字递增到下一个数字：

1. 如果最后一位数字是0，则将其设置为1。
2. 如果最后一位数字是1，则由于没有任何连续的1，因此将最后一位数字设置为0，并将下一位数字设置为1。
3. 通过将这两个数字都设置为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)-digit数字，您会发现每个数字都是一个前缀为10的k位数字。这意味着，如果所有k位数字中总共有B1，那么k+2位数字中的B总数等于B加上k位数字的数量，因为我们只是在重放序列，每个数字前面都有一个额外的1。

我们可以利用这一点来计算Fibonacci编码中最多有k位的1的数量。诀窍如下-如果对于我们跟踪的每一位数

1. 多少个数字至多有那么多位(称为N(d))，以及
2. 多少个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位数字( N(d) )的数字上加上前缀10而形成的数目(N(d))
• B(d + 2) = B(d + 1) + B(d) +N(D)(至多d+2的数目中的总1比特的数目是最多d+1的数目中的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个1位。对于2位数字，有两个1 (1和10)。对于3位数字，有5个1 (1，10,100,101)。对于四位数字，有10个1(前面的5个数字加上1000,1001,1010)。将其向外扩展可以得到我们想要的序列。

这非常容易计算-如果我们重用以前的空间，我们可以在O(k)时间内计算k位的值，而只需要O(1)的内存使用量。由于Fibonacci数呈指数级快速增长，这意味着如果我们有一些数N，并且想要找到所有1s比特的总和到小于N的最大Fibonacci数，我们可以在时间O(log N)和空间O(1)中做到这一点。

也就是说，我不确定如何使其适用于一般的上限。然而，我乐观地认为，有一些方法可以做到这一点。这是一个漂亮的递归，只需要有一个很好的方法来概括它。

希望这能有所帮助！谢谢你提出了一个很棒的问题！

Answer 2

免得解决3个问题。每个next比前一个更难，每个都使用前一个的结果。

1.如果写下从0到fibi-1的每个数字，则设置多少个1。

将其称为dp[i]。让我们来看看这些数字

     0
     1
    10
   100
   101
  1000
  1001
  1010 <-- we want to count ones up to here
 10000

如果将所有数字写到fibi-1，则首先将所有数字写到fibi-1-1 (dpi-1)，然后再写最后一个数字块。这些数字中恰好有fibi-2，每个数字在第一个位置都有一个1，所以我们添加fibi-2，如果您删除这些数字

000
001
010

然后去掉前导零，可以看到从0到fibi-2-1的每个数字都被写下来了。1的数量等于dpi-2，这给出了：

dp[i] = fib[i-2] + dp[i-2] + dp[i-1];

2.如果写下0到n的每个数字，则设置多少个1。

     0
     1
    10
   100
   101
  1000
  1001 <-- we want to count ones up to here
  1010 

让我们称其为solNumber(n)

假设你的数字是fi + x，其中fi是最大可能的斐波那契数。然后分析dpi + solNumber(x)。这可以用与第1点相同的方式来证明。

3.前n位设置了多少个1。

3a。有多少个数字的表示长度恰好是l

如果l= 1，答案是1，否则是fibl-2 +1，你可以注意到，如果你删除前导1，然后所有前导0，你将得到从0到fibl-1-1的每个数字。就是fibl数。

// 3a结束

现在你可以找到这样的数字m，如果你写从1到m的所有数字，它们的总长度将是<=n。但是如果你写从1到m+1，总长度将> n。手动解决m+1的问题并添加solNumber(m)。

这3个问题都在log( n)中得到了解决

#include <iostream>

using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define RFOR(i, b, a) for(int i = b - 1; i >= a; --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)

typedef long long Long;


const int MAXL = 30;



long long fib[MAXL];

//How much ones are if you write down the representation of first fib[i]-1 natural numbers
long long dp[MAXL];

void buildDP()
{
    fib[0] = 1;
    fib[1] = 1;
    FOR(i,2,MAXL)
        fib[i] = fib[i-1] + fib[i-2];


    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;

    FOR(i,3,MAXL)
        dp[i] = fib[i-2] + dp[i-2] + dp[i-1];
}

//How much ones are if you write down the representation of first n natural numbers
Long solNumber(Long n)
{   
    if(n == 0)
        return n;
    Long res = 0;
    RREP(i,MAXL)
        if(n>=fib[i])
        {           
            n -= fib[i];
            res += dp[i];
            res += (n+1);
        }
    return res;
}

int solManual(Long num, Long n)
{
    int cr = 0;

    RREP(i,MAXL)
    {
        if(n == 0)
            break;

        if(num>=fib[i])
        {
            num -= fib[i];
            ++cr;
        }

        if(cr != 0)
            --n;
    }
    return cr;
}

Long num(int l)
{
    if(l<=2)
        return 1;
    return fib[l-1];
}

Long sol(Long n)
{
    //length of fibonacci representation
    int l = 1;
    //totatl acumulated length
    int cl = 0;
    while(num(l)*l + cl <= n)
    {
        cl += num(l)*l;
        ++l;
    }   
    //Number of digits, that represent numbers with maxlength
    Long nn = n - cl;

    //Number of full numbers;
    Long t = nn/l;

    //The last full number
    n = fib[l] + t-1;

    return solNumber(n) + solManual(n+1, nn%l);



}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);
    buildDP();

    Long n;
    while(cin>>n)
        cout<<"ANS: "<<sol(n)<<endl;
    return 0;
}

Answer 3

这里是O((log n)^3)。

让我们计算前N位适合多少个数字

假设我们有一个函数：

long long number_of_all_bits_in_sequence(long long M); 

它计算所有不大于M的数所产生的“自然数的斐波那契位序列”的长度。

有了这个函数，我们可以使用二进制搜索来找出前N位适合多少个数字。

在表示前M个数字时，有多少位是1

让我们创建一个函数来计算<= M在第k位有多少个数字。

long long kth_bit_equal_1(long long M, int k);

首先，让我们对所有较小的值预处理此函数的结果，假设M <= 1000000。

M>PREPROCESS_LIMIT的实现：

long long kth_bit_equal_1(long long M, int k) {
   if (M <= PREPROCESS_LIMIT) return preprocess_result[M][k];

   long long fib_number = greatest_fib_which_isnt_greater_than(M);
   int fib_index = index_of_fib_in_fibonnaci_sequence(fib);

   if (fib_index < k) {
      // all numbers are smaller than k-th fibbonacci number
      return 0;
   }

   if (fib_index == k) {
      // only numbers between [fib_number, M] have k-th bit set to 1
      return M - fib_number + 1;       
   } 

   if (fib_index > k) {
      long long result = 0;

      // all numbers between [fib_number, M] have bit at fib_index set to 1
      // so lets subtrack fib_number from all numbers in this interval
      // now this interval is [0, M - fib_number]
      // lets calculate how many numbers in this inteval have k-th bit set.
      result += kth_bit_equal_1(M - fib_number, k);

      // don't forget about remaining numbers (interval [1, fib_number - 1])
      result += kth_bit_equal_1(fib_number - 1, k);

      return result;
   }
}

该函数的复杂度为O(M / PREPROCESS_LIMIT)。

请注意，在循环中，其中一个加数始终是fibbonaci数之一。

kth_bit_equal_1(fib_number - 1, k);

因此，如果我们记住所有的计算结果，那么复杂度将提高到T(N) = T(N/2) + O(1)。T(n) = O(log )。

让我们回到number_of_all_bits_in_sequence

我们可以稍微修改一下kth_bit_equal_1，这样它也会计算等于0的位数。