aFizyka logo

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

Schemat algorytmu zachłannego wydawania reszty Visual studio C#

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ą

aplikacja wydająca resztę metodą zachłanną Visual studio C#

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