Zadanie z rekurencją – wypisywanie wszystkich kombinacji 0 i 1

0

Cześć, moja metoda miałaby przyjmować n jako argument i wypisywać wszystkie kombinacje 0 i 1, ale jest jedno ale. Nie może być dwóch jedynek obok siebie. Czy ktoś może wie w jaki sposób zastosować w tym zadaniu rekurencję?

0

Rozwiązanie iteracyjne, więc nawet lepsze niż rekurencja (nie rozwala stosu), Python:

def append_one_or_zero(xs):
    out = []
    for x in xs:
        if x[-1] == "0":
            out.append(x + "0")
            out.append(x + "1")
        else:
            out.append(x + "0")
    return out


def all_specific_iter(n):
    xs = ["0", "1"]
    if n == 1:
        return xs
    k = 0
    while k < n - 1:
        xs = append_one_or_zero(xs)
        k += 1
    return xs
print(all_specific_iter(3)) # -> ['000', '001', '010', '100', '101']
print(all_strings(3))       # -> ['000', '100', '010', '110', '001', '101', '011', '111']

W zasadzie sprawę załatwia funkcja append_one_or_zero - skanuje wejściową listę stringów i odpowiednio ją powiększa (jak element kończy się na zero, dodaje do listy wynikowej element concat "0" i element concat "1", a jak na jeden to tylko element concat "0"). Potem już tylko all_specific_iter generuje odpowiednia ilość w pętli.
Jak wygenerować wszystkie stringi do testowania, można znaleźć tutaj: https://4programmers.net/Mikroblogi/View/25339#entry-25339 .
Generalnie, mi wygląda, że algorytm jest poprawny, tzn. uważam, że jest zgodny z taką specyfikacją problemu (która faktycznie jest jego opisem!:)):

  1. Pusty string należy do języka L (L wszystkie binarne stringi długości n, bez dwóch jedynek koło siebie).
  2. Jeśli string a nalezy do L, to jeśli a kończy się na zero to a0 i a1 należą do L; jeśli a kończy się na jeden, to a0 należy do L

1 użytkowników online, w tym zalogowanych: 0, gości: 1