ів масиву.
1.2 Вибір матеріалу для проведення теоретичного дослідження
Провівши літературний огляд можна зробити наступний висновок, що досить повна інформація про алгоритм пряме включення міститься в літературному джерелі [2, 66-69, 493-498,].
Будемо використовувати наступні формули залежності максимального і мінімального числа порівнянь від числа елементів в масиві, які були там [2, 66-69, 493-498,] наведені:
формула залежності максимального числа порівнянь від числа елементів в масиві з N елементів sravnmax=(n ^ 2 + n) * / 2 - 1 (1.1);
(n - 1)-формула залежності мінімального числа порівнянь від числа елементів в масиві з N елементів.
2. ДОСЛІДЖЕННЯ АЛГОРИТМА ПРЯМЕ ВКЛЮЧЕННЯ
Дослідити алгоритм можна по-різному. Перший спосіб дослідження - це теоретичний. Розглядається сам принцип, закладений в алгоритм. При такому дослідженні перевіряється характер поведінки даного алгоритму при різних умовах. Це необхідно, щоб виявити ті умови, при яких даний алгоритм є найбільш ефективним, а також такі умови, при яких його використання не доцільно.
Другий спосіб дослідження - це практичний, коли складається програма за заданим алгоритмом, який необхідно досліджувати. У самій програмі, виходячи з її принципу, ставляться лічильники числа порівнянь. Багаторазово проводиться пошук для однакового числа елементів у масиві, і визначаються свої значення числа порівнянь. Потім шукається середнє значення числа порівнянь для пошуку певного числа елементів в масиві. За отриманими значеннями будуються графіки залежності середнього числа порівнянь від числа елементів масиву.
Так як в завданні на курсовий проект вказуються масиви для дослідження від 10 до 100 елементів, покладемо, що N - максимальне число елементів у масивах одно 10 <= N <= 100.
2.1 Теоретичне дослідження алгоритму пряме включення
В літературі [2, 66-69, 493-498,] були запропоновані наступні залежності числа порівнянь від числа елементів в масиві:
формула залежності максимального числа порівнянь від числа елементів в масиві;
(n ^ 2 + n) * / 2 - 1 (1.1)
формула залежності мінімального числа порівнянь від числа елементів в масиві;
n - 1 (1.2)
формула залежності максимального числа переміщень від числа елементів в масиві;
(n ^ 2 + 3 * n - 4) / 2 (1.3)
формула залежності мінімального числа переміщень від числа елементів в масиві.
2 * (n - 1) (1.4)
Побудуємо за формулами (2.1) - (2.2) графіки залежностей максимального і мінімального числа порівнянь для бінарного пошуку.
Щоб побудувати графіки залежностей максимального і мінімального числа порівнянь для методу прямого включення, ми візьмемо десять довільних масивів з числом елементів від 10 до 100 і підставимо їх значення у формули (1.2) і (1.3), результати запишемо в таблицю (1).
Таблиця 1
Результати, отримані п...
