Найдите количество положительных целых чисел, меньших или равных n, которые не имеют последовательных единиц в двоичном представлении

S определяется как множество всех положительных целых чисел, чье двоичное представление не имеет последовательных единиц. Найдите лексикографический порядок, то есть количество элементов S меньше или равно ему, данного числа.

например,
ввод: 17
вывод: 9
Объяснение: 8 чисел в наборе меньше 17 — это 1, 2, 4, 5, 8, 9, 10 и 16.

* Вход гарантированно принадлежит множеству S.

Моя попытка:

Если вход представляет собой целую степень числа 2, то это просто проблема динамического программирования, подобная фибоначчи. Однако эта идея больше не работает, если ввод не является целочисленной степенью числа 2. Поэтому я думаю об использовании включения-исключения, но пока не нашел чего-то, что можно было бы запустить за разумное время. Любые подсказки приветствуются.


set binary algorithm counting dynamic-programming
person Learning Mathematics    schedule 08.11.2020    source источник

Ответы (2)


arrow_upward
2
arrow_downward

теорема Цекендорфа гласит:

каждое натуральное число может быть однозначно представлено в виде суммы одного или нескольких различных чисел Фибоначчи таким образом, что сумма не включает никакие два последовательных числа Фибоначчи.

Это означает, что, поскольку ваше число 17 является представлением Цекендорфа числа 9, следовательно, в наборе есть на 8 чисел меньше.

Следовательно, чтобы вычислить ответ:

  1. Преобразовать число в двоичное (17d -> 10001b биты, установленные в позиции 1 и 5)
  2. Добавьте число Фибоначчи Fi для каждого установленного бита в позиции i (F5+F1 = 8 + 1 = 9)
  3. Вычесть 1 (9 - 1 = 8)
person Peter de Rivaz    schedule 08.11.2020
comment
как теорема Цекендорфа связана с предоставленным вами алгоритмом? - person Learning Mathematics; 08.11.2020
comment
Множество S можно рассматривать как множество Цекендорфских представлений чисел. Этот алгоритм работает только потому, что существует уникальное представление каждого целого числа. - person Peter de Rivaz; 08.11.2020
comment
Понятно. Благодарю вас! - person Learning Mathematics; 08.11.2020

arrow_upward
1
arrow_downward

Для полноты картины вот цифровая динамическая программа с O(log n) временем и O(1) пространством, включая проверку на перебор.

Код 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.');

person גלעד ברקן    schedule 09.11.2020