Algorytm wydawania reszty - metoda zachłanna, implementacja Python, C++ i Java | Korepetycje do matury z informatyki

12 czerwca 2025
Posted by: Damian
Category: Baza wiedzy

Algorytm wydawania reszty jest rozwiązaniem stosowanym w informatyce od długiego czasu, który pozwala rozwiązać problem związany z najbardziej optymalnym wydawaniem reszty. W artykule przedstawię najpopularniejsze podejścia do tego algorytmu, omówię jego teoretyczne podstawy oraz zaprezentuję praktyczne rozwiązania, które mogą być zaimplementowane w różnych językach programowania.

Spis treści

1 Problem wydawania reszty – Kalkulator

2 Co to algorytm wydawania reszty?

2.1 Jak działa algorytm wydawania reszty?

2.2 Przykład działania algorytmu wydawania reszty

3 Algorytm wydawania reszty – Implementacje

3.1 Metoda zachłanna: Algorytm wydawania reszty – Schemat blokowy i pseudokod

3.2 Metoda zachłanna: Algorytm wydawania reszty – Python, C++ i Java

3.3 Czy algorytm zachłanny zawsze zwraca optymalną wartość?

4 QUIZ – Sprawdź swoją wiedzę

5 Najczęściej zadawane pytania o algorytm wydawania reszty

Problem wydawania reszty – Kalkulator

Algorytm wydawania reszty

–

Wynik

Komunikat:
Wynik:

Co to algorytm wydawania reszty?

Algorytm wydawania reszty pozwala rozbić określoną kwotę reszty, którą należy zwrócić klientowi na najmniejszą liczbę monet i banknotów (przy użyciu dostępnych nominałów). Kluczowe jest rozbicie tej kwoty w najbardziej efektywny sposób, dzięki czemu liczba monet i banknotów jest minimalna.

Jak działa algorytm wydawania reszty?

Algorytm najczęściej opiera się na podejściu zachłannym, które polega na tym, że w każdym kroku wybieramy największy możliwy nominał, który nie przekroczy pozostałej kwoty reszty. Proces powtarzamy, aż kwota reszty zostanie w pełni wydana, co widać na przykładzie widocznym w kolejnym podpunkcie.

Taki algorytm jest szybki, prosty do implementacji i zapewnia optymalną liczbę nominałów. Dzięki niemu można efektywnie zarządzać procesem wydawania reszty w sklepach, automatów sprzedażowych, kasach samoobsługowych i innych systemach płatniczych.

Przykład działania algorytmu wydawania reszty

Działanie tego algorytmu okazuje się proste, co widać na poniższym gifie.

Algorytm wydawania reszty - GIF — Algorytm wydawania reszty to metoda obliczania, jak najlepiej wydać określoną kwotę, używając dostępnych nominałów (monet i banknotów).

Załóżmy, że klient płaci kwotą 100 zł za zakupy o wartości 47,50 zł. Reszta wynosi 52,50 zł. Aby wydać tę kwotę, algorytm wydawania reszty zacznie od najwyższego dostępnego nominału:

Rozpoczynamy od najwyższego dostępnego nominału (50 zł):

Reszta = 52,50 zł
Wydajemy 50 zł (jedno 50-złotowe), zostaje 2,50 zł.

Przechodzimy do następnego nominału (2 zł):

Reszta = 2,50 zł
Wydajemy 2 zł (jedną monetę 2-złotową), zostaje 0,50 zł.

Przechodzimy do monety 0,50 zł:

Reszta = 0,50 zł
Wydajemy 0,50 zł (jedną monetę 50-groszową), zostaje 0 zł.

W efekcie klient otrzyma: jedno 50-złotowe, dwa 1-złotowe oraz jedną monetę 50-groszową, co jest najprostszym i najbardziej efektywnym sposobem wydania reszty.

Algorytm wydawania reszty – Implementacje

Poniżej znajdziesz algorytm wydawania reszty w formie schematu blokowego, pseudokodu, a także w Pythonie, C++ i Java.

Metoda zachłanna: Algorytm wydawania reszty – Schemat blokowy i pseudokod

Algorytm wydawania reszty - Schemat blokowy zachłannie — Zaczyna od największego nominału i stara się wydać jak najwięcej za pomocą tego nominału, a następnie przechodzi do mniejszych nominałów.

Funkcja WydawanieReszty(reszta):
    nominal ← [500, 200, 100, 50, 20, 10, 5, 2, 1]
    i ← 1
    dopóki reszta > 0 wykonuj
        jeśli reszta ≥ nominaly[i]
            wydanie ← reszta / nominaly[i]
            wypisz (wydanie, "x", nominaly[i])
            reszta ←  reszta % nominaly[i]
        i ← i + 1

Funkcja WydawanieReszty(reszta):

nominal ← [500, 200, 100, 50, 20, 10, 5, 2, 1]

i ← 1

dopóki reszta > 0 wykonuj

jeśli reszta ≥ nominaly[i]

wydanie ← reszta / nominaly[i]

wypisz (wydanie, "x", nominaly[i])

reszta ← reszta % nominaly[i]

i ← i + 1

Opis zachłannego algorytmu wydawania reszty – Pseudokod

1 linia – Definiujemy funkcję o nazwie WydawanieReszty, która przyjmuje argument reszta, czyli kwotę, którą należy wydać w odpowiednich nominałach.
2 linia – Tworzymy listę nominaly, która zawiera dostępne nominały (monety i banknoty) w porządku malejącym, zaczynając od największego nominału 500.
3 linia – Inicjalizujemy zmienną i, która będzie pełnić rolę wskaźnika do aktualnego nominału w liście. Początkowo ustawiamy ją na 1, czyli zaczynamy od największego nominału.
4 linia – Uruchamiamy pętlę dopóki, która będzie działała tak długo, jak długo reszta jest większa niż 0. Pętla ta będzie rozbijała kwotę reszta na kolejne nominały.
5 linia – Wewnątrz pętli, sprawdzamy warunek: jeśli reszta jest większa lub równa aktualnemu nominałowi (nominaly[i]), przechodzimy do linii 6, w przeciwnym razie przechodzimy do linii 9.
6 linia – Jeśli warunek jest spełniony (tzn. reszta jest większa lub równa aktualnemu nominałowi), obliczamy ile razy możemy wydać ten nominał, dzieląc reszta przez nominaly[i]. Wynik zapisujemy w zmiennej wydanie. Następnie wypisujemy wynik, który pokazuje, ile razy wydajemy dany nominał.
7 linia – Wypisujemy wartość nominału i ile banknotów lub monet wydajemy

8 linia – Aktualizujemy wartość reszta, obliczając resztę z dzielenia (reszta % nominaly[i]) po wydaniu nominałów. Oznacza to, że po wydaniu jakiejś liczby nominałów, pozostaje nam do wydania nowa, mniejsza reszta.
9 linia – Jeśli warunek z linii 5 nie był spełniony, przechodzimy do kolejnego nominału. Zmienna i jest inkrementowana o 1, co oznacza, że w następnej iteracji pętli rozważymy mniejszy nominał.

Metoda zachłanna: Algorytm wydawania reszty – Python, C++ i Java

Algorytm wydawania reszty – Python

def WydawanieReszty(reszta):
    nominaly = [500, 200, 100, 50, 20, 10, 5, 2, 1]
    i = 0

    while reszta > 0:
        if reszta >= nominaly[i]:
            wydanie = reszta // nominaly[i]
            print(f"{wydanie}x{nominaly[i]}", end=' ')

            reszta = reszta % nominaly[i]

    i += 1

reszta = int(input("Podaj kwotę do wydania: "))
WydawanieReszty(reszta)

def WydawanieReszty(reszta):

nominaly = [500, 200, 100, 50, 20, 10, 5, 2, 1]

i = 0

while reszta > 0:

if reszta >= nominaly[i]:

wydanie = reszta // nominaly[i]

print(f"{wydanie}x{nominaly[i]}", end=' ')

reszta = reszta % nominaly[i]

i += 1

reszta = int(input("Podaj kwotę do wydania: "))

WydawanieReszty(reszta)

Algorytm wydawania reszty – C++

#include <iostream>
using namespace std;

void WydawanieReszty(int reszta) {
	int nominaly[] = {500, 200, 100, 50, 20, 10, 5, 2, 1};
	int i = 0;

	while (reszta > 0) {
    	if (reszta >= nominaly[i]) {
        	int wydanie = reszta / nominaly[i];
        	cout << wydanie << "x" << nominaly[i] << " ";

        	reszta = reszta % nominaly[i];
    	}
    	i++;
	}
}

int main() {
	int reszta;
	cout << "Podaj kwotę do wydania: ";
	cin >> reszta;

	WydawanieReszty(reszta);
	return 0;
}

#include <iostream>

using namespace std;

void WydawanieReszty(int reszta) {

int nominaly[] = {500, 200, 100, 50, 20, 10, 5, 2, 1};

int i = 0;

while (reszta > 0) {

if (reszta >= nominaly[i]) {

int wydanie = reszta / nominaly[i];

cout << wydanie << "x" << nominaly[i] << " ";

reszta = reszta % nominaly[i];

}

i++;

}

int main() {

int reszta;

cout << "Podaj kwotę do wydania: ";

cin >> reszta;

WydawanieReszty(reszta);

return 0;

}

Algorytm wydawania reszty – Java

import java.util.*;

public class WydawanieReszty {

	public static void WydawanieReszty(int reszta) {
    	int[] nominaly = {500, 200, 100, 50, 20, 10, 5, 2, 1};
    	int i = 0;

    	while (reszta > 0) {
        	if (reszta >= nominaly[i]) {
            	int wydanie = reszta / nominaly[i];
            	System.out.print(wydanie + "x" + nominaly[i] + " ");

            	reszta = reszta % nominaly[i];
        	}
        	i++;
    	}
	}

	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	System.out.print("Podaj kwotę do wydania: ");
    	int reszta = sc.nextInt();
    	WydawanieReszty(reszta);
	}
}

import java.util.*;

public class WydawanieReszty {

public static void WydawanieReszty(int reszta) {

int[] nominaly = {500, 200, 100, 50, 20, 10, 5, 2, 1};

int i = 0;

while (reszta > 0) {

if (reszta >= nominaly[i]) {

int wydanie = reszta / nominaly[i];

System.out.print(wydanie + "x" + nominaly[i] + " ");

reszta = reszta % nominaly[i];

}

i++;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

System.out.print("Podaj kwotę do wydania: ");

int reszta = sc.nextInt();

WydawanieReszty(reszta);

}

Czy algorytm zachłanny zawsze zwraca optymalną wartość?

Tak w przypadku złotówek. W innych krajach zdarza się, że nie ma odpowiednika naszego 1 grosza np. w Kanadzie. Gdyby w polsce nie było jednogroszówki, algorytm zachłanny nie zwracałby poprawnych wyników. Zobaczmy wynik dla 6 groszy, poprawna odpowiedź to 3 x 2 grosze, ale nasz algorytm próbowałby zwrócić 5 groszy i potem miałby poważny problem.

Jednak algorytm może też zwrócić poprawnie resztę, ale nie w optymalny sposób, np. gdyby istniała moneta 4 złotowa. 8 zł można zwrócić w dwóch monetach po 4 złote, ale nasz algorytm zwróciłby resztę w formie 1 x 5 zł, 1 x 2 zł, 1 x 1 zł.

QUIZ – Sprawdź swoją wiedzę

Najczęściej zadawane pytania o algorytm wydawania reszty

Na czym polega algorytm wydawania reszty metodą zachłanną?

Algorytm wydawania reszty metodą zachłanną polega na wydawaniu jak największych możliwych nominałów, aż do wyczerpania całej kwoty reszty. Zaczyna się od największego nominału i stopniowo przechodzi do mniejszych, minimalizując liczbę wydanych monet i banknotów.

Na czym polega algorytm wydawania reszty metodą dynamiczną?

Algorytm wydawania reszty metodą dynamiczną polega na rozwiązywaniu problemu wydania reszty poprzez analizowanie wszystkich możliwych kombinacji nominałów. Używa tablicy, aby zapisać najmniejszą liczbę monet potrzebnych do wydania każdej możliwej kwoty, i stopniowo buduje rozwiązanie od najniższej kwoty do docelowej.

Algorytm wydawania reszty – metoda zachłanna, implementacja Python, C++ i Java

Problem wydawania reszty – Kalkulator

Co to algorytm wydawania reszty?

Jak działa algorytm wydawania reszty?

Przykład działania algorytmu wydawania reszty

Algorytm wydawania reszty – Implementacje

Metoda zachłanna: Algorytm wydawania reszty – Schemat blokowy i pseudokod

Metoda zachłanna: Algorytm wydawania reszty – Python, C++ i Java

Czy algorytm zachłanny zawsze zwraca optymalną wartość?

QUIZ – Sprawdź swoją wiedzę

Najczęściej zadawane pytania o algorytm wydawania reszty

Rozkład na czynniki pierwsze – co to czynniki pierwsze, kalkulator oraz implementacja algorytmu

Ciąg Fibonacciego: algorytm, schemat blokowy i kalkulator

Sortowanie przez wstawianie – co to jest, schemat blokowy oraz implementacja

Dbamy o prywatność Twoich danych

Mapa witryny: Korepetycje z informatyki

Polecane wpisy na blogu poświęconemu nauce informatyki