Опишите рекурсивный алгоритм для печати всех N-разрядных двоичных строк, которые не имеют последовательных единиц

Question

Я нашел решение, которое дает последовательные 1 с, но я не могу найти ничего, что не включает в себя последовательные 1 с в двоичной строке, может кто-нибудь мне помочь?

Answer 1

Вот простой.

def f(n, result=""):
    if n==0:
        print(result)
        return

    if len(result) == 0 or result[-1]=="0":
        f(n-1, result+"1")
    f(n-1, result+"0")

Answer 2

Если вы ищете рекурсивный алгоритм, я думаю иметь рекурсивную функцию, которая добавляет '0' или '1' к строке, в зависимости от последнего символа строки.

Мое решение ниже вызываетрекурсия, пока длина строки не достигнет заданного значения n. Его рекурсивные вызовы выполняются 1) путем добавления '0' к строке и 2) путем добавления '1' к строке, если предыдущий символ не является '1'. Добавление '1' только в том случае, если предыдущий символ не '1', не позволит строке содержать последовательные '1' s. В худшем случае временная сложность будет O (2 ^ n) из-за двух рекурсивных вызовов, а сложность пространства будет O (n) , поскольку глубина рекурсии будет n.

void printNDigitBinaries(int n) {
    printBinHelper(n, "");
}

void printBinHelper(int n, String s) {
    if (s.length() == n) {
        System.out.println(s);
        return;
    }

    printBinHelper(n, s+"0");
    if (s.length() == 0 || s.charAt(s.length()-1) != '1') printBinHelper(n, s+"1");
}

Answer 3

Вот один из способов (в псевдокоде, который является допустимым Python):

def gen(n):
  if n == 0:
    yield ''
    return
  for s in gen(n-1):
    yield s + '0'
    if s == '' or s[-1] == '0':
      yield s + '1'

for s in gen(5):
  print(s)

Он генерирует все строки длиной n-1, а затем:

• добавляет 0 для формирования допустимой строки длины n;
• добавляет 1, но только если это не нарушит ограничение.