Implementacja

Implementacja algorytmu wydawania reszty w języku C++

Problem 1

Zaimplementujemy funkcję zachlanneWydawanieReszty(), która dla zadanej reszty resztaDoWydania zwróci liczbę monet lub banknotów z n elementowej tablicy nominaly potrzebnych do jej wydania. Każdego nominału z tablicy nominaly możemy użyć dowolną liczbę razy.

Wykorzystamy uproszczony polski system monetarnysystem monetarnysystem monetarny.

Specyfikacja:

Dane:

resztaDoWydania – liczba naturalna; wartość reszty do wydania
n – liczba naturalna; liczba dostępnych nominałów
nominaly – tablica liczb naturalnych; tablica dostępnych nominałów posortowana malejąco

Wynik:

komunikat dotyczący wykorzystanych nominałów

Przykładowy komunikat:

Nominal 50 wydano 1 razy
Nominal 20 wydano 1 razy
Nominal 10 wydano 0 razy
Nominal 5 wydano 1 razy
Nominal 2 wydano 1 razy
Nominal 1 wydano 0 razy
Liczba nominalow uzytych do wydania reszty 77: 4

W kodzie źródłowym języka C++ przedstawiono przykładową implementację algorytmu zachłannegoalgorytm zachłannyalgorytmu zachłannego, który może zostać wykorzystany do rozwiązania problemu. Funkcja zachlanneWydawanieReszty() przyjmuje trzy parametry:

resztaDoWydania – wartość reszty do wydania,
nominaly – tablica dostępnych nominałów posortowana malejąco,
n – rozmiar tablicy, czyli po prostu liczba dostępnych nominałów.

Zmienna k wewnątrz pętli for przechowuje maksymalną liczbę powtórzeń nominału nominaly[i], przy pozostałej kwocie do wydania resztaDoWydania. Wartość resztaDoWydania jest zmniejszana o maksymalną wartość, którą można wydać danym nominałem. Algorytm zwraca liczbę monet lub banknotów użytych do wydania reszty o początkowej wartości resztaDoWydania.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int zachlanneWydawanieReszty otwórz nawias okrągły int resztaDoWydania przecinek int nominaly otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int wynik znak równości 0 średnik. Linia 8. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. int k znak równości resztaDoWydania prawy ukośnik nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. wynik znak równości wynik plus k średnik. Linia 11. resztaDoWydania znak równości resztaDoWydania minus k asterysk nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 13. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Nominal cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 14. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów wydano cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny k otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów razy cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 15. zamknij nawias klamrowy. Linia 17. return wynik średnik. Linia 18. zamknij nawias klamrowy. Linia 20. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. int nominaly otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 50 przecinek 20 przecinek 10 przecinek 5 przecinek 2 przecinek 1 zamknij nawias klamrowy średnik. Linia 22. int n znak równości sizeof otwórz nawias okrągły nominaly zamknij nawias okrągły prawy ukośnik sizeof otwórz nawias okrągły nominaly otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 23. int resztaDoWydania znak równości 77 średnik. Linia 24. int k znak równości zachlanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominaly przecinek n zamknij nawias okrągły średnik. Linia 26. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Liczba nominalow uzytych do wydania reszty cudzysłów średnik. Linia 27. cout otwórz nawias ostrokątny otwórz nawias ostrokątny resztaDoWydania otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów średnik. Linia 28. cout otwórz nawias ostrokątny otwórz nawias ostrokątny k średnik. Linia 30. return 0 średnik. Linia 31. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

int zachlanneWydawanieReszty(int resztaDoWydania, int nominaly[], int n) {
	int wynik = 0;

	for (int i = 0; i < n; i++) {
		int k = resztaDoWydania / nominaly[i];
		wynik = wynik + k;
		resztaDoWydania = resztaDoWydania - k * nominaly[i];

		cout << "Nominal " << nominaly[i];
		cout << " wydano " << k << " razy" << endl;
	}

	return wynik;
}

int main() {
	int nominaly[] = { 50, 20, 10, 5, 2, 1 };
    int n = sizeof(nominaly) / sizeof(nominaly[0]);    
	int resztaDoWydania = 77;
	int k = zachlanneWydawanieReszty(resztaDoWydania, nominaly, n);

	cout << "Liczba nominalow uzytych do wydania reszty ";
	cout << resztaDoWydania << ": ";
	cout << k;
    
    return 0;
}

Przyjrzyjmy się innej implementacji funkcji zachlanneWydawanieReszty(), która w celu określenia liczby nominałów, potrzebnej do wydania reszty resztaDoWydania, używa operacji dzielenia modulo. Możemy podzielić resztę resztaDoWydania przez nominał nominaly[i], a następnie wynik dzielenia zaokrąglić w dół, do całkowitej części liczby. Dzięki temu dowiemy się, ile sztuk danego nominału algorytm użyje do wydania reszty. Operacja resztaDoWydania % nominaly[i] zwróci informację o tym, jaka kwota pozostała do wydania.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int zachlanneWydawanieReszty otwórz nawias okrągły int resztaDoWydania przecinek int nominaly otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int wynik znak równości 0 średnik. Linia 8. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. int k znak równości resztaDoWydania prawy ukośnik nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 10. wynik znak równości wynik plus k średnik. Linia 11. resztaDoWydania znak równości resztaDoWydania procent nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 13. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Nominal cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny nominaly otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 14. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów wydano cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny k otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów razy cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 15. zamknij nawias klamrowy. Linia 17. return wynik średnik. Linia 18. zamknij nawias klamrowy. Linia 20. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. int nominaly otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 50 przecinek 20 przecinek 10 przecinek 5 przecinek 2 przecinek 1 zamknij nawias klamrowy średnik. Linia 22. int n znak równości sizeof otwórz nawias okrągły nominaly zamknij nawias okrągły prawy ukośnik sizeof otwórz nawias okrągły nominaly otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 23. int resztaDoWydania znak równości 77 średnik. Linia 24. int k znak równości zachlanneWydawanieReszty otwórz nawias okrągły resztaDoWydania przecinek nominaly przecinek n zamknij nawias okrągły średnik. Linia 26. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Liczba nominalow uzytych do wydania reszty cudzysłów średnik. Linia 27. cout otwórz nawias ostrokątny otwórz nawias ostrokątny resztaDoWydania otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów dwukropek cudzysłów średnik. Linia 28. cout otwórz nawias ostrokątny otwórz nawias ostrokątny k średnik. Linia 30. return 0 średnik. Linia 31. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

int zachlanneWydawanieReszty(int resztaDoWydania, int nominaly[], int n) {
	int wynik = 0;

	for (int i = 0; i < n; i++) {
		int k = resztaDoWydania / nominaly[i];
		wynik = wynik + k;
		resztaDoWydania = resztaDoWydania % nominaly[i];

		cout << "Nominal " << nominaly[i];
		cout << " wydano " << k << " razy" << endl;
	}

	return wynik;
}

int main() {
    int nominaly[] = { 50, 20, 10, 5, 2, 1 };
    int n = sizeof(nominaly) / sizeof(nominaly[0]);
	int resztaDoWydania = 77;
	int k = zachlanneWydawanieReszty(resztaDoWydania, nominaly, n);

	cout << "Liczba nominalow uzytych do wydania reszty ";
	cout << resztaDoWydania << ": ";
	cout << k;
    
    return 0;
}

Nie możemy zapomnieć o przypadku, w którym reszta będzie liczbą zmiennoprzecinkową. W Polsce do wydawania reszty po przecinku używamy nominałów 50 gr, 20 gr, 10 gr, 5 gr, 2 gr, 1 gr. W przypadku języka C++, podczas wydawania reszty, należy pamiętać o niedokładnościach w reprezentacji liczb zmiennoprzecinkowych. Operacje na takich liczbach powodują pewne niedokładności. Dlatego, aby nasze obliczenia były precyzyjne, najłatwiej jest zamienić wszystkie nominały na grosze. W takiej sytuacji resztę 19,99 zł zamienimy na 1999 gr, co pozwoli na łatwe i dokładne określenie minimalnej liczby monet lub banknotów potrzebnych do wydania reszty.

Słownik

algorytm zachłanny

algorytm dokonujący na każdym kroku takiego wyboru, który wydaje się w danym momencie najlepszy; zakładając, że seria wszystkich kroków doprowadzi do wyniku globalnie optymalnego

system monetarny

podział określonej waluty na nominały o określonej wartości

Eksperyment: zachłanny kontra optymalny

Strefa wyzwań

Implementacja algorytmu wydawania reszty w języku C++

Słownik