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
    Commented 1 июн. 2017 в 14:10
  • @pavel Да, представляю
    – Tommy
    Commented 1 июн. 2017 в 14:13
  • ну тогда как минимум битовый сдвиг вызовет переполнение... Ответ на конкретный вопрос - да можно
    – pavel
    Commented 1 июн. 2017 в 14:14
  • А при чем здесь вообще этот код? Почему вы решили, что они имеет хоть какое-то отношение к вашей задаче? Commented 1 июн. 2017 в 14:28
  • @AnT Подумал, что она похожа на задачу с подмножествами
    – Tommy
    Commented 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('');

Ваш ответ

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

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