Сложность и решение проблемы возврата - PullRequest
Новая
       28

Сложность и решение проблемы возврата

0 голосов
/ 23 мая 2019

Дайте псевдокод алгоритма, который с учетом всего n печатает вся строка длиной n с символами в {a, b}, которые содержат нечетное количество символов a и нечетное количество символов b. Например, для n = 3 ничего не печатается, а для n = 4 строки для печати: 

abbb babb bbab bbba baaa abaa aaba aaab

Алгоритм должен иметь сложность O(nS(n)), где S(n) - это число строки для печати. Мотивировать сложность вашего алгоритма. Я сделал решение, но я не знаю, является ли это алгоритмом возврата или нет, и сложностью этого алгоритма. это правильный подход? 

def stringheBinarie(n, i, sol = [], totA = 0, totB = 0):
    if n == i:
        print("".join(sol))
    else:
        if i < n - 1:
            sol.append('a')
            stringheBinarie(n, i + 1, sol, totA + 1, totB)
            sol.pop()
            sol.append('b')
            stringheBinarie(n, i + 1, sol, totA, totB + 1)
            sol.pop()
        else:
            if totA % 2 == 0 and totB % 2 == 1:
                sol.append('a')
                stringheBinarie(n, i + 1, sol, totA +1, totB)
                sol.pop()
            if totB % 2 == 0 and totA % 2 == 1:
                sol.append('b')
                stringheBinarie(n, i + 1, sol, totA, totB + 1)
                sol.pop()
...