Подходът: Разделяй и владей.Свойства, известни алгоритми, реализация и оценъчна формула.
Идеята на този подход е обектът(входните данни)да се раздели на части и рекурсивно се намира реш.на всяка част и оттук за це-лия обект. Пр.намиране на макс.от N елем, съхранени в масив:а[0],a[1],…,a[N-1]
Нерекурс.реш:
for ( t = a[0]; i = 1; i < N; i++)
if ( a[i] > t ) t = a[i]
Рекурс.реш. се изр.в следното:поредицата от елем. a[l],…,a[r] се разделя на 2 пореди-ци: a[l],…,a[m] и a[m+1],…,a[r],намират се max елем.в двете части(рекурсивно) и се връща по-гол.от тях като max от редицата
Item max (Item a[ ], int l, int r)
{ Item u,v; int m = (l+r) / 2; if (l == r) return a[l];
u = max (a, l, m);
Използ.на метода се дължи на факта,че той дава по-бързи реш.отколкото тези,получе-ни с прости итеративни алг.
Св-во. Рекурс.ф-я,разделяща зад.с размер N на 2 незав,непразни части,които тя решава рекурс.,се обръща към себе сиобщото време е линейно.
Друг клас.пример е зад.за Ханойските кули
Дадени са 3 пръчки и N диска с дупки в ср. които мд се надяват на пръчките,дисковете са разл.по размер и първоначално са подре-дени на най-лявата от пръчките в ред най-големия диск(N)долу,най-малкия(1) горе. Зад.е да се преместят дисковете на следв. отдясно пръчка по => правила:
само 1 диск се премества в даден момент
в/у по-малък диск не мд се пост.по-голям
//Ние премест.кулата от дискове надясно чрез рекурсивно премест.наляво на всички с изкл.на най-долния,после премест.най-долния надясно,след което рекурсивно ме-стим кулата обратно в/у най-долния диск.
void hanoi ( int N, int d)
Сподели с приятели: |
