Ciągi binarne bez sąsiednich jedynek
Treść zadania
Ciąg binarny to napis złożony ze znaków 0 i 1. Wypisz wszystkie ciągi binarne długości n, w których żadne dwie jedynki nie stoją obok siebie (np. 1010 jest poprawny, a 0110 nie), w kolejności leksykograficznej (słownikowej), a na końcu ich liczbę.
Napisz rekurencyjną funkcję generuj(n, ciag), która wypisuje wszystkie poprawne ciągi długości n zaczynające się od napisu ciag i zwraca ich liczbę. Program wywołuje generuj(n, "") i wypisuje zwróconą liczbę.
Dane wejściowe
Jedna liczba naturalna n.
Dane wyjściowe
Najpierw wszystkie poprawne ciągi, każdy w osobnej linii, w kolejności leksykograficznej. W ostatniej linii — liczba tych ciągów.
Ograniczenia
1 ≤ n ≤ 12
Uwagi
- To przykład przeszukiwania z nawrotami (ang. backtracking): budujemy ciąg znak po znaku. W każdym kroku najpierw próbujemy dopisać
0(zawsze wolno), a potem1— ale tylko wtedy, gdyciagjest pusty albo kończy się na0. Gdyciagma już długośćn, wypisujemy go i zwracamy1. - Próbowanie
0przed1sprawia, że ciągi pojawiają się od razu w kolejności leksykograficznej — nie trzeba ich sortować. - Ciekawostka: liczba takich ciągów to kolejne liczby Fibonacciego ($2, 3, 5, 8, 13, \dots$).
Przykład
3
000 001 010 100 101 5
Pozostałe ciągi długości 3 (011, 110, 111) mają dwie sąsiednie jedynki.
Potrzebujesz teorii?
Zasady obowiązujące w rozdziale 15
Poniższe zadania uczą rekurencji: funkcja rozwiązuje problem, wywołując samą siebie dla mniejszych danych, aż dojdzie do przypadku bazowego, w którym odpowiedź jest znana od razu (np. $0! = 1$).
Konwencje wspólne:
- Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście. Program wczytuje dane, wywołuje funkcję opisaną w treści i wypisuje wynik (gotowy szkielet znajdziesz w sekcji „Kod startowy”).
- Rozwiązanie musi być rekurencyjne. Właściwe obliczenia wykonuje funkcja, która wywołuje samą siebie. Nie używaj w niej pętli
foraniwhile, ani gotowych narzędzi, które wykonają całą pracę za Ciebie (np.sum(),pow(), operatora**,math.factorial(),list.index()). Sprawdzarka porównuje tylko wynik, ale celem zadań jest ćwiczenie rekurencji. - Każda funkcja rekurencyjna potrzebuje przypadku bazowego (kiedy przestajemy się wywoływać) i kroku rekurencyjnego (wywołania dla mniejszego problemu). Bez przypadku bazowego program przerwie działanie błędem
RecursionError. - Python ogranicza głębokość rekurencji (domyślnie do około 1000 zagnieżdżonych wywołań), dlatego dane w zadaniach są małe.
- Liczby naturalne liczymy od zera: $0, 1, 2, \dots$
- Program nie wypisuje komunikatów typu „Podaj liczbę:”.
Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.
Przywrócono Twój zapisany kod.
Python uruchomi się w przeglądarce przy pierwszym teście.
Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.
Testy
Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.
Test 1
Nie uruchomiono1
0 1 2
Test 2
Nie uruchomiono2
00 01 10 3
Test 3
Nie uruchomiono4
0000 0001 0010 0100 0101 1000 1001 1010 8
Test 4
Nie uruchomiono6
000000 000001 000010 000100 000101 001000 001001 001010 010000 010001 010010 010100 010101 100000 100001 100010 100100 100101 101000 101001 101010 21
Test 5
Nie uruchomiono11
00000000000 00000000001 00000000010 00000000100 00000000101 00000001000 00000001001 00000001010 00000010000 00000010001 00000010010 00000010100 00000010101 00000100000 00000100001 00000100010 00000100100 00000100101 00000101000 00000101001 00000101010 00001000000 00001000001 00001000010 00001000100 00001000101 00001001000 00001001001 00001001010 00001010000 00001010001 00001010010 00001010100 00001010101 00010000000 00010000001 00010000010 00010000100 00010000101 00010001000 00010001001 00010001010 00010010000 00010010001 00010010010 00010010100 00010010101 00010100000 00010100001 00010100010 00010100100 00010100101 00010101000 00010101001 00010101010 00100000000 00100000001 00100000010 00100000100 00100000101 00100001000 00100001001 00100001010 00100010000 00100010001 00100010010 00100010100 00100010101 00100100000 00100100001 00100100010 00100100100 00100100101 00100101000 00100101001 00100101010 00101000000 00101000001 00101000010 00101000100 00101000101 00101001000 00101001001 00101001010 00101010000 00101010001 00101010010 00101010100 00101010101 01000000000 01000000001 01000000010 01000000100 01000000101 01000001000 01000001001 01000001010 01000010000 01000010001 01000010010 01000010100 01000010101 01000100000 01000100001 01000100010 01000100100 01000100101 01000101000 01000101001 01000101010 01001000000 01001000001 01001000010 01001000100 01001000101 01001001000 01001001001 01001001010 01001010000 01001010001 01001010010 01001010100 01001010101 01010000000 01010000001 01010000010 01010000100 01010000101 01010001000 01010001001 01010001010 01010010000 01010010001 01010010010 01010010100 01010010101 01010100000 01010100001 01010100010 01010100100 01010100101 01010101000 01010101001 01010101010 10000000000 10000000001 10000000010 10000000100 10000000101 10000001000 10000001001 10000001010 10000010000 10000010001 10000010010 10000010100 10000010101 10000100000 10000100001 10000100010 10000100100 10000100101 10000101000 10000101001 10000101010 10001000000 10001000001 10001000010 10001000100 10001000101 10001001000 10001001001 10001001010 10001010000 10001010001 10001010010 10001010100 10001010101 10010000000 10010000001 10010000010 10010000100 10010000101 10010001000 10010001001 10010001010 10010010000 10010010001 10010010010 10010010100 10010010101 10010100000 10010100001 10010100010 10010100100 10010100101 10010101000 10010101001 10010101010 10100000000 10100000001 10100000010 10100000100 10100000101 10100001000 10100001001 10100001010 10100010000 10100010001 10100010010 10100010100 10100010101 10100100000 10100100001 10100100010 10100100100 10100100101 10100101000 10100101001 10100101010 10101000000 10101000001 10101000010 10101000100 10101000101 10101001000 10101001001 10101001010 10101010000 10101010001 10101010010 10101010100 10101010101 233