1.Definicja Algorytmu
2.Problem kasjera
a)opis problemu
b)metody rozwiązania:
-lista kroków
-schemat blogowy (x2)
-Exel (zrzut)
-Turbo Pascal (listing x2)
-C++
-Virtual Basic for Application
Algorytm to w matematyce oraz informatyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Badaniem algorytmów zajmuje się algorytmika. Algorytm może zostać zaimplementowany 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( algorytmu zachłannego)
Kasjer ma wydać resztę przy użyciu minimalnej liczby monet lub banknotów . Rozwiązanie oparte na algorytmie zachłannym:
1.używamy monety o największej dopuszczalnej wartości, tym samym redukuje w ten sposób problem do wypłacenia mniejszej liczby pieniędzy.
Lista kroków:
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
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
Schemat blogowy (1)
Schemat blogowy (2)
Exel..
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.
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;
}
Brak komentarzy:
Prześlij komentarz