Oto zadanie:
Napisz funkcję, która dla danej liczby naturalnej \(\displaystyle{ n}\) wypisze wszystkie poprawne ciągi nawiasów \(\displaystyle{ (,)}\) o łącznej długości \(\displaystyle{ 2 \cdot n}\).( poprawne czyli na przykład \(\displaystyle{ ((()));()()();(()())}\)). Widzę, że kążdy taki ciąg możemy opisać ciągiem zero-jedynkowym zaczynającym się od zera i takim, że w jeśli utniemy ciąg do \(\displaystyle{ k}\) pierwszych wyrazów to zawsze \(\displaystyle{ liczba zer \ge liczba jedynek}\) (dla dowolnego naturalnego k ), no i dodatkowo musi być tyle samo zer i jedynek. Jak teraz przejść do wypisywania takich kombinacji?
[Algorytmy] Wypisywanie nawiasów
-
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
[Algorytmy] Wypisywanie nawiasów
Najprościej jest rekurencyjnie, ale czy najwydajniej - zapewne nie.
Po prostu utrzymuj obecny ciąg, obecną sumę (liczbę jedynek).
Czyli coś w stylu:
Po prostu utrzymuj obecny ciąg, obecną sumę (liczbę jedynek).
Czyli coś w stylu:
Kod: Zaznacz cały
nawiasy (int suma, string ciag, int dlugosc){
if (suma < 0 || ciag.length() > dlugosc){
return;
}
if (suma == 0 && ciag.length() == dlugosc){
print (ciag);
}
nawiasy (suma + 1, ciag + "(", dlugosc);
nawiasy (suma - 1, ciag + ")", dlugosc);
}
nawiasy (0, "", 2 * n);