Wydawanie reszty — kiedy zachłanność jest bezpieczna
🎯 Po co Ci to?
Kasjerka wydaje Ci 76 groszy reszty i nie zastanawia się ani sekundy: 50, 20, 5, 1. Cztery monety — i nie da się mniej. Wykonała algorytm zachłanny (znasz go z 1.4), nie wiedząc o tym — i wykonała go bezbłędnie, choć w ogólności zachłanność potrafi kłamać. Dziś zapiszesz ten algorytm porządnie, przetestujesz jego granice i postawisz pytanie, które odróżnia rzemieślnika od myśliciela: skąd wiadomo, że dla naszych monet zachłanność zawsze daje optimum? Odpowiedź nie jest oczywista — i podstawa programowa (słusznie) każe ten algorytm znać każdemu.
✅ Czego się nauczysz
Po tej jednostce potrafisz:
- zapisać zachłanne wydawanie reszty i prześledzić je dla dowolnej kwoty;
- podać przykład systemu monet, w którym zachłanność NIE daje optimum;
- wyjaśnić, na czym polega problem optymalizacyjny i czym różni się od „znajdź jakiekolwiek".
🔁 Przypomnij sobie
Z 1.4: podejście zachłanne — lokalnie najlepszy wybór bez oglądania się; z 3.3: pętla while z malejącą resztą.
📘 Wyjaśnienie
📐 DEFINICJA — problem optymalizacyjny: problem, w którym rozwiązań jest wiele, każde ma wartość (koszt, zysk, liczbę monet), a szukamy rozwiązania o wartości najlepszej (najmniejszej lub największej).
Po ludzku: nie „czy da się wydać 76 gr" (da się na mnóstwo sposobów), tylko „jak wydać NAJMNIEJ monetami". Czym NIE jest: problemem decyzyjnym („czy istnieje…") ani wyszukiwaniem („znajdź element…"). Optymalizacja porównuje rozwiązania między sobą — i to podnosi poprzeczkę: mało znaleźć dobre, trzeba uzasadnić, że lepszego nie ma.
Algorytm zachłanny dla reszty: bierz największy nominał, który się mieści, tyle razy, ile się da; przejdź do mniejszego:
def reszta(kwota, nominaly=[500, 200, 100, 50, 20, 10, 5, 2, 1]):
wynik = [] # kwoty w groszach — pamiętasz 2.4!
for n in nominaly: # nominały od największego
while kwota >= n:
wynik.append(n)
kwota = kwota - n
return wynik
reszta(76) → 50 (zostaje 26), 20 (6), 5 (1), 1 (0) → [50, 20, 5, 1]. Cztery monety. Algorytm jest szybki (jedno przejście po nominałach), prosty i… dla polskich nominałów optymalny. Ale słowo „dla polskich" niesie cały ciężar tego zdania.
💭 Pomyśl: Królestwo Trójkątów ma monety 1, 3 i 4. Wydaj zachłannie resztę 6. A jak wydałby ją ktoś myślący? Co poszło nie tak?
Sprawdź odpowiedź
Zachłannie: 4 (zostaje 2), 1, 1 — trzy monety. Myśląco: 3 + 3 — dwie. Zachłanność przegrała, bo wzięcie największej czwórki „zablokowało" elegancki podział na trójki: lokalnie najlepszy ruch zepsuł globalny wynik. To nie jest błąd w kodzie — kod działa dokładnie tak, jak ma; to błąd strategii dla tego systemu monet. Wniosek fundamentalny: poprawność zachłanności zależy od struktury problemu, nie od staranności programisty.
Kiedy więc zachłanność jest bezpieczna? Dla systemów monet takich jak polski czy euro (nominały 1-2-5 razy potęgi dziesiątki) da się udowodnić, że zachłanność zawsze daje minimum — kluczowa własność: każdy nominał jest „wystarczająco duży" względem mniejszych (np. dwie dwudziestki to więcej niż pięćdziesiątka? nie — 40 < 50… własność jest subtelniejsza: żadna kombinacja mniejszych nominałów zastępująca większy nie jest krótsza). Dowód wykracza poza program — ale sama świadomość, że dowodu potrzeba, jest w programie jak najbardziej: zachłanny algorytm bez uzasadnienia to hipoteza, nie rozwiązanie. W jednostce 8.2 zobaczysz problem, gdzie zachłanność przegrywa z hukiem, a w 8.3 — metodę, która radzi sobie z każdym systemem monet.
🐞 Znajdź błąd
Ktoś „ulepszył" algorytm, żeby zwracał tylko liczbę monet:
def ile_monet(kwota, nominaly=[500, 200, 100, 50, 20, 10, 5, 2, 1]):
ile = 0
for n in nominaly:
ile = ile + kwota // n # ile razy nominał mieści się w kwocie
kwota = kwota % n # reszta po tych monetach
return ile
Sprytne — dzielenie całkowite zamiast pętli while! Czy to jest poprawne? Przetestuj na 76 i na… no właśnie, na czym warto?
Sprawdź odpowiedź
Jest poprawne — kwota // n to dokładnie liczba obrotów pętli while, a kwota % n to reszta po nich (jedno divmod zamiast wielu odejmowań — ta sama zamiana, którą Euklides z resztą wygrał z odejmowaniem w 4.2!). Testy warte uwagi: 0 (zero monet ✓), 1 (jedna ✓), 500 (jedna ✓), 999 (5+2+2… policz: 500+200+200+50+20+10+5+2+2 → 9 monet ✓). To rzadki przypadek 🐞 bez błędu — celowo: sprawdzanie poprawnego kodu to też umiejętność, a odruch „skoro pytają, musi być błąd" bywa zawodny. Na maturze również.
🌍 Powiązania
Zachłanność spotkasz wszędzie tam, gdzie decyzje zapadają „na bieżąco, bez cofania": planowanie zajęć (bierz najwcześniej kończące się — to akurat daje optimum!), pakowanie plików na dysk, trasy śmieciarek, a nawet Twój sposób jedzenia frytek (najpierw najlepsze — strategia dyskusyjna). Część tych zachłanności jest dowodliwie optymalna, część to tylko heurystyka (1.6!) — cała sztuka w odróżnianiu. Nawet kompresja z 2.6 ma zachłanne serce: kody Huffmana buduje się, łącząc zachłannie dwa najrzadsze symbole — i to akurat jest optymalne, z dowodem.
🛠️ Teraz Ty
Bez komputera: wydaj zachłannie 1 zł 37 gr (137 gr) i 2 zł 88 gr; potem w systemie monet {1, 5, 8} wydaj 10 zachłannie i optymalnie. Z komputerem: zaimplementuj reszta tak, by zwracała pary (nominał, ile sztuk) — np. dla 999 gr → [(500,1), (200,2), (50,1), (20,2), (5,1), (2,2)] — i przetestuj na brzegach (0, 1, wielokrotność nominału).
📐 Definicje tej lekcji
- Problem optymalizacyjny — wiele rozwiązań o różnych wartościach; szukamy najlepszego.
- Algorytm zachłanny — w każdym kroku wybór lokalnie najlepszy, bez cofania; optymalny tylko dla problemów o odpowiedniej strukturze.
📌 Najważniejsze w pigułce
- Reszta zachłannie: od największego nominału,
//i%zamiast pętli odejmowań. - Dla polskich nominałów zachłanność jest optymalna; dla monet {1, 3, 4} — już nie: strategia zależy od struktury problemu.
- Zachłanny algorytm bez uzasadnienia optymalności to hipoteza — miej odruch pytania „skąd wiadomo, że najlepiej?".
🎒 Zadania
- Wydaj zachłannie 99 gr, 638 gr i 1024 gr (nominały polskie, w groszach). Dla każdej kwoty podaj listę monet i ich liczbę.
Wskazówka i odpowiedź
99 → 50+20+20+5+2+2 (6 monet). 638 → 500+100+20+10+5+2+1 (7). 1024 → 500+500+20+2+2 (5). Rytm jest zawsze ten sam: bierz największy, aż przestanie się mieścić. Zauważ w 638 gładkie „schodzenie" przez nominały — system 1-2-5 jest tak zaprojektowany, żeby reszta wydawała się krótko; to nie przypadek, tylko decyzja projektantów systemów monetarnych (tak, oni też myślą algorytmicznie).
- W systemie {1, 10, 25} wydaj zachłannie i optymalnie kwotę 30. Uogólnij: co „psuje" ten system, że zachłanność zawodzi?
Wskazówka i odpowiedź
Zachłannie: 25+1+1+1+1+1 — sześć monet. Optymalnie: 10+10+10 — trzy. Psuje to, że 25 nie jest „zgodne" z 10: wzięcie 25 zostawia 5, którego nie ma czym ładnie domknąć, a trzy dziesiątki domykają idealnie. Ogólna intuicja: zachłanność zawodzi, gdy duży nominał nie jest wielokrotnością mniejszych „w rytmie" kwot — lokalny zysk (25 zamiast 10) niszczy globalne dopasowanie. Amerykański system ćwierćdolarówek naprawdę ma monety 1-5-10-25 — i tam akurat zachłanność działa; granica jest naprawdę subtelna.
- Problem spotkań: masz listę zajęć (początek, koniec) i jedną salę; chcesz zmieścić jak najwięcej zajęć bez nakładania. Zachłanność „bierz najkrótsze" i „bierz najwcześniej się zaczynające" obie zawodzą — pokaż kontrprzykłady. (Zachłanność „najwcześniej się kończące" jest optymalna — możesz spróbować poczuć dlaczego.)
Wskazówka i odpowiedź
„Najkrótsze": zajęcia 10–12 i 12–14 (dwa) kontra krótkie 11:30–12:30 (jedno, ale blokuje oba) — zachłanność na krótkość bierze środek i kończy z jednym. „Najwcześniejszy start": długaśne 8–16 startuje pierwsze i blokuje wszystko. „Najwcześniejszy koniec" wygrywa, bo zostawia salę wolną najszybciej — każdy inny pierwszy wybór kończy się nie wcześniej, więc nie może pozwolić na więcej. To słynny przykład zachłanności z dowodem — i lekcja, że nawet w jednym problemie różne „zachłanności" mają różny los. Wybór kryterium zachłanności to decyzja projektowa, nie odruch.
🔍 Sprawdź, czy umiesz
- Wydać resztę zachłannie na kartce i w kodzie (wersja z
//i%). - Podać z pamięci kontrprzykład {1, 3, 4} i wyjaśnić, co poszło nie tak.
- Odróżnić problem optymalizacyjny od decyzyjnego i wyszukiwania.