LO – Algorytmy zachłanne: wyjaśnienia programów

Wydawanie reszty metodą zachłanną

NOMINALY = (5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01)
N = len(NOMINALY)

def WydajReszte(reszta):
    i = 0
    while reszta > 0 and i < N:
        if reszta >= NOMINALY[i]:
            print(NOMINALY[i])
            reszta = reszta - NOMINALY[i]
        else:
            i += 1

reszta = float(input("Podaj kwotę reszty: "))
WydajReszte(reszta)

1. Lista nominałów

NOMINALY to krotka zawierająca nominały od największego do najmniejszego: 5, 2, 1, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01. Dzięki temu program działa zachłannie – wydaje najpierw największy możliwy nominał.

2. Zmienna N

N = len(NOMINALY) – zapisuje liczbę nominałów (czyli 9).

3. Funkcja WydajReszte(reszta)

Funkcja przyjmuje kwotę reszty, a następnie stara się wydać ją za pomocą dostępnych nominałów.

4. Zmienna i

i = 0 – indeks aktualnego nominału. Zaczyna od największego.

5. Pętla while

Program działa, dopóki kwota reszty jest większa od zera i nie skończyły się nominały: while reszta > 0 and i < N.

6. Warunek if

Jeśli aktualny nominał mieści się w reszcie (reszta >= NOMINALY[i]), to zostaje „wydany” – wypisany, a reszta pomniejszona. Jeśli nie, program przechodzi do mniejszego nominału (i += 1).

7. Przykład działania

Dla kwoty 12.37 program wyda kolejno: 5, 5, 2, 0.2, 0.1, 0.05, 0.02.

8. Uwaga float!

W praktyce operacje finansowe wykonuje się na groszach (liczbach całkowitych), bo typ float może generować błędy zaokrągleń. Tu jednak program służy do zrozumienia algorytmu.

Analiza programu – Problem kinomana

Zacznijmy od ogólnej myśli, a potem rozbierzemy program linijka po linijce. Ten program rozwiązuje klasyczny problem:

„Na festiwalu filmowym jest wiele seansów. Każdy ma godzinę rozpoczęcia i zakończenia. Jak wybrać jak najwięcej filmów tak, żeby się nie nakładały?”

Program:

ma listę filmów z godzinami rozpoczęcia i zakończenia,
sortuje je według godziny zakończenia,
potem chciwie (greedy) wybiera filmy tak, aby były niekolidujące.

1. Dane wejściowe – lista filmów

P = [9, 16, 15, 18, 14, 10, 10, 13, 15, 18]   # początek
K = [10, 17, 17, 21, 15, 14, 11, 14, 17, 20]  # koniec
IDEN = ["F0", "F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8", "F9"]
N = len(P)

P[i] – start filmu
K[i] – koniec filmu
IDEN[i] – identyfikator filmu
N – liczba filmów

Listy są równoległe – film F3 to:

P[3] = 18 (start)
K[3] = 21 (koniec)
IDEN[3] = "F3"

2. Funkcja Sortuj – sortowanie po zakończeniu filmu

To klasyczny insertion sort, działający równocześnie na trzech listach.

def Sortuj(koniec, poczatek, iden):
    for i in range(1, N):
        pom_koniec = koniec[i]
        pom_poczatek = poczatek[i]
        pom_iden = iden[i]
        j = i - 1
        while j >= 0 and koniec[j] > pom_koniec:
            koniec[j+1] = koniec[j]
            poczatek[j+1] = poczatek[j]
            iden[j+1] = iden[j]
            j -= 1

        koniec[j+1] = pom_koniec
        poczatek[j+1] = pom_poczatek
        iden[j+1] = pom_iden

Krok po kroku:

Dla każdego elementu od 1 do N–1 próbujemy wstawić go w posortowaną część listy.
Zapamiętujemy wstawiany film (pom_koniec, pom_poczatek, pom_iden).
Przesuwamy w prawo wszystkie filmy, które kończą się później.
Wstawiamy film na właściwe miejsce.

Efekt: filmy są posortowane rosnąco wg czasu zakończenia (K).

3. Funkcja Wypisz – wypisanie jednego filmu

def Wypisz(koniec, poczatek, iden, k):
    print(iden[k], ":", poczatek[k], "-", koniec[k])

Drukuje np.: F3 : 18 - 21

4. Funkcja Wybierz – sedno algorytmu greedy

def Wybierz(koniec, poczatek, iden):
    Wypisz(koniec, poczatek, iden, 0)
    koniec_poprzedniego = koniec[0]
    for i in range(1, N):
        if poczatek[i] > koniec_poprzedniego:
            Wypisz(koniec, poczatek, iden, i)
            koniec_poprzedniego = koniec[i]

Działa tak:

Wybiera pierwszy film (ten kończący się najwcześniej po sortowaniu).
Zapamiętuje, kiedy się kończy.

Dla każdego kolejnego filmu sprawdza:

czy jego początek > koniec poprzedniego filmu?

Jeśli tak – film się nie nakłada i można go obejrzeć.

To klasyczny algorytm selekcji aktywności – udowodniono, że wybiera maksymalną możliwą liczbę niekolidujących przedziałów.

5. Główna część programu

A) wypisanie oryginalnej listy filmów

print("Harmonogram festiwalu:")
for i in range(0, N):
    Wypisz(K, P, IDEN, i)
print()

B) sortowanie filmów

Sortuj(K, P, IDEN)
print("Filmy po sortowaniu:")
for i in range(0, N):
    Wypisz(K, P, IDEN, i)
print()

C) wybór niekolidujących filmów

print("Wybrane filmy:")
Wybierz(K, P, IDEN)

Cały analizowany kod programu

'''
    Ćwiczenie 8
    Zapisz pełen kod źródłowy programu Problem kinomana i uruchom program.
'''

P = [9, 16, 15, 18, 14, 10, 10, 13, 15, 18]
K = [10, 17, 17, 21, 15, 14, 11, 14, 17, 20]
IDEN = ["F0", "F1", "F2", "F3", "F4", "F5", "F6", "F7", "F8", "F9"]
N = len(P)

def Sortuj(koniec, poczatek, iden):
    for i in range(1, N):
        pom_koniec = koniec[i]
        pom_poczatek = poczatek[i]
        pom_iden = iden[i]
        j = i - 1
        while j >= 0 and koniec[j] > pom_koniec:
            koniec[j+1] = koniec[j]
            poczatek[j+1] = poczatek[j]
            iden[j+1] = iden[j]
            j -= 1

        koniec[j+1] = pom_koniec
        poczatek[j+1] = pom_poczatek
        iden[j+1] = pom_iden

def Wypisz(koniec, poczatek, iden, k):
    print(iden[k], ":", poczatek[k], "-", koniec[k])

def Wybierz(koniec, poczatek, iden):
    Wypisz(koniec, poczatek, iden, 0)
    koniec_poprzedniego = koniec[0]
    for i in range(1, N):
        if poczatek[i] > koniec_poprzedniego:
            Wypisz(koniec, poczatek, iden, i)
            koniec_poprzedniego = koniec[i]

print("Harmonogram festiwalu:")
for i in range(0, N):
    Wypisz(K, P, IDEN, i)
print()

Sortuj(K, P, IDEN)
print("Filmy po sortowaniu:")
for i in range(0, N):
    Wypisz(K, P, IDEN, i)
print()

print("Wybrane filmy:")
Wybierz(K, P, IDEN)