Модуль: Перебор всех подмасок данной маски


Задача

1 /7


Двоичные строки заданной длины

Теория Нажмите, чтобы прочитать/скрыть

Бывает, что необходимо перебрать все битовые последовательности определенной длины. Или другими словами, перебрать все возможные варианты, где для каждого объекта выбирается одно из двух возможных состояний.

В таких ситуациях можно реализовать перебор с помощью битовых масок. Плюсы такого подхода в том, что такой код работает нерекурсивно и оперирует с числами вместо коллекций или т.п., что значительно улучшает производительность.

Общий код с использованием битмасок приведен ниже:

    int n; // количеств ообъектов (длина битовой последовательности)

    for (int mask = 0; mask < (1 << n); mask++) { // перебираем все числа от 0 до 2^n - 1, где каждое число соответствует битовой маске

        // текущее число mask является битовой маской, где i-ый бит задает состояние i-ого объекта

        for (int i = 0; i < n; i++) { // перебираем n бит, чтобы понять какое состояние у какого объекта

            if ((1 << i) & mask) { // проверяем, что i-ый бит равен единице

                // обрабатываем вариант, что у i-ого объекта состояние '1'
            }
            else { // случай, когда i-ый бит равен нулю

                // обрабатываем вариант, что у i-ого обхекта состояния '0'
            }
        }
    }


Такой код работает за О(2^n * f(n)), где f(n) - это время, за которое вы обрабатываете один конкретный перебираемый вариант.

Задача

По данному числу N выведите все строки длины N из нулей и единиц в лексикографическом порядке.

В решении задачи использовать перебор всех подмасок.

Входные данные

Задано единственное число N. (натуральное, 1 ≤ N ≤ 10)

Выходные данные

Необходимо вывести все строки длины N из нулей и единиц в лексикографическом порядке, по одной на строке

Ввод Вывод
2
00
01
10
11
 



time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Mingw-w6433
C#1
Python32
Комментарий учителя