Spotkanie4. Rozwiązywanie problemów za pomocą komputera.

1. Algorytm w matematyce oraz informatyce skończony, uporządkowany 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.

Algorytm zachłanny polega na tym, że w trakcie szukania drogi do rozwiązania całego problemu, w kolejnym kroku, podejmujemy działanie najlepiej rokujące w danym momencie, nie zastanawiając się, czy ma ono sens w dalszej perspektywie.

2. Problem kasjera- algorytm zachłanny

a) Opis problemu:

 Kasjer ma wydać resztę, będącą dowolną kwotą  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.

b) Metody rozwiązywania:

Sposób 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.

Sposób 2.

Schematy blokowe

Sposób 3.

Rozwiązanie  problemu w Excelu

Sposób 4.

Turbo Pascal

To podstawowy program do pisania różnych programów.Obecnie rzadko używany.

Przydaje się do rozwiązywania problemów kasjera.

Sposób 5.

VBA

Sposób wydawania reszty.

Sposób 6.C++

Algorytm zachłanny zapisany w C++ :

    // k – zadana kwota, x=0 – wynik

    // N – zbior (tablica o długości l) nominalow

    while (k>0)                              // dopoki kwota wieksza od zera

    {

      int n=0;                                 // n – maksymalny nominal mniejszy lub rowny kwocie

      for (int i=0;i<l;++i)                    // wsrod wszystkich nominalow...

         if((N[i]<=k)&&(N[i]>n)) n=N[i];         // ...znajdz n

      k -= n;                                  // pomniejsz kwote o n

      ++x;                                     // zwieksz wynik o 1

    } 

Analogiczny algorytm w Pascalu :

type

Tnominaly: array [1..n] of Integer;

{funkcja ilosc_monet zwraca najmniejszą liczbę monet potrzebnych, aby wydać zmienną

kwota typu Integer (uproszczenie dla skrócenia algorytmu) za pomocą nominałów

których wartości są zawarte w tablicy nominaly typu Tnominaly (typ zadeklarowany powyżej).

n jest stałą oznaczającą długość tablicy.}

function ilosc_monet(kwota: Integer; nominaly: Tnominaly )

var

i, x: integer; {deklaracja zmiennych - i to iterator, a x - odpowiednik n z}

                     {powyższego przykładu}

begin

ilosc_monet:=0;

repeat

  i:=n;

  repeat

    x:=nominaly[i];

    if x>kwota then           {znajdowanie x}

      i:=i-1;

  until kwota>=x;

  ilosc_monet:=ilosc_monet+1;

  kwota:=kwota-x;

until kwota=0;

end;