Harjutus nr 10 ja praktikum 11 Algoritmimise strateegiad Ülesanne 1 Loe läbi järgmine ülesanne ja paku välja idee, kuidas Sa seda lahendama asuksid: 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 Vaata teste eelmises lahtris. Ülesanne 2 Teine sarnane ülesanne: millised oleksid eelmisest ülesandest lähtudes sammud, et seda lahendada? VALIMISED Ühe liitriigi presidendi valivad valijamehed, keda on igas osariigis kindel arv. Valimiste lõppvoorus on kaks kandidaait ja valituks osutub kandidaat, kes saab rohkem hääli. Kehtib kirjutamata seadus, et ühe osariigi valijamehed hääletavad alati sama kandidaadi poolt. Kirjutada programm, mis kontrollib, kas president võib jääda ka valimata -- kui mõlemad kandidaadid saavad täpselt võrdselt hääli. Sisend. Tekstifaili VALIM.SIS esimesel real on osariikide arv N ja teisel real valijameeste arvud osariikide kaupa (N tühikutega eraldatud täisarvu). Valijameeste koguarv ei ületa 1000. Väljund. Tekstifaili VALIM.VAL esimesele reale väljastada JAH, kui on kindel, et president saab valitud (st, kui ei ole võimalik, et hääled jagunevad täpselt pooleks); faili teisele reale väljastada sel juhul vähim võimalik vahe võitja ja kaotaja häälte arvude vahel. Kui president võib jääda valimata (st, kui on võimalik, et hääled jagunevad täpselt pooleks), väljastada faili esimesele reale EI ja teisele reale ühe võimaliku viigiseisu korral esimese kandidaadi poolt hääletavate valijameeste arvud. Näide. VALIM.SIS VALIM.VAL 4 JAH 3 1 2 5 1 Näide. VALIM.SIS VALIM.VAL 4 EI 4 1 2 5 4 2 Vaata teste eelmises lahtris. Ülesanne 3. Kaheksa lippu (tagurdus, ingl backtracking) Uuri kaheksa lipu (ehk eigth queen problem) lahendust siit: https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/ https://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf Graafiülesanne - laiuti otsimine: Ülesanne 4. Kasutajagrupid (informaatika olümpiaad, 2005/06 õppeaasta) Paljudes arvutisüsteemides on kasutajate õiguste määramise lihtsustamiseks võimalik ühendada kasutajaid gruppideks ja määrata õigusi tervetele gruppidele korraga. Sellistes süsteemides on kasutaja õiguste tuvastamiseks vaja leida kõik grupid, millesse see kasutaja kuulub. Uuemates süsteemides võib iga grupp sisaldada liikmetena lisaks kasutajatele ka teisi gruppe. Sel juhul loetakse grupi liikmeteks ka kõik tema liikmesgruppide liikmed. Kirjutada programm, mis leiab sellise hierarhilise gruppide süsteemi põhjal kõik grupid, millesse antud kasutaja kuulub. Sisend. Tekstifaili grp.sis esimesel real on kasutajagruppide arv N (1 <= N <= 1000) ja järgmisel 2 * N real gruppide kirjeldused 2-realiste plokkidena. Iga ploki esimesel real on kaks täisarvu: grupi identifikaator Gi ja grupi kirjelduses esinevate liikmete (kasutajate ja teiste gruppide) arv Ni (1 <= Ni <= 100). Ploki teisel real on Ni täisarvu: grupi liikmete identifikaatorid, kus positiivsed arvud tähistavad gruppe ja negatiivsed kasutajaid (identifikaatorite absoluutväärtused ei ületa 1000). Faili viimasel real on negatiivne täisarv K: ühe kasutaja identifikaator. Väljund. Tekstifaili grp.val esimesele reale väljastada üks täisarv M: kasutajat K sisaldavate gruppide arv. Faili teisele reale väljastada M täisarvu: nende gruppide identifikaatorid kasvavas järjekorras. Näide. grp.sis 3 1 3 2 3 -1 2 3 -2 -3 -4 3 4 -2 -3 -5 -6 -5 grp.val 2 1 3