"rekkursiivne" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

Valiksorteerimise algoritm (igal sammul otsitakse vähimat arvu, mida sorteerimata massiiviosa algusesse tõsta). Seljakoti probleem. Varga eesmärk on seljakotti sisse panna võimalikult suure summa eest kraami. (kaks variatsiooni: diskreetne – asju ei ole võimalik tükeldada ja pidev – osade kaupa) Algoritmid ja andmestruktuurid 2015 6 2.3 Divide and Conquer ehk jaga ja valitse Kogu meetod on oma olemuselt rekkursiivne (st jaga ülesanne tükkideks ja tükid omakorda tükkideks kuni saadakse sobiva suursega tükid, mida on paras lahendada) • Probleem jagatakse mitmeks alamprobleemiks, mis lahendatakse üksteisest sõltumatult. • Seejärel ühendateakse alamprobleemide lahendused nö alt üles ja saadakse lahendus kogu probleemile. 2.3.1 Omadused: • Minimaalne sisendi mõõt n0 – kui probleemi suurs on alla selle ei hakata probleemi jagama.