Skaldyk ir valdyk algoritmas yra problemų sprendimo strategija, kuri apima sudėtingos problemos suskaidymą į mažesnes, lengviau valdomas dalis, kiekvienos dalies sprendimą atskirai ir sprendimų derinimą, kad būtų išspręsta pradinė problema. Tai plačiai naudojama algoritminė technika kompiuterių moksle ir matematikoje.

Pavyzdys: Viduje Sujungti Rūšiuoti algoritmas, Skaldyk ir valdyk strategija naudojama elementų sąrašui rūšiuoti. Žemiau esančiame paveikslėlyje iliustruojamos padalijimo ir sujungimo būsenos, pagal kurias galima rūšiuoti masyvą Sujungti Rūšiuoti .

Turinys

• Kas yra Skaldyk ir valdyk?
• Skaldyk ir valdyk etapai
• „Skaldyk ir valdyk“ programos
• Skaldyk ir valdyk pagrindai
• Standartiniai skaldyk ir valdyk algoritmai
• Dvejetainės paieškos problemos
• Praktikuokite „Skaldyk ir valdyk“ problemas

Kas yra „Skaldyk ir užkariauk“ algoritmas?

„Skaldyk ir valdyk“ yra problemų sprendimo technika, kuri apima didesnės problemos suskaidymą į subproblemus, savarankišką subproblemų sprendimą ir tų subproblemų sprendimų derinimą, kad būtų išspręsta didesnė problema.

Skaldyk ir užkariauk algoritmo etapai:

„Skaldyk ir užkariauk“ algoritmą galima suskirstyti į tris etapus: Padalinti , Užkariauti ir Sujungti .

1. Padalinkite:

• Suskaidykite pradinę problemą į mažesnes problemas.
• Kiekviena subproblema turėtų būti bendros problemos dalis.
• Tikslas yra padalinti problemą tol, kol nebebus įmanoma skaidyti.

2. Užkariauti:

• Išspręskite kiekvieną smulkesnę užduotį atskirai.
• Jei subproblema yra pakankamai maža (dažnai vadinama baziniu atveju), mes ją išsprendžiame tiesiogiai, be tolesnių pasikartojimų.
• Tikslas yra savarankiškai rasti šių subproblemų sprendimus.

3. Sujungti:

• Sujunkite antrines problemas, kad gautumėte galutinį visos problemos sprendimą.
• Išsprendę mažesnes subproblemas, mes rekursyviai sujungiame jų sprendimus, kad gautume didesnės problemos sprendimą.
• Tikslas yra suformuluoti pradinės problemos sprendimą, sujungiant subproblemų rezultatus.

„Skaldyk ir valdyk“ algoritmo taikymas:

• Sujungti rūšiavimą: Sujungti rūšiavimą yra klasikinis „skaldyk ir valdyk“ rūšiavimo algoritmo pavyzdys. Jis suskaido masyvą į mažesnius pogrupius, surūšiuoja juos atskirai ir sujungia, kad gautų surūšiuotą masyvą.
• Vidutinis radinys: Skaičių rinkinio medianą galima rasti naudojant „skaldyk ir valdyk“ metodą. Rekursyviai padalijus aibę į mažesnius poaibius, medianą galima nustatyti efektyviai.
• Min ir Max radiniai: „Skaldyk ir užkariauk“ algoritmas gali būti naudojamas norint vienu metu rasti ir mažiausią, ir didžiausią masyvo elementus. Padalijus masyvą į dalis ir palyginus kiekvienos pusės min-max poras, bendrą min ir max galima nustatyti logaritminiu laiko sudėtingumu.
• Matricos daugyba: Strasseno matricos daugybos algoritmas yra „skaldyk ir valdyk“ technika, kuri sumažina daugybų skaičių, reikalingą didelėms matricoms, skaidant matricas į mažesnes submatricas ir sujungiant jų sandaugas.
• Artimiausios poros problema: Artimiausios poros problema apima dviejų artimiausių taškų radimą taškų rinkinyje daugiamatėje erdvėje. „Skaldyk ir valdyk“ algoritmas, pvz., „Skaldyk ir užkariauk“ algoritmas, gali efektyviai išspręsti šią problemą, rekursyviai padalydamas taškus ir sujungdamas subproblemų sprendimus.

Skaldyk ir valdyk algoritmo pagrindai:

• Įvadas į „Skaldyk ir valdyk“.
• Dinaminis programavimas prieš „skaldyk ir valdyk“.
• Sumažinti ir užkariauti
• Išplėstinė pagrindinė teorema, skirta „skaldyk ir valdyk“ pasikartojimui

Įjungti standartiniai algoritmai Skaldyk ir užkariauk algoritmas :

• Dvejetainė paieška
• Sujungti Rūšiuoti
• Greitas rūšiavimas
• Apskaičiuoti pow(x, n)
• Karatsuba algoritmas greitam dauginimui
• Strasseno matricos daugyba
• Išgaubtas korpusas (paprastas dalyk ir užkariauk algoritmas)
• Quickhull algoritmas išgaubtam korpusui

Dvejetainės paieškos problemos:

• Raskite smailės elementą duotame masyve
• Patikrinkite, ar surūšiuotame masyve nėra daugumos elemento
• K-asis dviejų surūšiuotų masyvų elementas
• Raskite nulių skaičių
• Raskite sukimosi skaičių masyve Rotated Sorted
• Raskite tašką, kuriame monotoniškai didėjanti funkcija pirmą kartą tampa teigiama
• Dviejų surūšiuotų masyvų mediana
• Dviejų skirtingų dydžių surūšiuotų masyvų mediana
• Dailininko skaidinio problema naudojant dvejetainę paiešką

Praktikuokite problemas Skaldyk ir užkariauk algoritmas :

• Kvadratinė šaknis iš sveikojo skaičiaus
• Maksimalus ir minimumas masyve naudojant mažiausią palyginimų skaičių
• Raskite kiekvieno elemento dažnį riboto diapazono masyve per trumpesnį nei O(n) laiką
• Plytelių klijavimo problema
• Apskaičiuokite inversijas
• Skyline problema
• Ieškokite 2D masyve pagal eilutes ir stulpelius
• Paskirstykite minimalų puslapių skaičių
• Modulinis eksponentiškumas (galia modulinėje aritmetikoje)

Greitos nuorodos :

• Sužinokite duomenų struktūrą ir algoritmus | DSA mokymo programa
• „Skaldyk ir valdyk“ „Praktikos problemos“.
• „Viktorinos“ apie „Skaldyk ir valdyk“.