4835. Без двух единиц подряд

По данному натуральному числу n выведите все двоичные последовательности длины n, не содержащие двух единиц подряд, в лексикографическом порядке.

Вход. Одно натуральное число n (n ≤ 20).

Выход. Вывести каждую последовательность в отдельной строке. Числа в последовательности следует разделять одним пробелом.

Пример входа	Пример выхода
3	0 0 0 0 0 1 0 1 0 1 0 0 1 0 1

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Пусть x – целое число. В двоичном представлении число x содержит две единицы подряд, если x & (x << 1) не равно нулю.

Переберем в переменной x все числа от 0 до 2ⁿ – 1. Если число x в двоичном представлении не содержит две единицы подряд, то выводим такое двоичное представление.

Второе решение. Рассмотрим рекурсивное решение. Объявим массив и будем строить в нем требуемые последовательности. Для текщей позиции p (0 ≤ p < n) есть два варианта установки значений:

· m[p] = 0, и далее генерируем последовательность с позиции p + 1;

· m[p] = 1, m[p + 1] = 0, и далее генерируем последовательность с позиции p + 2;

Для второго варианта при p = n – 1 (последняя позиция) совершаем только присваивание m[p] = 1.

Реализация алгоритма

Читаем значение n.

scanf("%d",&n);

Перебираем числа от 0 до 2ⁿ – 1.

for(x = 0; x < (1 << n); x++)

{

Если число x в двоичном представлении содержит две единицы подряд, то пропускаем его.

if (x & (x << 1)) continue;

В одной строке выводим двоичный код числа x слева направо в виде последовательности 0 и 1.

for(i = n - 1; i >= 0; i--)

printf("%d ",(x >> i) & 1);

printf("\n");

}

Реализация алгоритма – рекурсивное решение

#include <stdio.h>

int n;

int m[22];

void gen(int p)

{

if (p >= n)

{

for (int i = 0; i < n; i++)

printf("%d ", m[i]);

printf("\n");

return;

}

m[p] = 0; gen(p + 1);

m[p] = 1; m[p + 1] = 0; gen(p + 2);

}

int main(void)

{

scanf("%d", &n);

gen(0);

return 0;

}

Реализация алгоритма – рекурсивное решение, string

#include <iostream>

#include <string>

using namespace std;

int n;

string s;

void gen(int p, string s)

{

if (p == n)

{

cout << s << endl;

return;

}

gen(p + 1, s + "0 ");

if (p < n - 1) gen(p + 2, s + "1 0 ");

else gen(p + 1, s + "1 ");

}

int main(void)

{

cin >> n;

gen(0, "");

return 0;

}