back-tracking

warning: Creating default object from empty value in /usr/share/drupal6/modules/taxonomy/taxonomy.pages.inc on line 33.

Ćwiczenia 25 i 26: Programowanie dynamiczne, zachłanne i back-tracking -- powtórzenie

Rozwiązanie każdego z poniższych zadań wymaga użycia jednej z trzech technik:
back-trackingu, programowania dynamicznego lub zachłannego.
Pytanie której?

  1. [PCh, Zadanie o misjonarzach i kanibalach]
    Przez rzekę chcą przeprawić się kanibale i misjonarze.
    Kanibali i misjonarzy jest po trzech.
    Mają jedną łódkę, którą może płynąć do dwóch osób.
    Łódką umieją wiosłować kanibale i tylko jeden misjonarz.
    Jeżeli w dowolnej chwili, na dowolnym brzegu rzeki będzie więcej kanibali, niż misjonarzy, to zjedzą oni misjonarzy.

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

  1. 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.)
  2. 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ć.
Subskrybuje zawartość