Repetytorium - Ćwiczenia 10

Temat: Programowanie dynamiczne.

Programowanie dynamiczne

Jeżeli podproblemy, na które został podzielony problem główny, nie są niezależne to w różnych podproblemach wykonywane są wiele razy te same obliczenia, warto jest wtedy zastosować ulepszenie tej metody- programowanie dynamiczne. Wyniki obliczeń są zapamiętywane w tablicy pomocniczej, która jest wykorzystywana w kolejnych krokach algorytmu, co eliminuje potrzebę wielokrotnego wykonywania tych samych obliczeń. Prowadzi to do widocznego obniżenia złożoności obliczeniowej. Przykładem może być obliczanie symbolu Newtona. Rekurencyjna funkcja wyznaczająca ten współczynnik ma złożoność wykładniczą. Po zastosowaniu programowania dynamicznego złożoność maleje do O(n2). Programowanie dynamiczne polega więc na wykonania obliczeń każdego podproblemu tylko raz i zapamiętaniu jego wyniku w tabeli. W każdym kolejnym kroku można z tej tabeli korzystać. Programowanie dynamiczne jest zazwyczaj stosowane w rozwiązywaniu problemów optymalizacyjnych, prowadzi to często do wyznaczenia kilku równoznacznych, optymalnych rozwiązań. Taka metoda tworzenia algorytmów znalazła zastosowanie m.in. w rozwiązywaniu problemu plecakowego, w optymalnym mnożeniu ciągu macierzy. Jest także stosowana w automatach do kawy przy wydawaniu reszty w taki sposób, my monet było najmniej. (http://www.algorytm.org/kurs-algorytmiki/programowanie-dynamiczne.html)

Zadanie 1 - ciąg Fibonacciego

Napisz program znajdujący n-ty element ciągu Fibonacciego. Rozwiąż zadanie na dwa sposoby:
1) rekurencyjnie
2) za pomocą tablicy - i przechowując wszystkie dotychczas znalezione wartości.

Zadanie 2 - Współczynnik dwumianowy Newtona

Napisz program umożliwiający obliczenie (n po k) - symbolu newtona. (za pomocą programowania dynamicznego)