МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра физической электроники и технологии
ОТЧЕТ по лабораторной работе №5
по дисциплине «Информационные технологии» Тема: Алгоритмы и программы решения задач комбинаторики
Студентка гр. 0207 |
|
Лиоско Е.П. |
|
Преподаватель |
|
|
Рябцев И.А. |
Санкт-Петербург
2021
Алгоритм «Бинарного поиска» (Binary Search)
Цель работы.
Изучение и программирование стандартного алгоритма «бинарного поиска».
Блок-схема программы для сортировки выбором.
2
Текст программы 1.
%binary search clear all
clc global CM CM=0; N=10;
nd=2; %шаг значений элементов в векторе low=1;
high=N;
key=N;
S=ones(1,N); for i=1:N S(i)=i*nd-1; end
tic; Nq=binary_search(S,key,low,high); toc;
disp(Nq);
disp(CM);
function[M]=binary_search(S, key, low, high) global CM
CM=CM+1; %счетчик вызова binary_search M=fix((low+high)/2);
if (low>high) M=-1; return;
end
if (S(M)==key) return;
end
if (S(M)>key)
M=binary_search (S,key,low,M-1); else
M=binary_search (S,key,M+1,high); end
end
3
Листинг 1
Elapsed time is 0.004775 seconds.
S=
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
17 |
19
Nq=
-1
CM=
4
Таблица 1
i |
N |
lg N |
t*10^4 |
CM |
1 |
10 |
1 |
61,3 |
4 |
2 |
100 |
2 |
62,93 |
7 |
3 |
1000 |
3 |
66,18 |
10 |
4 |
10^4 |
4 |
67,75 |
14 |
5 |
10^5 |
5 |
86,6 |
17 |
6 |
10^6 |
6 |
89,93 |
20 |
7 |
10^7 |
7 |
94,6 |
24 |
CM |
|
|
|
|
|
|
|
|
25 |
|
|
|
|
|
|
|
|
20 |
|
|
y = 3,3214x + 0,4286 |
|
|
|
||
|
|
|
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
|
|
|
|
|
lg N |
CM=3,32 * lg N |
|
|
|
|
|
|
|
|
4
Вывод
Количество вызовов функции увеличивается с увеличением логарифма размерности вектора.
5