H14 ülesanded esimene ül dynamic programmong, düna
Kool: Tallinna Tehnikaülikool (TalTech, TTÜ)
Aine: Algoritmid ja andmestruktuurid - ICD0001
Kategooria: Informaatika
Postitatud: 21 detsember 2024
Postitaja: rig14
Kirjeldus
H14 ülesanded 1. Meil on MxN suurusega väljak kus iga läbitav väli on tähistatud 0-ga ja mitteläbitav väli -1-ga. Väljaku ülemise vasaku nurga koordinaadid on (11) ja parema alumise nurga koordinaadid on (MN). Liikuma hakatakse ülemisest vasakust nurgast ja liikuda saab ainult paremale või alla ja siis kui sihtkohaks on läbitav väli. Tuleb leida mitu erinevat teed on ülemisest vasakust nurgast alumisse paremasse nurka. a. Leidke graafi läbimisel põhinev lahendusalgoritm ja määrake selle keerukus b. Leidke otsingul põhinev algoritm koos memoization tehnikaga ja määrake selle keerukus c. Leidke dünaamilise planeerimise algoritm ja määrake selle keerukus. Näiteks järgneval ülesandel on vastus 9 O((NM)) 0 0 0 0 0 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 fun int findWay(int map int M int N) queue new Queue((11)) result 0 while queue.isEmpty() current queue.poll() if current (MN) result continue if mapcurrent0current1 -1 continue else queue.…