2

Даны числа n и k, где:

n - длина битовой последовательности

k - количество единиц в этой последовательности

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

Функция binary(k, n) имеет только два параметра - k и n.

Думал, что надо вывести binary(k - 1, n - 1) + '1' и binary(k, n - 1) + '0', рассматривая случаи n == k, k == 0 и так далее, но не получилось...

7
  • Необходимо написать функцию- на чем написать? 19 ноя 2017 в 19:11
  • Мне нужно на C++, но псевдокода тоже хватит 19 ноя 2017 в 19:12
  • Ну раз у тебя никаких ограничений на время/память и нет требований про оптимальности - пиши просто рекурсивно получение всех последовательностей длины N. А выводи только те, в которых K единиц...
    – Akina
    19 ноя 2017 в 19:27
  • 1
    Олимпиады нужно решать самостоятельно. Стыдитесь.
    – VladD
    19 ноя 2017 в 19:58
  • 1
    @VladD это не олимпиада, я для себя решаю) 19 ноя 2017 в 20:50

2 ответа 2

2

Вот такой вариант придумался...

void binary(int n, int k)
{
    static string prefix;
    if (n < k) return;
    if (n == 0) { cout << prefix << endl; return; }
    prefix.push_back('0');
    binary(n-1,k);
    prefix.pop_back();
    if (k >= 1)
    {
        prefix.push_back('1');
        binary(n-1,k-1);
        prefix.pop_back();
    }
}
4
  • Благодарю, все работает! 19 ноя 2017 в 20:56
  • ох спорили мы один раз на эту тему) ru.stackoverflow.com/questions/567314/… кстати, а не дубль ли это?
    – pavel
    20 ноя 2017 в 13:15
  • @pavel Со мной?...
    – Harry
    20 ноя 2017 в 13:30
  • @Harry с владом). Я просто кинул ссылку, вот не нравится мне рекурсивный алгоритм для этой задачи есть честно.
    – pavel
    20 ноя 2017 в 13:39
1

Прямолинейный алгоритм:

  • если количество единиц равно нулю, то вернуть одни нули
  • если длина последовательности равна количеству единиц, то вернуть одни единицы
  • зная все возможные последовательности n-1 битов c k единицами, можно получить в правильном лексикографическом порядке последовательность с n битами приставив 0 слева
  • зная все возможные последовательности n-1 битов c k-1 единицами, можно получить последовательность с n битами и k единицами приставив 1 слева (все варианты с нулём слева уже исчерпаны в предыдущем пункте)

На Питоне:

#!/usr/bin/env python
def binary(n, k):
    if k == 0:  # no bits set
        yield '0' * n
    elif n == k:  # all bits set
        yield '1' * k
    else:
        assert n > k > 0
        for bits in binary(n - 1, k):
            yield '0' + bits
        for bits in binary(n - 1, k - 1):
            yield '1' + bits

Пример:

for bits in binary(4, 3):
    print(*bits)

Результат:

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

Трансляция на С++:

using Bits = std::string;    

void binary(int n, int k, std::function<void(Bits)> yield) {
  if (k == 0) // no bits set
    yield(Bits(n, '0'));
  else if (n == k) // all bits set
    yield(Bits(k, '1'));
  else {
    assert(n > k && k > 0);
    binary(n - 1, k,     [&yield](Bits bits) { yield("0" + bits); });
    binary(n - 1, k - 1, [&yield](Bits bits) { yield("1" + bits); });
  }
}

Пример:

int main() {
  int n, k;
  if(!(std::cin >> n >> k && n >= k && k >= 0))
    exit(EXIT_FAILURE);

  binary(n, k, [](Bits bits) { std::cout << bits << '\n'; });
}

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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