2sem / LR5MatlabZapiska
.doc
МИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В.И. Ульянова (Ленина)
Кафедра МВЭ
Отчет
По лабораторной работе №4
по дисциплине «Алгоритмы и вычислительные средства»
Тема:Алгоритмы и программы решения задач комбинаторики. Быстрая сортировка.
Студент гр. 3206 |
|
Корепанов Д. М. |
Руководитель |
|
Шевченко С. А. |
Санкт-Петербург
2024
Цель
Изучение и программирование стандартного алгоритма бинарного поиска
Постановка задачи
Задан алгоритм бинарного поиска и отсортированный вектор исходных данных S(n)
Алгоритм выполнения работы
Реализовать алгоритм бинарного поиска для вектора исходных данных S(10) в программе Matlab
Вставить комментарии к операторам программы
Вставить в программу стандартные функции tic, toc для оценки времени решения задачи.
Проверить программу Matlab на векторе исходных данных S(10)
Определить количество вызовов функции binary_search, используя глобальный счетчик (CM)
Получить листинг, включающий: вектор S(10), значение глобального счетчика CM и время решения задачи
Модифицировать программу Matlab, задав исходный вектор S(100). Для этого установить размерность массива N=100
Определить зависимость количество вызовов функции binary_search и время выполнения программы (наибольшее из 20 прогонов программы) для векторов S(10), S(100), S(1000), S(104), S(105), S(106), S(107)
Составить таблицу из семи строк (i=1-7), включив столбики с размерностью вектора, логарифмом размерности вектора, временем выполнения сортировки и количеством вызовов функции binary_search.выполнения программы (наибольшее из 20 прогонов программы) и соответствующее ему количество вызовов функции quicksort.
Рассчитать коэффициент пропорциональности А между логарифмом размерности вектора и количеством вызовов функции binary_search (CM=А lg N), используя инструмент тренда Excel или другим удобным способом.
Оформить отчет, включив в него тексты программ Matlab, листинг отсортированного вектора S(10), таблицу зависимости количества вызовов функции binary_search и времени решения задачи от размерности вектора. В выводы включить закономерность изменения количества вызовов функции binary_search от логарифма размерности вектора.
Основная часть
Рисунок 1 -- Блок-схема алгоритма
Бинарный поиск для вектора из 10 компонентов
Код программы
clc
clear
global cm
N=10;
cm=0;
nd=2;
L=1; %Позиция наименьшего значения
H=N; %Позиция наибольшего значения
KEY=N/2; %искомое значение в векторе
S=[1 1 1 1 1 1 1 1 1 1]; %Вводим единичный вектор
for I=1:N
S(I)=I+nd; %Заполняем единичный вектор
end
function[M] = binary_search(S, KEY, L, H); %Задание функции
global cm
cm=cm+1;
M=fix((L+H)/2); %номер центрального элемента между L и H элементамм
if L>H %массив не отсортирован
M=-1;
return
end
if (S(M)==KEY) %значение найдено
return
end
if (S(M)>KEY)
M=binary_search(S, KEY, L, M-1); %ограничение поиска
elseif (S(M)<KEY)
M=binary_search(S, KEY, M+1, H); %ограничение поиска
end
End
tic
M=binary_search(S, KEY, L,H); %Вызов функции
toc
S(M)
cm
Листинг результатов
Рисунок 2 -- Листинг результатов поиска
Количество итераций = 3.
Б
Таблица 1 -- Листинг результатов бинарного поиска
инарный поиск для больших векторов
i |
N |
lg(N) |
t*10^4, сек |
cm |
1 |
10 |
1 |
1.358 |
3 |
2 |
100 |
2 |
3.281 |
6 |
3 |
10^3 |
3 |
3.529 |
9 |
4 |
10^4 |
4 |
4.442 |
13 |
5 |
10^5 |
5 |
6.731 |
16 |
6 |
10^6 |
6 |
43.14 |
19 |
7 |
10^7 |
7 |
406.809 |
23 |
Вывод
В ходе выполненной работы был изучен алгоритм бинарного поиска. Проведен алгоритм поиска для больших векторов, начинающихся с числа 3 с шагом 1. Рассмотрена зависимость количества вызовов функции количества элементов массива: cm=A*lg(N). A≈3
Рисунок 3 -- График моды количества итераций от lg(N)