Strona główna › Wstęp do programowania - podejście funkcyjne › Ćwiczenia

Ćwiczenia 20: Przeszukiwanie z nawrotami (ang. back-tracking)

wt., 12/07/2010 - 00:53 — kubica
  1. Napisz procedurę, która dla danej liczby \(n\) znajdzie jak można obejść szachownicę \(n \times n\) skoczkiem.
    Skoczek zaczyna obejście w rogu szachownicy, ale może skończyć gdziekolwiek.
    Wynikiem powinna być lista par liczb -- kolejnych pozycji skoczka.
    Jeżeli rozwiązanie nie istnieje, procedura powinna zgłaszać wyjątek Failure.

    Rozwiązania
  2. Napisz procedurę pierwsze, która dla danej liczby całkowitej \(n\) (\(n>1\)) wyznacza
    rozbicie \(n\) na sumę minimalnej liczby składników będących liczbami pierwszymi.
    (Możesz założyć prawdziwość hipotezy Goldbacha.)
  3. Dany jest (multi-)zbiór kostek domina.
    Należy wyznaczyć maksymalny łańcuch, jaki można ułożyć z danych kostek, oczywiście zgodnie z zasadami domina.
    Rozwiązanie powinno mieć postać procedury domino : (α * α) list → (α * α) list.
    Klocki można obracać.
  4. [XIV OI] Atrakcje turystyczne (uproszczone).
    Mamy \(n\) miejscowości, ponumerowanych od 1 do \(n\).
    Odległości między miejscowościami są dane w postaci (symetrycznej) tablicy liczb całkowitych, o wymiarach \(n \times n\).

    Chcemy zwiedzić wszystkie te miejscowości, jednak nie w dowolnej kolejności.
    Mamy daną listę ograniczeń postaci \([(i_1, j_1); \dots; (i_k,j_k)]\).
    Ograniczenie \((i,j)\) oznacza, że miasto \(i\) musi być zwiedzone przed miastem \(j\).
    Możesz założyć, że ograniczenia da się spełnić.

    Na początku wyruszamy z miasta 1, a kończymy podróż w mieście \(n\).
    Wyznacz minimalną drogę jaką trzeba przejechać, żeby zwiedzić wszystkie miasta.