Cvičenie č.8

Ciele

Porozumieť dodanej implementácii výpočtu Fibonacciho čísla a binomického koeficientu metódou Divide-and-Conquer (DnC) a metódou dynamického programovania (DP).
Podľa uvedeného pseudokódu (prednášok) implementovať vzorový algoritmus pre metódu DnC.
Podľa uvedeného pseudokódu (prednášok) implementovať vzorový algoritmus pre metódu DP.

Úvod

Návrh a implementácia algoritmov s využitím metód Divide-and-Conquer (DnC) a dynamického programovania (DP).

Postup

Implementácia jednoduchých algoritmov s využitím metód DnC a DP.

Príklad: Ilustrácia využitia návrhových techník DnC a DP pri výpočte Fibonacciho čísel a binomických koeficientov (kombinačných čísel).

Úloha: Pridajte do vytvoreného projektu všetky súbory z pripraveného archívu. Projekt preložte. Výsledný program spustite.

Pripravený archív obsahuje tieto súbory:
- binkoef.h - definičný modul výpočtu binomických koeficientov.
- binkoef.c - implementačný modul výpočtu binomických koeficientov.
- fibonacci.h - definičný modul výpočtu Fibonacciho čísla.
- fibonacci.c - implementačný modul výpočtu Fibonacciho čísla.
- test.c - modul pre testovanie. Obsahuje aj funkciu main.
Poznámka: Dôkladne preštudujte dodaný kód. V prípade nejasností sa s konkrétnou otázkou obráťte na cvičiaceho.

Implementácia algortimov metódou DnC.

Úloha: Implementujte algoritmus MAXMIN podľa uvedeného pseudokódu (alebo prednášok).

Opis: Rekurzívna aplikácia procedúry maxmin, 3/2(n)-2 porovnaní.

Vstup: Množina S s n prvkami, Výstup: maximálny a minimálny prvok S.

procedure maxmin(A[1...n] of numbers) -> (max, min)
begin
	if (n == 1)
		return (A[1], A[1])
	else if (n == 2)
		if( A[1] > A[2])
			return (A[1], A[2])
		else
			return (A[2], A[1])
	else
		(max_left, min_left) ← maxmin(A[1...(n/2)])
		(max_right, min_right) ← maxmin(A[(n/2 +1)...n])
		if (max_left < max_right)
			max ← max_right
		else
			max ← max_left
		if (min_left < min_right)
			min ← min_left
		else
			min ← min_right
		return (min, max)
end

Implementácia algortimov metódou DP.

Úloha: Implementujte CHAIN_MATRIX_MULTIPLICATION algoritmus podľa uvedeného pseudokódu (alebo prednášok).

Opis: Výpočet súčinu n matíc s využitím metódy DP.
Vstup: Rozmery matíc, Výstup: minimálna cena násobenia matíc.
```
begin
	for i ← 1 until n do m_i,i ← 0;
	for l ← 1 until n-1 do			// Pozor na podobnosť znakov 1 a l
		for i ← 1 until n-l do
		begin
			j ← i + l;
			m_i,j ← MIN_i≤k<j(m_i,k + m_k+1,j + r_i-1r_kr_j);
		end
	write m_1,n
end				
            
```
Úloha: Implementujte algoritmus Coin Change Problem podľa nižšie uvedeného pseudokódu. Uvažujte riešenia pre rôzne vstupné sumy, ak dostupné sú mince s nominálnymi hodnotami: 100,25,20,5,1.

Opis: Riešenie "Coin Change" problému s využitím Greedy metódy. V rámci každej iterácie slučky je pridaný nominál (minca) s najvyššou hodnotou, po pripočítaní ktorej nie je prekročená celková požadovaná suma (vstup algoritmu), do množiny doposiaľ vybraných nominálov.
Vstup: Suma, ktorú je potrebné rozmeniť a hodnoty dostupných nominálov, Výstup: minimálny počet nominálov, ktorými je možné sumu rozmeniť.
```
MAKE-CHANGE (n)
        C ← {100, 25, 20, 5, 1}     // constant.
        Sol ← {};                   // set that will hold the solution set.
        Sum ← 0 sum of item in solution set
        WHILE sum not == n
            x ← largest item in set C such that sum + x ≤ n
            IF no such item THEN
                RETURN "No Solution"
            S ← S U {value of x}
            sum ← sum + x
        RETURN S
            
```

Zdroje

Tu vložte zdroje používané na cvičení.

Doplňujúce úlohy

Úloha: Implementujte algoritmus Coin Change Problem podľa nižšie uvedeného pseudokódu. Uvažujte riešenia pre rôzne vstupné sumy, ak dostupné sú mince s nominálnymi hodnotami: 100,25,20,5,1.

Doplňujúce zdroje

Greedy metóda.