[Algorytmy] Wypisywanie nawiasów

gmore
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 6 paź 2017, o 21:36
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 2 razy

[Algorytmy] Wypisywanie nawiasów

Post autor: gmore » 6 paź 2017, o 21:41

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?
Ostatnio zmieniony 8 paź 2017, o 04:40 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

matinf
Użytkownik
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

Post autor: matinf » 7 paź 2017, o 20:29

Najprościej jest rekurencyjnie, ale czy najwydajniej - zapewne nie.

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);

ODPOWIEDZ