Algorytm wydawania reszty (metoda zachłanna)
Algorytm zachłanny, to taki algorytm, który w celu wyznaczenia rozwiązania w każdym kroku dokonuje najkorzystniejszego (zachłannego) w danym kroku rozwiązania częściowego.
Analizując sposób wydawania reszty uwzględniamy dostępne nominały w danym systemie monetarnym (bierzemy do uwagę banknoty i bilon). W każdym kolejnym kroku wydawania reszty wydaje się możliwie największych dostępnych nominałów niewiększych niż wydawana kwota.
Uwaga: Tablica z dostępnymi nominałami jest posortowana od największego nominału do najmniejszego.
Największą możliwą ilość wydawanego nominału w danym kroku iteracji jest wynik dzielenia bez reszty kwoty przez dopasowaną wartość nominału. Po każdym wydaniu części kwoty należy obliczyć pozostała resztę do wydania.
Algorytm powtarzany jest dopóki nie wypłaci się całej należnej kwoty.
Schemat algorytmu zachłannego wydawania reszty
Kod ciała funkcji algorytmu zachłannego wydawania reszty przedstawiony jest poniżej
Wskazówka:
void wydaj(float kwota,TextBox tb)
{
//kwota to kowata do wydania- reszta
int i=0;
while (kwota > 0)
{
if (kwota >= nominal[i])
{
int ileNominalow = (int)(kwota / nominal[i]);
//zaokraglij do 2 miejsca po przecinku (bo jest z dokładnością do 1 grosza)
//to co zostalo do wydania
kwota = (float)Math.Round(kwota - nominal[i] * ileNominalow, 2);
//wypisz do textBoxa kolejną wydaną resztę w obliczonyej ilości nominałów
tb.AppendText(ileNominalow.ToString()+" x "
+ nominal[i]+ "zł"
+Environment.NewLine);
}
i++;
}
}
Przykładowa aplikacja wydająca resztę metodą zachłanną
Pełny kod klasy Form utworzonej formatki dla aplikacji wydającej resztę
Wskazówka:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
namespace Alg8WydawanieReszty
{
public partial class Form1 : Form
{
//tablica mozliwych nominałów, w tym groszy
float[] nominal = { 500, 200, 100, 50, 20, 10, 5, 2, 1, 0.50f, 0.20f, 0.10f, 0.02f, 0.01f };
void wydaj(float kwota,TextBox tb)
{
//kwota to kowata do wydania- reszta
int i=0;
while (kwota > 0)
{
if (kwota >= nominal[i])
{
int ileNominalow = (int)(kwota / nominal[i]);
//zaokraglij do 2 miejsca po przecinku
//bo jest z dokładnością do 1 grosza
//to co zostalo do wydania
kwota = (float)Math.Round(kwota - nominal[i] * ileNominalow, 2);
//wypisz kolejną wydaną resztę w obliczonej ilości nominałów
tb.AppendText(ileNominalow.ToString()+" x "
+ nominal[i]+ "zł"
+Environment.NewLine);
}
i++;
}
}
public Form1()
{
InitializeComponent();
}
private void textBox1_KeyPress(object sender, KeyPressEventArgs e)
{
if (e.KeyChar == 8 || e.KeyChar==',') return; ;//wyskocz na BackeSpace lub przecinek
if (e.KeyChar < '0' || e.KeyChar > '9') e.Handled = true;
}
private void button1_Click(object sender, EventArgs e)
{
if (textBox1.Text.Length < 1) return;
textBox2.Clear();
float kwota=float.Parse(textBox1.Text);
wydaj(kwota, textBox2);
}
}
}
