Rešitev: Trikotnik števil (Algoritem)

Iz MaFiRaWiki

Naloga: Trikotnik števil

Algoritem bomo načrtovali z metodo dinamičnega programiranja. Velik trikotnik bomo razdelili na več manjših trikotnikov, na katerih je enostavno poiskati največjo vsoto.

Problema se bomo lotili spodaj in nato šli proti vrhu. Na prvem koraku si zapomnimo vsa števila v zadnji (n-ti) vrstici. Nato na drugem koraku j-temu številu v (n-1). vrstici prištejemo večje izmed j. in (j+1). števila v n. vrstici. Vsote si zapomnimo. Nato na vsakem naslednjem koraku j. številu v vrstici prištejemo večjo od vsot, ki se začenjata v j. in (j+1). številu prejšnje vrstice. Ko pridemo do zgornje vrstice, moramo primerjati le še dve vsoti. Izberemo večjo.

Primer

Poiščimo pot z največjo vsoto v naslednjem trikotniku.

Zapomnimo si števila v zadnji vrstici: 1,12,17,8.

3. vrstica: 6-ki prištejemo večjega izmed 1 in 12, t.j. 12, 9-ki in 10-ki pa prištejemo 17. Zapomnimo si vsote: 18, 26, 27.

S tem smo dobili največjo vsoto v trikotnikih:

2. vrstica: 7-ki prištejemo 26, 5-ki pa 27. Zapominmo si: 33, 32.

S tem smo dobili največjo vsoto v trikotnikih:

33>32, zato je končna vsota 4+33=37, iskana veriga pa 4-7-9-17.

Osebna orodja