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 
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 
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 
 Þrepasönnun
 Deilið og drottnið (stjórnmálafræðileg hugmyndafræði)
 Akra-Bazzi aðferðin
 Meistarasetningin

 Heimildir 

Flokkur:Reiknirit