Spotkanie 4. Rozwiązywanie problemów

Algorytm to skończony, uporządkowany zbiór jasno zdefiniowanych czynności, koniecznych do wykonania pewnego zadania. Słowo "algorytm" pochodzi od nazwiska Muhammed ibn Musa Alchwarizmi matematyka perskiego z IX wieku i początkowo oznaczało w Europie sposób obliczeń oparty na dziesiętnym systemie liczbowym. Algorytm ma przeprowadzić system z pewnego stanu początkowego do pożądanego stanu końcowego.
 Cechy algorytmu:
- poprawność (algorytm daje dobre wyniki),
- jednoznaczność (daje takie same wyniki przy takich samych danych),
- skończoność (wykonuje się w skończonej ilości kroków),
- sprawność (czasowa - szybkość działania i pamięciowa - "zasobożerność")
 

Problem kasjera 

Opis problemu:
Kasjer ma wydać resztę, będącą dowolną kwotą między 0,01PLN a 0,99PLN, przy użyciu minimalnej liczby monet. Rozwiązanie oparte 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  

a) 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

b) Schematy blokowe:

c) Rozwiązanie problemu w arkuszu kalkulacyjnym MS Excel

d) Rozwiązanie problemu przy pomocy VBA (działanie i listing)

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

e) Rozwiazywanie problemu przy pomocy Turbo Pascal (listing)

  Sposób 1.

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.

Sposób 2.

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.


f) Rozwiazywanie problemu przy pomocy 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;
}