Разделяй и владей - I част
Вълшебникът – пастир
Преди около 2000 години живял вълшебник-пастир, който имал голямо стадо овце. Всеки ден той изяждал по една овца от стадото си. Овцете му създавали голямо безпокойство – бягали от кошарата, доста трудно можел да ги хване и отново да ги събере заедно. Овцата, която имал намерение да заколи, го усещала и силно се съпротивлявала, а нейните вопли ужасявали другите овце в стадото. Тогава на вълшебникът-пастир му хрумнала идея – той привикал всяка овца поотделно и на всяка внушил по нещо различно.
На една казал:
„Ти не си овца, ти си също такъв човек, както и аз. Няма от какво да се страхуваш, тъй като аз коля и ям само овце, но ти си единственият човек в това стадо и аз ще те спася“.
На друга казал:
„Защо бягаш от мен като овцете? Ти си лъв и няма от какво да се страхуваш. Аз коля само овце, а теб ще спася“.
На трета внушил:
„Ти не си овца, ти си вълк. Вълк, който уважавам. Аз, както и преди, ще продължавам всеки ден да коля по една овца, но ти вълчо, най-добрият ми приятел, няма от какво да се страхуваш! Ти ще бъдеш спасен!”.
Така този вълшебник – пастир поговорил с всяка от овцете и на всяка внушил, че не е овца и не прилича по нищо на останалите овце от стадото. След тези разговори поведението на овцете се променило коренно – те си пасели съвсем спокойно и вече не бягали от кошарата. Когато вълшебникътът – пастир колел поредната овца, останалите си мислели: „Ето, заклаха още една овца, а аз (лъва, вълка, човека, най-добрия приятел на вълшебникът – пастир) няма от какво да се страхувам. Ще бъда спасен“
Дори овцете, които колел, спрели да се съпротивляват. Вълшебникът – пастир доближавал до някоя от тях и ѝ прошепвал: „О, добри мой приятелю, отдавна не сме си говори. Ела с мен в двора. Да си поговорим с теб за стадото“. Овцата радостно тръгвала с вълшебникът – пастир към двора, където той действително я питал каква е ситуацията в стадото. Жертвата с радост му разказвала за всичко, а след това вълшебникът – пастир я убивал. Тъй като смъртта настъпвала на мига, овцата не успявала да разбере какво се случва.
Вълшебникът – пастир бил много доволен – той повишил самочувствието на всяка от овцете и така те вече не се притеснявали за неизбежната смърт, станали спокойни, наслаждавали се на живота и спокойно си пасели, в резултат на което и месото им станало много по-вкусно. Години наред вълшебникът – пастир лесно се справял с огромното стадо и най-интересното е, че всички овце му помагали – ако случайно някоя по-съобразителна овца започвала да се досеща за истинското положение, то останалите овце, вълци, хора, лъвове – най-добрите приятели на вълшебникът – пастир – му казвали за странното поведение на тази овца и той още на следващия ден без притеснение я изяждал.
В тази прича се описват два сортиращи алгоритъма на матрицата: сортиране чрез пряка селекция и сортиране чрез вмъкване имащи дълго време за изпълнение. Други два алгоритъма за сортиране: сортиране чрез сливане и бързо сортиране имат по-кратко време за изпълнение.
- Раздробява задачата на подзадачи, които са подобни на същата задача.
- Овладява подзадачите, като ги решава рекурсивно. Ако са достатъчно малки, решава подзадачите като базови случаи.
- Комбинира решенията на подзадачите в решение на първоначалната задача.
Тъй като алгоритъмът “разделяй и владей” създава минимум две подзадачи, този алгоритъм прави няколко рекурсивни извиквания.
„Аз съм пратен само при загубените овце от Израилевия дом” (Матей 15:24).
Преди около 2000 години живял вълшебник-пастир, който имал голямо стадо овце. Всеки ден той изяждал по една овца от стадото си. Овцете му създавали голямо безпокойство – бягали от кошарата, доста трудно можел да ги хване и отново да ги събере заедно. Овцата, която имал намерение да заколи, го усещала и силно се съпротивлявала, а нейните вопли ужасявали другите овце в стадото. Тогава на вълшебникът-пастир му хрумнала идея – той привикал всяка овца поотделно и на всяка внушил по нещо различно.
На една казал:
„Ти не си овца, ти си също такъв човек, както и аз. Няма от какво да се страхуваш, тъй като аз коля и ям само овце, но ти си единственият човек в това стадо и аз ще те спася“.
На друга казал:
„Защо бягаш от мен като овцете? Ти си лъв и няма от какво да се страхуваш. Аз коля само овце, а теб ще спася“.
На трета внушил:
„Ти не си овца, ти си вълк. Вълк, който уважавам. Аз, както и преди, ще продължавам всеки ден да коля по една овца, но ти вълчо, най-добрият ми приятел, няма от какво да се страхуваш! Ти ще бъдеш спасен!”.
Така този вълшебник – пастир поговорил с всяка от овцете и на всяка внушил, че не е овца и не прилича по нищо на останалите овце от стадото. След тези разговори поведението на овцете се променило коренно – те си пасели съвсем спокойно и вече не бягали от кошарата. Когато вълшебникътът – пастир колел поредната овца, останалите си мислели: „Ето, заклаха още една овца, а аз (лъва, вълка, човека, най-добрия приятел на вълшебникът – пастир) няма от какво да се страхувам. Ще бъда спасен“
Дори овцете, които колел, спрели да се съпротивляват. Вълшебникът – пастир доближавал до някоя от тях и ѝ прошепвал: „О, добри мой приятелю, отдавна не сме си говори. Ела с мен в двора. Да си поговорим с теб за стадото“. Овцата радостно тръгвала с вълшебникът – пастир към двора, където той действително я питал каква е ситуацията в стадото. Жертвата с радост му разказвала за всичко, а след това вълшебникът – пастир я убивал. Тъй като смъртта настъпвала на мига, овцата не успявала да разбере какво се случва.
Вълшебникът – пастир бил много доволен – той повишил самочувствието на всяка от овцете и така те вече не се притеснявали за неизбежната смърт, станали спокойни, наслаждавали се на живота и спокойно си пасели, в резултат на което и месото им станало много по-вкусно. Години наред вълшебникът – пастир лесно се справял с огромното стадо и най-интересното е, че всички овце му помагали – ако случайно някоя по-съобразителна овца започвала да се досеща за истинското положение, то останалите овце, вълци, хора, лъвове – най-добрите приятели на вълшебникът – пастир – му казвали за странното поведение на тази овца и той още на следващия ден без притеснение я изяждал.
В тази прича се описват два сортиращи алгоритъма на матрицата: сортиране чрез пряка селекция и сортиране чрез вмъкване имащи дълго време за изпълнение. Други два алгоритъма за сортиране: сортиране чрез сливане и бързо сортиране имат по-кратко време за изпълнение.
- Раздробява задачата на подзадачи, които са подобни на същата задача.
- Овладява подзадачите, като ги решава рекурсивно. Ако са достатъчно малки, решава подзадачите като базови случаи.
- Комбинира решенията на подзадачите в решение на първоначалната задача.
Тъй като алгоритъмът “разделяй и владей” създава минимум две подзадачи, този алгоритъм прави няколко рекурсивни извиквания.
„Аз съм пратен само при загубените овце от Израилевия дом” (Матей 15:24).
