Jak rozwiązywać problemy za pomocą algorytmów
Niniejszy artykuł pochodzi z książki pt. „Myślenie algorytmiczne. Jak rozwiązywać problemy za pomocą algorytmów” Daniela Zingaro (Helion 2022).
Problem. Promocja w supermarkecie
W supermarkecie każdy klient wybiera produkty, które chce kupić, a następnie idzie do kasy, by za nie zapłacić. Po zapłaceniu za zakupy otrzymuje paragon z sumaryczną ceną zakupionych produktów. Na przykład, jeśli ktoś wybrał produkty za 18 złotych, to całkowita cena zakupów wyświetlona na paragonie wyniesie 18 złotych. Nie interesują nas ceny poszczególnych produktów.
Supermarket organizuje promocję, która potrwa przez n dni. Podczas niej każdy paragon jest umieszczany w urnie do losowania. Pod koniec dnia z urny wyciągane są dwa paragony: jeden o maksymalnej wartości x złotych i drugi o minimalnej wartości y złotych. Właściciel paragonu o maksymalnej wartości otrzymuje zwrot, w kwocie x–y złotych. (Nie musimy się przejmować problemem, w jaki sposób supermarket identyfikuje właściciela paragonu). Po wyciągnięciu tych dwóch paragonów są one wyrzucane i już nigdy nie wracają do urny, wszystkie pozostałe paragony z tego dnia natomiast pozostają w urnie (i mogą zostać wylosowane i usunięte w następnych dniach promocji).
Każdego dnia do urny na pewno zostaną dodane co najmniej dwa nowe paragony.
Naszym zadaniem jest obliczenie całkowitej kwoty, którą supermarket zwróci klientom jako nagrody w ramach promocji.
Dane wejściowe
Dane wejściowe obejmują jeden przypadek testowy składający się z:
- Wiersza zawierającego liczbę całkowitą n określającą liczbę dni promocji. Wartość n mieści się w zakresie od 1 do 5000.
- n wierszy, po jednym dla każdego dnia promocji. Każdy z tych wierszy rozpoczyna się od liczby całkowitej k, która określa liczbę paragonów wrzuconych do urny danego dnia. W dalszej części wiersza zapisanych jest k liczb całkowitych reprezentujących kwoty na poszczególnych paragonach z danego dnia. Wartość k mieści się w zakresie od 0 do 100 000, a każdy paragon ma wartość nieprzekraczającą 1 000 000.
Całkowita liczba paragonów, które mogą się pojawić w trakcie promocji, nie przekracza 1 000 000.
Wyniki
Należy wyświetlić całkowitą sumę nagród, którą supermarket wypłaci podczas promocji. Limit czasu na podanie rozwiązania wynosi 1 sekundę.
Rozwiązanie. Wartość maksymalna i minimalna w tablicy
Od czego powinniśmy zacząć? Zapewne zaczęlibyśmy od pierwszego dnia promocji i kupowalibyśmy wszystko, może z wyjątkiem najtańszych cukierków za parę groszy. A potem pewnie byśmy wrócili i kupili także te cukierki.
A jak to przełożyć na język algorytmu?
W wielu problemach (…) dużym wyzwaniem jest wymyślenie prawidłowego algorytmu rozwiązania, a co dopiero takiego, który dodatkowo będzie wydajny. Jednak tym razem poprawność rozwiązania nie wydaje się być większym problemem. Określenie kwoty nagrody przekazywanej przez supermarket danego dnia sprowadza się do przeszukania urny i wybrania paragonu o maksymalnej i minimalnej wartości. A te operacje można wykonać stosunkowo efektywnie.
Przyjrzyjmy się takiemu przypadkowi testowemu:
2
16 6 63 16 82 25 2 43 5 17 10 56 85 38 15 32 91
1 57
Pod koniec pierwszego dnia i przed usunięciem jakichkolwiek paragonów mamy ich 16:
6 63 16 82 25 2 43 5 17 10 56 85 38 15 32 91
Maksymalna wartość paragonu w urnie wynosi zatem 91, a minimalna 2. Te dwa paragony zostają usunięte, a kwota nagrody wyniesie 91–2 = 89 złotych. Po usunięciu tych o wartościach 91 i 2 w urnie zostaną takie paragony:
6 63 16 82 25 43 5 17 10 56 85 38 15 32
Teraz przechodzimy do kolejnego dnia, w trakcie którego do urny zostaje dodany paragon o wartości 57 złotych; w ten sposób w urnie znajdują się paragony:
6 63 16 82 25 43 5 17 10 56 85 38 15 32 57
Maksymalna wartość paragonu w urnie wynosi teraz 85, a minimalna 5, zatem tego dnia nagroda wyniesie 85–5 = 80 złotych. Łączna kwota nagród w promocji wynosi zatem 89+80 = 169 złotych.
Jednym z potencjalnych sposobów rozwiązania tego problemu jest zapisanie wszystkich paragonów w tablicy. W takim wypadku paragon będziemy mogli usunąć dosłownie, tak jak wcześniej go dodaliśmy. Wymagałoby to także przesunięcia wszystkich pozostałych paragonów o jedno miejsce w lewo, by wypełnić lukę. Jednak łatwiejszym rozwiązaniem będzie skojarzenie z każdym paragonem flagi used, określającej, czy dany paragon został wylosowany, czy nie. Wartość 0 tej flagi będzie oznaczać, że dany paragon nie został jeszcze użyty, a wartość 1, że został wylosowany i logicznie usunięty z urny (więc w dalszych operacjach powinniśmy go pomijać).
Poniżej przedstawiam fragment kodu zawierający makra i definicję typu, których będziemy używać w kodzie:
#define MAX_RECEIPTS 1000000
#define MAX_COST 1000000
typedef struct receipt {
int cost;
int used;
} receipt;
Będziemy także potrzebować funkcji pomocniczych, pozwalających usunąć rachunki odpowiednio o maksymalnej i minimalnej wartości. Od razu przedstawiam ich kod (patrz listing), byśmy nie musieli później się nimi przejmować.
int extract_max(receipt receipts[], int num_receipts) {
int max, max_index, i;
max = -1; ❶
for (i = 0; i < num_receipts; i++)
if (!receipts[i].used && receipts[i].cost > max) { ❷
max_index = i;
max = receipts[i].cost;
}
receipts[max_index].used = 1; ❸
return max;
}
int extract_min(receipt receipts[], int num_receipts) {
int min, min_index, i;
min = MAX_COST + 1; ❹
for (i = 0; i < num_receipts; i++)
if (!receipts[i].used && receipts[i].cost < min) { ❺
min_index = i;
min = receipts[i].cost;
}
receipts[min_index].used = 1; ❻
return min;
}
Standardowym terminem dla operacji realizowanych przez pierwszą z tych funkcji jest usunięcie minimum (ang. extract-min), a dla operacji realizowanych przez drugą z nich — usunięcie maksimum (ang. extract-max).
Obie te funkcje działają w bardzo podobny sposób. Funkcja extract_max
przypisuje zmiennej max wartość -1 ❶, czyli mniejszą od wartości każdego możliwego paragonu. Kiedy funkcja odczyta wartość „prawdziwego” paragonu, przypisze ją zmiennej max i od tej pory funkcja będzie zapamiętywać największą wartość paragonu, jaką udało się jej do tej pory znaleźć. W podobny sposób możemy wyjaśnić, dlaczego funkcja extract_min
początkowo przypisuje zmiennej min największą dopuszczalną wartość paragonu ❹. Zwróć uwagę, że obie funkcje uwzględniają wyłącznie te paragony, w których pole used
ma wartość 0
❷ i ❺. Podobnie każda z funkcji zapisuje w polu used znalezionego paragonu wartość 1 ❸ i ❻.
Skoro dysponujemy tymi dwiema funkcjami pomocniczymi, możemy już napisać funkcję main
, która odczyta dane wejściowe i rozwiąże problem. Interesującym aspektem tego problemu jest to, że odczytanie danych tekstowych i znalezienie rozwiązania są ze sobą wzajemnie powiązane: wczytujemy mały fragment danych wejściowych (paragony z pierwszego dnia), obliczamy wartość nagrody wypłaconej tego dnia, wczytujemy następny fragment danych wejściowych (paragony z drugiego dnia), obliczamy wartość nagrody wypłaconej tego dnia itd. Kod funkcji main
przedstawiam na poniższym listingu.
int main(void) {
static struct receipt receipts[MAX_RECEIPTS];
int num_days, num_receipts_today;
int num_receipts = 0;
long long total_prizes = 0; ❶
int i, j, max, min;
scanf("%d", &num_days);
for (i = 0; i < num_days; i++) {
scanf("%d", &num_receipts_today);
for (j = 0; j < num_receipts_today; j++) {
scanf("%d", &receipts[num_receipts].cost);
receipts[num_receipts].used = 0;
num_receipts++;
}
max = extract_max(receipts, num_receipts);
min = extract_min(receipts, num_receipts);
total_prizes += max - min;
}
printf("%lld\n", total_prizes);
return 0;
}
Jedyną ciekawostką zastosowaną w tym kodzie jest typ zmiennej total_prizes
❶. Zakres wartości typów int
i long
mogą być zbyt małe. Typowa liczba typu long
może przechowywać wartości do około 4 000 000 000, wartość całkowitej łącznej nagrody może wynieść do 5000×1 000 000, czyli 5 000 000 000. Zmienne typu llong
long
mogą przechowywać wartości liczbowe sięgające wielu miliardów, trylionów, a nawet jeszcze większe, dlatego też zastosowanie tego typu na pewno będzie bezpiecznym rozwiązaniem.
Zewnętrzna pętla jest wykonywana raz dla każdego dnia trwania promocji, z kolei pętla wewnętrzna odczytuje wartość każdego paragonu. Po wczytaniu wszystkich paragonów z danego dnia znajdujemy i usuwamy te o wartości maksymalnej i minimalnej, a następnie wyliczamy kwotę nagrody.
To kompletne rozwiązanie postawionego problemu. Dla naszego przykładowego przypadku testowego zwróci ono prawidłową wartość 169 i trzeba by poświęcić trochę czasu, aby zyskać pewność, że jego sposób działania jest, ogólnie rzecz biorąc, prawidłowy.
Niestety, okazuje się, że rozwiązanie to jest także zbyt wolne, o czym wyraźnie świadczy komunikat o przekroczeniu limitu czasu, który na pewno zobaczysz, gdy spróbujesz opublikować je na witrynie oceniającej.
Problem braku wydajności tego rozwiązania możemy oszacować poprzez analizę najbardziej pesymistycznego ze wszystkich przypadków. Załóżmy, że promocja trwa 5000 dni i że podczas każdego z pierwszych 10 dni promocji do urny wrzucono 100 000 paragonów. To oznacza, że po 10 dniach będziemy mieli w tablicy około 1 000 000 paragonów. Znalezienie wartości maksymalnej i minimalnej wymaga liniowego przeglądnięcia tablicy. Ponieważ usuwamy tylko dwa paragony dziennie, to przez cały dalszy okres promocji będziemy ich mieli w urnie prawie 1 000 000. Promocja trwa 5000 dni, a niemal w każdym z tych dni musimy wykonać około 1 000 000 kroków w celu znalezienia maksimum i około kolejnego 1 000 000 kroków w celu znalezienia minimum. To nam daje 5000×2 000 000, czyli 10 000 000 000 kroków! Nie ma najmniejszych szans, by rozwiązać ten problem w tak krótkim czasie jak 1 sekunda. Gdybyśmy tylko mogli w jakiś sposób przyspieszyć operacje znajdowania paragonów o maksymalnej i minimalnej wartości…
Zacznijmy może od szybkiego wykluczenia sortowania jako potencjalnej metody na przyspieszenie rozwiązania. Gdybyśmy byli w stanie zapewnić, że tablica paragonów zawsze będzie posortowana, to znalezienie i usunięcie wartości maksymalnej trwałoby tyle samo, gdyż wartość tę można by odczytać przy użyciu skrajnego, prawego indeksu tablicy. Także znalezienie minimum zabierałoby tyle samo czasu, jednak czas konieczny do usunięcia tego elementu rósłby liniowo, gdyż usunięcie go wymagałoby przesunięcia wszystkich pozostałych elementów o jeden w lewo. Sortowanie psuje także wydajność dodawania poszczególnych paragonów: jeśli ich nie sortujemy, to możemy po prostu zapisywać każdy kolejny paragon na końcu tablicy; kiedy zaczniemy je sortować, będziemy musieli znajdować odpowiednie miejsce tablicy do wstawienia nowego paragonu. Zatem sortowanie nie jest żadnym rozwiązaniem. Tym rozwiązaniem są kopce.
Artykuł stanowi fragment książki pt. „Myślenie algorytmiczne. Jak rozwiązywać problemy za pomocą algorytmów” Daniela Zingaro (Helion 2022)