Spotkanie 4 - Rozwiązywanie problemów za pomocą komputera

1.Co to jest algorytm?

ALGORYTM - 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 (w odróżnieniu od abacism - przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi , matematyk perski z IX wieku[1].

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ć zaimplementowany w postaci programu komputerowego.

Jako przykład stosowanego w życiu codziennym algorytmu podaje się często przepis kulinarny. Dla przykładu, aby ugotować bigos należy w określonej kolejności oraz odstępach czasowych (imperatyw czasowy) dodawać właściwe rodzaje kapusty i innych składników. Może istnieć kilka różnych przepisów dających na końcu bardzo podobną potrawę. Przykład ten ma wyłącznie charakter poglądowy, ponieważ język przepisów kulinarnych nie został jasno zdefiniowany. Algorytmy zwykle formułowane są w sposób ścisły w oparciu o język matematyki.

W niektórych krajach, jak USA, algorytmy mogą zostać opatentowane, jeżeli zostaną zaimplementowane w jakimś praktycznym celu. Niektórzy twierdzą, że patentowanie algorytmów spowalnia rozwój informatyki, bo jeden producent może uzyskać monopol, np. na pisanie oprogramowania tworzącego pewne typy plików (np. GIF). Wiele koncernów komputerowych prowadzi między sobą spory prawne dotyczące praw własności do niektórych patentów. Kontrargumentem jest tzw. prawo własności intelektualnej (jaką objęty jest np. utwór muzyczny, będący wytworem intelektu i pracy muzyka) zakładające, że program jest intelektualną własnością twórcy.

2.Problem kasjera.

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.

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.

3.Metody rozwiązania "problemu kasjera"

1.Lista kroków
Opis słowny algorytmu wydawania reszty
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.Schemat blokowy

3.Za pomocą Excel

4 Za pomocą Turbo pascal.

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.


5.Za pomocą C++
//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;
}


6 Za pomocą VBA

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