Spotkanie 4. Rozwiązywanie problemów.

1. Definicja algorytmu.
To sposób postępowania, który prowadzi do rozwiązania problemu lub osiągnięcia jakiegoś celu. Ilość kroków algorytmu zależy od tego, jak złożony jest problem, którego on dotyczy. Liczba tych kroków zawsze będzie skończona. 
2. Problem kasjera

• opis problemu

 Jest nim nieumiejętne wydawanie wszystkich pieniędzy z kasy o niskim nominale co prowadzi do niewydawania całej reszty, kasjer używa wtedy słynnych słów "mogę być dłużny/na grosika". Aby uniknąć takiej sytuacji kasjer powinien operować algorytmem wydawania reszty. Algorytm ten polega po prostu na tym, aby przy wydawaniu reszty użyć jak najmniejszej możliwej liczby banknotów/monet. Takie rozwiązania są zastosowane np. w bankomatach.

• metody rozwiązywania problemów

-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

-schematy blokowe

 

-programu Exel

 -Turbo Pascal

 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;

 

-program 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;
}

 

-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;
}