Informatyka MIMUW

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.

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.

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: