logo

TechCodeview

Dali un iekaro algoritms

Dali un iekaro algoritms ir problēmu risināšanas stratēģija, kas ietver sarežģītas problēmas sadalīšanu mazākās, vieglāk pārvaldāmās daļās, katras daļas atrisināšanu atsevišķi un risinājumu apvienošanu, lai atrisinātu sākotnējo problēmu. Tā ir plaši izmantota algoritmiskā tehnika datorzinātnēs un matemātikā.

Piemērs: Iekš Sapludināt Kārtot algoritms, Skaldi un iekaro stratēģija tiek izmantota, lai sakārtotu elementu sarakstu. Zemāk redzamajā attēlā ir parādīti sadalīšanas un sapludināšanas stāvokļi, lai kārtotu masīvu, izmantojot Sapludināt Kārtot .



oops koncepcija java

Satura rādītājs

Kas ir sadali un iekaro algoritms?

Sadaliet un iekarojiet ir problēmu risināšanas paņēmiens, kas ietver lielākas problēmas sadalīšanu apakšproblēmās, apakšproblēmu atrisināšanu neatkarīgi un šo apakšproblēmu risinājumu apvienošanu, lai iegūtu lielākas problēmas risinājumu.



Skaldi un valdi algoritma posmi:

Dali un iekaro algoritmu var iedalīt trīs posmos: Sadaliet , Iekarot un Apvienot .

struktūras masīvs c valodā

1. Sadaliet:

  • Sadaliet sākotnējo problēmu mazākās apakšproblēmās.
  • Katrai apakšproblēmai ir jāatspoguļo daļa no kopējās problēmas.
  • Mērķis ir sadalīt problēmu, līdz tālāka sadalīšana nav iespējama.

2. Iekarot:

  • Atrisiniet katru no mazākajām apakšproblēmām atsevišķi.
  • Ja apakšproblēma ir pietiekami maza (bieži saukta par pamatgadījumu), mēs to atrisinām tieši bez turpmākas atkārtošanās.
  • Mērķis ir patstāvīgi rast risinājumus šīm apakšproblēmām.

3. Apvienot:

  • Apvienojiet apakšproblēmas, lai iegūtu visas problēmas galīgo risinājumu.
  • Kad mazākās apakšproblēmas ir atrisinātas, mēs rekursīvi apvienojam to risinājumus, lai iegūtu lielākas problēmas risinājumu.
  • Mērķis ir formulēt sākotnējās problēmas risinājumu, apvienojot apakšproblēmu rezultātus.

Skaldi un valdi algoritma pielietojumi:

  • Sapludināt kārtot: Sapludināšanas kārtošana ir klasisks šķirošanas algoritma “sadali un iekaro” piemērs. Tas sadala masīvu mazākos apakšblokos, sašķiro tos atsevišķi un pēc tam apvieno, lai iegūtu sakārtoto masīvu.
  • Vidējais atradums: Skaitļu kopas mediānu var atrast, izmantojot sadali un valdi pieeju. Rekursīvi sadalot kopu mazākās apakškopās, mediānu var noteikt efektīvi.
  • Minimālais un maksimālais atrašana: Dalīšanas un iekarošanas algoritmu var izmantot, lai masīvā vienlaikus atrastu gan minimālos, gan maksimālos elementus. Sadalot masīvu uz pusēm un salīdzinot min-max pārus no katras puses, kopējo min un max var noteikt logaritmiskā laika sarežģītībā.
  • Matricas reizināšana: Strassen algoritms matricas reizināšanai ir dalīšanas un iekarošanas paņēmiens, kas samazina reizināšanas reižu skaitu, kas nepieciešams lielām matricām, sadalot matricas mazākās apakšmatricās un apvienojot to reizinājumus.
  • Tuvākā pāra problēma: Tuvākā pāra problēma ietver divu tuvāko punktu atrašanu punktu kopā daudzdimensiju telpā. Dalīšanas un iekarošanas algoritms, piemēram, tuvākā pāra algoritms, var efektīvi atrisināt šo problēmu, rekursīvi sadalot punktus un apvienojot apakšproblēmu risinājumus.

Skaldi un valdi algoritma pamati:

Standarta algoritmi ieslēgti Dali un iekaro algoritms :

Binārās meklēšanas problēmas:

  • Atrodiet pīķa elementu dotajā masīvā
  • Pārbaudiet, vai sakārtotā masīvā nav vairākuma elementa
  • Divu sakārtotu masīvu K-tais elements
  • Atrodiet nulles skaitu
  • Atrodiet rotāciju skaitu masīvā Rotated Sorted
  • Atrodiet punktu, kurā monotoniski pieaugoša funkcija pirmo reizi kļūst pozitīva
  • Divu sakārtotu masīvu mediāna
  • Divu sakārtotu dažāda lieluma masīvu mediāna
  • Gleznotāja nodalījuma problēma, izmantojot bināro meklēšanu

Praktizējiet problēmas Dali un iekaro algoritms :

  • Vesela skaitļa kvadrātsakne
  • Masīva maksimālais un minimums, izmantojot minimālo salīdzinājumu skaitu
  • Atrodiet katra elementa frekvenci ierobežotā diapazona masīvā mazāk nekā O(n) laikā
  • Flīžu ieklāšanas problēma
  • Skaitīt inversijas
  • Skyline problēma
  • Meklējiet 2D masīvā pēc rindas un kolonnas
  • Piešķiriet minimālo lapu skaitu
  • Modulārā kāpināšana (jauda moduļu aritmētikā)

Ātrās saites :

  • Uzziniet datu struktūru un algoritmus | DSA apmācība
  • “Prakses problēmas” sadaļā “Skaldi un valdi”.
  • “Viktorīnas” par tēmu “Skaldi un valdi”.