Ҷудо кун ва ҳукмронӣ кун

Ҷудо кун ва ҳукмронӣ кун

Муқаддима

Тақсим кун ва ҳукмронӣ намо — ин техникаи алгоритмӣ аст, ки дар он масъала бо истифода аз стратегия «Тақсим кун, ҳукмронӣ намо ва муттаҳид кун» ҳал карда мешавад.

Алгоритми маъмулии «Тақсим кун ва ҳукмронӣ намо» масъалаҳоро бо истифода аз се қадами зерин ҳал мекунад:

• Тақсим кардан: тақсим кардани масъала ба зермасъалаҳои хурдтар.
• Ҳукмронӣ кардан: ҳал кардани зермасъалаҳо тавассути даъвати рекурсивӣ то он даме, ки онҳо ҳал шаванд.
• Муттаҳид кардан: муттаҳид кардани зермасъалаҳо барои ба даст овардани ҳалли ниҳоии масъалаи аслӣ.

Татбиқ

Шарти масъала

Массиви $a_1, a_2, \ldots, a_n$ аз адад дода шудааст. Талаб карда мешавад, ки массив бо бо истифода аз техникаи «Тақсим кун ва ҳукмронӣ намо» тартиб дода шавад.