Wydawanie reszty.pdf

(70 KB) Pobierz
Wydawanie reszty
Problem wydawania reszty jest problemem optymalizacyjnym. Dysponujemy nieograniczoną liczbą
monet o nominałach
, , … ,
oraz daną kwotą pieniędzy , którą należy rozmienić jak
najmniejszą
liczbą monet. Moneta o danym nominale może być wykorzystana dowolną liczbę (w tym
zero) razy.
Specyfikacja problemu
We:
Wy:
,
,
,…,
,
­ liczby całkowite dodatnie
,…,
­ liczby całkowite nieujemne takie, że:
najmniejsze
Uwaga:
Aby zagwarantować istnienie rozwiązania w przypadku dowolnej kwoty przyjmujemy, że
zawsze dysponujemy monetą jednostkową, to znaczy, wejściowy zbiór nominałów spełnia warunek:
1.
Przykład 1.
Rozważmy zbiór nominałów:
1,
2,
5,
Istnieją dwa optymalne rozwiązania wynikające z rozkładów:
20 11 5 2 2
oraz
20 5 5 5 5.
11
oraz kwotę
20.
Przykład 2.
Rozważmy zbiór nominałów:
1,
2,
5,
10
oraz kwotę
Mamy rozkład
18 10 5 2 1
i w tym przypadku rozwiązanie jest jednoznaczne.
Przykład 3.
Rozważmy zbiór nominałów:
wyznacza rozkład
12 5 5 1 1.
Zadania
1,
5,
8
oraz kwotę
18.
12.
Rozwiązanie
1. Zaproponuj algorytm zachłanny dla problemu wydawania reszty. Zapisz go w postaci listy
kroków lub pseudokodzie, a następnie w postaci programu.
2. Czy algorytm zachłanny zawsze daje optymalne rozwiązanie?
3. (*) Wykaż, że jeśli zbiór nominałów
, , … ,
spełnia warunek
dla
1,2, … ,
,
gdzie
1
jest ustaloną liczbą naturalną, to algorytm zachłanny daje optymalne rozwiązanie
dla dowolnej kwoty .
4. (*) Rozstrzygnij, czy algorytm zachłanny daje optymalne rozwiązanie, jeśli zbiór nominałów
, ,…,
spełnia warunek:
1,
2
dla
2, … ,
.
5. (*) Wykaż, że za pomocą monet o nominałach
3
i
5
można rozmienić dowolną (całkowitą)
kwotę
7.
Ciekawostka:
Dla zbioru nominałów
1, 2, 5, 10
algorytm zachłanny daje zawsze optymalne rozwiązanie.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin