2sem / LR5MatlabZapiska

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра МВЭ

Отчет

По лабораторной работе №4

по дисциплине «Алгоритмы и вычислительные средства»

Тема:Алгоритмы и программы решения задач комбинаторики. Быстрая сортировка.

Студент гр. 3206		Корепанов Д. М.
Руководитель		Шевченко С. А.

Санкт-Петербург

2024

1. Цель

Изучение и программирование стандартного алгоритма бинарного поиска

2. Постановка задачи

Задан алгоритм бинарного поиска и отсортированный вектор исходных данных S(n)

3. Алгоритм выполнения работы

1. Реализовать алгоритм бинарного поиска для вектора исходных данных S(10) в программе Matlab

2. Вставить комментарии к операторам программы

3. Вставить в программу стандартные функции tic, toc для оценки времени решения задачи.

4. Проверить программу Matlab на векторе исходных данных S(10)

5. Определить количество вызовов функции binary_search, используя глобальный счетчик (CM)

6. Получить листинг, включающий: вектор S(10), значение глобального счетчика CM и время решения задачи

7. Модифицировать программу Matlab, задав исходный вектор S(100). Для этого установить размерность массива N=100

8. Определить зависимость количество вызовов функции binary_search и время выполнения программы (наибольшее из 20 прогонов программы) для векторов S(10), S(100), S(1000), S(104), S(105), S(106), S(107)

9. Составить таблицу из семи строк (i=1-7), включив столбики с размерностью вектора, логарифмом размерности вектора, временем выполнения сортировки и количеством вызовов функции binary_search.выполнения программы (наибольшее из 20 прогонов программы) и соответствующее ему количество вызовов функции quicksort.

10. Рассчитать коэффициент пропорциональности А между логарифмом размерности вектора и количеством вызовов функции binary_search (CM=А lg N), используя инструмент тренда Excel или другим удобным способом.

11. Оформить отчет, включив в него тексты программ Matlab, листинг отсортированного вектора S(10), таблицу зависимости количества вызовов функции binary_search и времени решения задачи от размерности вектора. В выводы включить закономерность изменения количества вызовов функции binary_search от логарифма размерности вектора.

4. Основная часть

Рисунок 1 -- Блок-схема алгоритма

1. Бинарный поиск для вектора из 10 компонентов

   1. Код программы

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. Листинг результатов

Рисунок 2 -- Листинг результатов поиска

Количество итераций = 3.

2. Б

   Таблица 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

5. Вывод

В ходе выполненной работы был изучен алгоритм бинарного поиска. Проведен алгоритм поиска для больших векторов, начинающихся с числа 3 с шагом 1. Рассмотрена зависимость количества вызовов функции количества элементов массива: cm=A*lg(N). A≈3

Рисунок 3 -- График моды количества итераций от lg(N)