查找小于或等于 n 且二进制表示中没有连续“1”的正整数个数

Question

S is defined to be the set of all positive integers whose binary representation does not have consecutive '1's. Find the lexicographical order, i.e. the number of elements of S less than or equal to it, of the given number.

例如
输入：17
输出：9
解释：集合中小于17的8个数分别是1,2,4,5,8,9,10,16.

*输入保证在集合S中。

我的尝试：

如果输入是2的整数次方，那么就是一个类似斐波那契的动态规划问题。但是，如果输入不是 2 的整数次方，这个想法就不再有效。所以我正在考虑使用包含 - 排除，但到目前为止我还没有找到可以在合理时间内运行的东西。欢迎任何提示。

Answer 1

Zeckendorf's theorem 表示：

every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.

这意味着由于您的数字 17 是 9 的 Zeckendorf 表示，因此集合中有 8 个较小的数字。

因此计算答案：

将数字转换为二进制（17d -> 10001b 位设置在位置 1 和 5）
为位置i处的每个设置位添加斐波那契数Fi (F5+F1 = 8 + 1 = 9)
减 1 (9 - 1 = 8)

Answer 2

为了完整性，这里是数字动态程序 O(log n) 时间和 O(1) space，包括对暴力的检查。

JavaScript代码：

function bruteForce(n){
  let result = 0;
  let last;
  
  for (let k=1; k<=n; k++){
    let i = k;
    let prev;
    let valid = 1;
    while (i){
      bit = i & 1;
      if (bit && prev){
        valid = 0;
        break;
      }
      prev = bit;
      i >>= 1;
    }
    result += valid;
    if (valid)
      last = k
  }

  return last == n ? [last, result] : null;
}

function f(n){
  // Counts:
  // Bit set and bound
  // Bit unset and bound
  // Bit set and unbound
  // Bit unset and unbound
  let dp = [0, 0, 0, 0];
  let dp_prev = [0, 1, 0, 1];
  let result = 0;
  
  while (n){
    const bit = n & 1;
    n >>= 1;
    
    // Add only the bound result for
    // the most significant bit of n
    if (!n){
      result += dp_prev[1];
      break;
    }
    
    if (bit){
      dp[0] = dp_prev[1];
      dp[1] = dp_prev[2] + dp_prev[3];

    } else {
      dp[0] = 0;
      dp[1] = dp_prev[0] + dp_prev[1];
    }

    // (Fibonacci)
    dp[2] = dp_prev[3];
    dp[3] = dp_prev[2] + dp_prev[3];

    // Add result for all numbers
    // with this bit as most significant
    if (n)
      result += dp[2];

    dp_prev = dp;
    dp = [0, 0, 0, 0];
  }

  return result;
}

for (let n=1; n<2000; n++){
  const bf = bruteForce(n);
  // n must be a member of S,
  // which we check in bruteForce
  if (bf){
    const _f = f(n);
    if (_f != bf[1]){
      console.log(`Mismatch: ${ n }, b${ n.toString(2) }, brute force: ${ bf[1] }, f: ${ _f }`);
      break;
    }
  }
}

console.log('Done testing.');

查找小于或等于 n 且二进制表示中没有连续“1”的正整数个数

Find number of positive integers less than or equal to n that doesn't have consecutive '1's in its binary representation

algorithm

binary

set

counting

dynamic-programming

我的尝试：