Сортування масиву. Розділення його на частини, по окремим впорядкуванням їх та наступним злиттям частин.

Виявляється дешевше сортувати два під масиви і об’єднати їх у впорядкований, а ніж сортувати весь масив вцілому.

Злиття .

Фрагмент підпрограми має вигляд:

i:=1;

j:=1;

k:=1;

while (i<=N)and(j<=M)do

if a[i]<b[j] then

Begin

i:=i+1;

k:=k+1

End

Else

Begin

c[k]:=b[j];

j:=j+1;

k:=k+1;

end;

while i<=N do

Begin

c[k]:=a[i];

i:=i+1;

j:=k+1

end;

while j<=M do

Begin

c[k]:=b[j];

j:=j+1;

k:=k+1;

end;

Тема: Метод послідовних наближень.

В ряді випадків розв’язок задачі не може бути знайдений абсолютно точно. Це може мати місце лише, якщо вхідні дані задачі визначені не точно. В процесі обчислення виконується округлення або взагалі задача немає точного розв'язку. В таких випадках користуються методом послідовних наближень, при цьому вибирається або довільним чином, або за певною умовою початкове наближення розв'язку, потім будується деякий алгоритм, який дозволяє за кожним попереднім наближенням розв'язку отримати наступне наближення. Такий процес уточнень продовжується до тих пір, поки буде досягнута необхідна точність результату.

Оскільки точний розв'язок в принципі є невідомим, то користуються наступною умовою припущення уточнень .

Наприклад. Формула Ньютона-Рафоса для обчислення кореня квадратного для невід’ємного числа.

;

<== попередня сторінка	\|	наступна сторінка ==>
Якщо ж поділ дає різноманітні задачі, метод виділення під цілей.	\|	алгоритм Ньютона-Рафоса закладений в реалізацію функцій sqr, sqrt.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.