Definicja algorytmu:
W matematyce oraz informatyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa "algorism", oznaczającego wykonywanie działań przy pomocy liczb arabskich. Algorytm ma przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego. Badaniem algorytmów zajmuje się algorytmika. Algorytm może zostać zastosowany w postaci programu komputerowego.
Algorytm zachłanny-wykonuje zawsze działanie, które wydaje się w danej chwili najkorzystniejsze. Wybiera zatem lokalnie optymalną możliwość w nadziei, że doprowadzi ona do globalnie optymalnego rozwiązania.
Problem kasjera:
Kasjer ma wydać resztę, będącą dowolną, przy użyciu minimalnej liczby monet. Rozwiązanie oparte jest na algorytmie zachłannym Najpierw używamy monety o największej dopuszczalnej wartości, redukując w ten sposób problem do wypłacenia mniejszej kwoty.
Metody rozwiązania:
1. Lista kroków:
Dane: Kwota pieniędzy do wydania, nominały banknotów i bilonu uporządkowane malejąco
Wyniki: Ilość poszczególnych nominałów banknotów i bilonu
- Krok 1: Ustalenie wartości początkowych
- Krok 2: Sprawdzamy, ile razy najwyższy nominał mieści się w kwocie do wydania
- Krok 3: Obliczamy resztę do wydania: poprzednia kwota - obliczona ilość * nominał
- Krok 4: Przechodzimy do niższego nominału
- Krok 5: Jeśli reszta do wydania = 0 [stop] w przeciwnym razie powtarzamy kroki 2 - 4
2. Schematy blokowe:
3. Rozwiązanie w programie Microsoft Office Excel:
4. Rozwiązanie przy pomocy VBA (listing i działania)
Sub ile_banknotow()
'wartość zostanie przeliczona na dane z tablicy i kolejno zaproponowane
Dim liczba As Currency, y&, do_wydania$, pyt
Dim tablica As Variant, skarbonka As Currency
tablica = Array(500, 200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.02, 0.01)
pyt = InputBox("Wpisz wartość liczbową aby uzyskać " & _
"informacje o banknotach składających się na tą wartość:", _
"Bankomat VBATools.pl", "1234,56")
If Len(pyt) = 0 Then Exit Sub
If IsNumeric(pyt) = False Then MsgBox "Wartość " & Chr(34) & pyt & Chr(34) & _
" nie jest spodziewaną wartością pieniężną!", vbExclamation, _
" VBATools.pl": Exit Sub
liczba = CCur(pyt)
On Error GoTo Blad
Do While skarbonka < liczba
nowy_banknot:
If skarbonka + tablica((y)) > liczba Then
y = y + 1
GoTo nowy_banknot
Else
skarbonka = skarbonka + tablica((y))
do_wydania = do_wydania & tablica((y)) & " +"
If skarbonka = liczba Then Exit Do
End If
Loop
Debug.Print skarbonka & " = " & do_wydania
MsgBox "Aby wydać wartość " & skarbonka & " należy wydać kolejno: " _
& vbCr & Left$(do_wydania, Len(do_wydania) - 2), _
vbInformation, "Bankomat VBATools.pl"
Exit Sub
Blad:
MsgBox "Podana wartość " & pyt & " nie jest postaci walutowej!", _
vbExclamation, " VBATools.pl"
End Sub
5. Rozwiązanie w programie Turbo Pascal (listing):
I Sposób:
program wydawanie_reszty; uses crt; var reszta : longint;
begin
clrscr;
writeln('podaj kwote: '); readln(reszta); writeln;
writeln(reszta div 200, ' banknotow 200zl');
reszta:=reszta mod 200;
writeln(reszta div 100, ' banknotow 100zl');
reszta:=reszta mod 100;
writeln(reszta div 50, ' banknotow 50zl');
reszta:=reszta mod 50;
writeln(reszta div 20, ' banknotow 20zl');
reszta:=reszta mod 20;
writeln(reszta div 10, ' banknotow 10zl');
reszta:=reszta mod 10;
writeln(reszta div 5, ' monet 5zl');
reszta:=reszta mod 5;
writeln(reszta div 2, ' monet 2 zl');
reszta:=reszta mod 2;
writeln(reszta, ' monet 1 zl');
repeat until keypressed;
end.
II Sposób:
program Reszta; {obliczenia w petli WHILE}
uses crt;
const N: Array [1..8] of integer = (200, 100, 50, 20, 10, 5, 2, 1);
var i,P,R: longint;
begin
clrscr;
Write('Podaj reszte do wyplacenia: ');
ReadLn(R);
i:=1;
while (R>0) do {dopoki nie wydano calej reszty}
begin
if R>= N[i] then {sprawdz czy mozna wydac danym nominalem}
begin
P:= R div N[i]; {ile razy wydac dany nominal}
R:= R - (P*N[i]); {zmniejsz reszte o wydany nominal}
WriteLn(N[i], ' x ', P); {wypisz wynik}
end;
inc(i); {rozpatrz kolejny nominal}
end;
repeat until keypressed;
end.
6. Rozwiązanie w programie C++ (listing):
//Wydawanie reszty, C++
#include <iostream>
#include <stdlib.h>
using namespace std;
int main(int argc, char *argv[])
{
//tablica dostepnych nominalow
int N[8]={200, 100, 50, 20, 10, 5, 2, 1};
int R,P, i;
cout << "Podaj reszte do wyplacenia: ";
cin >> R;
i=0;
while (R>0) //dopoki nie wydano calej reszty
{
if (R >= N[i]) //sprawdz czy mozna wydac danym nominalem
{
P=R / N[i]; //ile razy wydac dany nominal
R=R-(N[i]*P); //zmniejsz reszte o wydany nominal
cout << N[i] << " x " << P << endl; //wypisz wynik
}
i++; //rozpatrz kolejny nominal
}
system("PAUSE");
return 0;
}
