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
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: Parę Algorytmów Numerycznych... .
Generalnie, mi wygląda, że algorytm jest poprawny, tzn. uważam, że jest zgodny z taką specyfikacją problemu (która faktycznie jest jego opisem!:)):
- Pusty string należy do języka
L
(L
wszystkie binarne stringi długości n, bez dwóch jedynek koło siebie). - Jeśli string
a
nalezy doL
, to jeślia
kończy się na zero toa0
ia1
należą doL
; jeślia
kończy się na jeden, toa0
należy doL