programowanie dynamiczne

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 21 i 22: Spamiętywanie i programowanie dynamiczne

  1. Jaka jest minimalna liczba monet lub banknotów potrzebna do wydania \(n\)zł reszty, przyjmując, że w obrocie są dostępne monety o zadanych (w postaci tablicy) nominałach?
  2. Na ile sposobów można wydać \(n\) zł reszty przyjmując, że w obrocie są dostępne monety o zadanych (w postaci listy) nominałach.
  3. Dana jest kwota \(k\) oraz zestaw nominałów banknotów \(b = [b_1; b_2; \dots; b_n]\).
    Mamy dowolną liczbę banknotów każdego z nominałów.

Ćwiczenia 1: poprawność i złożność algorytmu

Zadanie 1 (Potęgowanie binarne)

Zaprojektuj algorytm, który dla danych nieujemnej liczby całkowitej \( \displaystyle n \) i liczby całkowitej \( \displaystyle a \), policzy wartość \( \displaystyle a^n \). Przyjmij za operację dominującą mnożenie dwóch liczb całkowitych i w tym modelu:

  1. zaproponuj algorytm działający w czasie \( \displaystyle O(\log n) \),
  2. udowodnij poprawność swojego algorytmu metodą niezmienników.

Zadanie 2 (Liczby Fibonacciego)

Liczby Fibonacciego definiuje się jak następuje:

Subskrybuje zawartość