2

Перечислить все последовательности нулей и единиц длины N (N<=100), в которых никакие две единицы не стоят рядом. Можно как-то модифицировать этот код?

int main(){
    int arr[]={1, 2, 3};
    for(int i = 0; i< (1 << sizeof(arr) / sizeof(int)); i++){
        int k = i, j = 0;
        while(k){
            if (k & 1) printf("%i ",arr[j]);
            j++;
            k >> =1;
        }
        printf("\n");
    }
}

Эта программа печатает все подмножества массива arr.

7
  • 1
    а вы представляете количество таких последовательностей? Это как бы 100 число фибоначи примерно.
    – pavel
    1 июн 2017 в 14:10
  • @pavel Да, представляю
    – Tommy
    1 июн 2017 в 14:13
  • ну тогда как минимум битовый сдвиг вызовет переполнение... Ответ на конкретный вопрос - да можно
    – pavel
    1 июн 2017 в 14:14
  • А при чем здесь вообще этот код? Почему вы решили, что они имеет хоть какое-то отношение к вашей задаче? 1 июн 2017 в 14:28
  • @AnT Подумал, что она похожа на задачу с подмножествами
    – Tommy
    1 июн 2017 в 16:19

2 ответа 2

3

Если рассматривать последовательное инкрементирование двоичного числа из 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.

1

Схематично:

proc variants(current) {
    if current.length = 100 {
        output current;
    }
    else
    {
        call variants(current + '0');
        if current[current.length] = '0' {
            call variants(current + '1');
        }
    }
}

call variants('');

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.