Otsimine Räägime kõigepealt natuke puna-mustast puust koos animeeritud näitega (eelmised harjutused). Seejärel vaatame korraks otsa B-puule, mida näiteks andmebaasides indekite tegemisel ühe variandina kasutatakse. See materjal on ka vafrem toimunud otsimise loengus (vaatame seal olevaid slaide). ------------------------------------------------ Edasi valikus lahendamiseks kaks ülesannet: esimene kahendotsingupuust ja teine dünaamilisest programmeerimisest. Ülesanne 1 Kahendotsingupuu Kirjuta programm kahendotsingupuu moodustamiseks ning sealt otsimiseks. Puu võib olla realiseeritud dünaamiliselt või staatiliselt. Dünaamilise puu tehniline ülesehitus ja toimimine (liikumine juurest leheni) on väga sarnane loomade arvamise puu omale. Staatilise puu (massiivina realiseeritud) tegemiseks vaata üle sorteerimiste materjalis kirjeldatud kahendkuhja (binery heap) esitus või loengus Puudest üldiselt vaadatud slaidid. Oluline: kuidas on kahendpuu andmed esitatavad massiivis ja kuidas arvutada välja vasaku ja parema lapse asukohad-indeksid. Loomulikult reeglid selle kohta, mis on vasakus alampuus ja mis paremas on kahendkuhjal ja kahendotsingupuul erinevad. Proovi info mõistlikult kokku viia! Ülesanne 2 KASSA Kassas on hulk erinevaid rahatähti. Nende abil on vaja välja maksta teatud summa. Kirjutada programm, mis leiab vähima võimaliku rahatähtede arvuga variandi selle summa maksmiseks. Sisend. Tekstifaili KASSA.SIS esimesel real on kassas olevate nominaalide arv N (1 <= N <= 30). Faili teisel real on N täisarvu (Ai, 0 < Ai <= 1000) ? rahatähtede nominaalid kasvavas järjekorras. Kolmandal real on samuti N täisarvu (Ki, 0 <= Ki <= 100) ? iga nominaaliga rahatähtede arv kassas. Faili neljandal real on makstav summa S (0 <= S <= 10000). Väljund. Tekstifaili KASSA.VAL ainsale reale väljastada N täisarvu ? kassast väljastatavate rahatähtede arvud nominaalide kaupa. Raha tuleb välja anda nii, et nõutud summa saaks täpselt makstud ja välja antaks vähim võimalik arv rahatähti. Sisendandmed on alati sellised, et on võimalik nõutud summa täpselt välja maksta. Kui sama rahatähtede arvuga lahendusi on mitu, väljastada neist ükskõik milline. Näide. KASSA.SIS KASSA.VAL 3 1 1 1 1 2 5 5 5 5 8 Lingi failidele algoritmimise strateegiate tunni all