Если рассматривать последовательное инкрементирование двоичного числа из N
битов начиная с нулевой комбинации 0..0
, то последовательности с двумя соседними единичными битами будут возникать в процессе инкрементирования в виде xxx110..0
, т.е. пара соседних единиц, за которыми следуют нули.
Понятно, что сколько бы мы ни инкрементировали такую последовательность, она нас не будет интересовать (т.е. будет содержать эту пару соседних единиц), пока мы не получим перенос в младшую единицу этой пары. То есть нас заведомо не интересуют никакие результаты инкремента, пока мы не дойдем до последовательности xxx111..1
и не прибавим к ней единицу, получив xxx000..0
. Это ненужные результаты не надо генерировать вообще - их несложно "перепрыгнуть" в процессе генерации последовательностей.
Таким образом, для генерации искомых последовательностей нам надо реализовать обычный инкремент N
-значного двоичного числа с одной хитрой модификацией: если какой-то разряд i
в результате инкремента получил значение 1
, то нам надо проверить следующий старший разряд i + 1
. Если он тоже содержит 1
, то мы должны искусственно продолжить выполнение алгоритма инкрементирования с разряда i
#include <stdio.h>
#include <stdbool.h>
#define N 5u
bool increment_no_11(unsigned char (*n)[N])
{
unsigned i;
for (i = 0; i < N; ++i)
if ((*n)[i] == 1)
(*n)[i] = 0;
else if (i + 1 == N || (*n)[i + 1] == 0)
{
(*n)[i] = 1;
break;
}
return i < N;
}
int main(void)
{
unsigned char n[N] = { 0 };
do
{
for (unsigned i = N; i-- > 0;)
printf("%d", n[i]);
printf("\n");
} while (increment_no_11(&n));
}
Для N = 100
количество последовательностей будет равно 927372692193078999176
.