Deili- og drottnunarreiknirit
Í tölvunarfræði eru deili- og drottnunarreiknirit mikilvæg tegund reiknirita. Þau brjóta viðfangsefnið aftur og aftur niður í tvö eða fleiri einfaldari vandamál af sömu eða svipaðri gerð uns þau verða nægilega einföld til að leysast með beinum hætti. Lausnir hinna minni vandamála eru síðan sameinuð til þess að fá lausn á hinu upprunalega vandamáli.
Útfærsla
[breyta | breyta frumkóða]Deili- og drottnunarreiknirit eru auðveldlega útfærð sem ítrunarföll. Þannig eru hlutalausnirnar geymdar á kallhlaðanum.
Einnig er hægt að útfæra slík reiknirit án þess að nota ítrun, en þá eru hlutalausnirnar geymdar í gagnagrind á borð við hlaða, biðröð eða FIFO. Með þessari aðferð er hægt að velja með mun auðveldari hætti hvaða minni vandamál reikniritið skuli fást við næst, sem er mjög mikilvægur eiginleiki í sumum lausnum, svo sem breidd fyrst ítrun og greina og afmarka aðferðinni við bestun falla.
Afbrigði
[breyta | breyta frumkóða]Eitt afbrigði af deili- og drottnunarreikniritum eru minnkunar- og drottnunarreiknirit, þar sem að lokaniðurstaðan er aðeins háð einni milliniðurstöðu. Það getur verið gott að höndla slík verkefni sérstaklega, þar sem þau eru yfirleitt leysanleg með lausnum af hluta hinna minni verkefna. Auk þess er oft auðveldara að greina þau en önnur deili- og drottnunarvandamál.
Reiknirit til þess að finna stærsta gildið í lista af tölum:
Reiknirit StærstaTala Ílag: Listi af tölum L, sem er ekki tómur. Úttak: Stærsta talan í listanum L. Athugasemd: Deili- og drottnunaraðferð. ef L.stærð == 1 þá skila L.haus stærst1 ← StærstaTala(L.haus...L.miðja) stærst2 ← StærstaTala(L.miðja....L.hali) ef stærst1 > stærst22, þá stærst ← stærst1 else stærst ← stærst2 skila stærst
Reiknirit StærstaTala Ílag: Listi af tölum L, sem er ekki tómur. Úttak: Stærsta talan í listanum L. Athugasemd: Minnka og drottna. ef L.stærð == 1 þá skila L.haus síðasta = L.stærð - 1; stærst ← StærstaTala(L.haus...L.síðasta) ef stærst < L.hali þá stærst ← L.hali skila stærst
Tengt efni
[breyta | breyta frumkóða]- Þrepasönnun
- Deilið og drottnið (stjórnmálafræðileg hugmyndafræði)
- Akra-Bazzi aðferðin
- Meistarasetningin
Heimildir
[breyta | breyta frumkóða]Fyrirmynd greinarinnar var „Divide and conquer algorithm“ á ensku útgáfu Wikipedia. Sótt 9. maí 2006.