2sem / LR6_MatlabZapiska

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

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

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

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

Кафедра МВЭ

Отчет

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

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

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

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

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

2024

1. Цель

Изучение и программирование стандартного алгоритма «поиска моды».

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

Задан вектор исходных данных S(N) отсортированный по возрастанию значений его элементов, и алгоритм поиска моды, наиболее часто встречающегося (повторяющегося) значения S(im) элементов в векторе.

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

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

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

3. Проверить программу Matlab на трех версиях (A-C) вектора исходных данных S(8).

4. Составить Таблицу 1 из трех столбиков для отдельных листингов трех версий вектора S(8), включающих: значение моды S(im), индекс начала последовательности значений моды im и количество значений mc в последовательности моды.

5. Составить в Matlab Программу 2, добавив в Программу 1 формирование исходного вектора S(N). Для этого использовать функции rand и fix: s=fix(50*rand ([1 N])) так же, как в программе к лабораторной работе 4.1 «Быстрая сортировка».

6. Вставить в Программу 2 ранее разработанный модуль Quick Sort из лабораторной работе 4.1 «Быстрая сортировка» для сортировки исходного вектора S(N)

7. Вставить Программу 2 стандартные функции tic, toc для оценки времени поиска моды.

8. Определить зависимость времени поиска моды (наибольшее из 20 прогонов программы) для векторов S(10⁴), S(10⁵), S(10⁶), S(10⁷).

9. Составить Таблицу 2 из четырех строк (i=1-4), включив три столбика: с номером вектора, его размерностью и временем поиска моды t.

10. Составить Таблицу 3 из трех строк и трех столбиков. В первом столбике разместить комбинации (i-j: 1-2, 1-3, 1-4). Рассчитать коэффициенты: K_N=N_j/N_i, K_t=t_j/t_i и разместить полученные значения во втором и третьем столбиках.

11. Оформить отчет, включив в него тексты Программ 1, 2 и Таблицы 1, 2. В выводы включить закономерность изменения времени поиска моды от изменения размерности вектора (K_t ~ K_N).

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

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

1. Поиск моды для вектора из 8 компонентов

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

clc

clear

N=8;

mt=1;

mc=1;

im=1;

i=1; % 4-7 счетчики

S=[4 4 4 4 4 7 7 7]; %отсортированный массив

while i<(N-1)

j=i;

while j<N && (S(j)==S(j+1));

mt=mt+1; %сколько раз число равно последующему при шаге 1

j=j+1; %делаем шаг

end

i=i+mt; %новая точка отсчета

if mt > mc %наличие повторений числа

mc=mt; %запоминаем количество наибольших повторений, с которым далее будем сравнивать в строке 16

im=(i-mt); %перемещение в начало повторений

end

mt=1; %"обнуление" счетчика повторений числа

end

if mc>1 %если есть число повторяющееся больше 1 раза

disp("Число в моде")

disp(S(im))

disp("Позиция начала")

disp(im)

disp("Длительность моды")

disp(mc)

else

disp('No mode')

end

2. Листинг результатов

Таблица 1 – Листинг поиска моды вариаций векторов

Вектор А	Вектор В	Вектор С
Число в моде 7 Позиция начала 4 Длительность моды 5	Число в моде 4 Позиция начала 1 Длительность моды 5	No mode

2. Поиск моды больших векторов

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

clc

clear

N=10^7;

mt=1;

mc=1;

im=1;

i=1; % 4-7 счетчики

S=fix(N*rand ([1 N])); %отсортированный массив

function[S] = quicksort(S);

if ~(numel(S)<=1);

global cm;

cm=cm+1;

pivot=S(1);

A1=quicksort(S(S<pivot));

A2=S(S==pivot);

A3=quicksort(S(S>pivot));

S=[A1 A2 A3];

end

end

y=quicksort(S);

tic

while i<(N-1)

j=i;

while j<N && (y(j)==y(j+1));

mt=mt+1; %сколько раз число равно последующему при шаге 1

j=j+1; %делаем шаг

end

i=i+mt; %новая точка отсчета

if mt > mc %наличие повторений числа

mc=mt; %запоминаем количество наибольших повторений, с которым далее будем сравнивать в строке 16

im=(i-mt); %перемещение в начало повторений

end

mt=1; %"обнуление" счетчика повторений числа

end

toc

if mc>1 %если есть число повторяющееся больше 1 раза

disp("Число первой наибольшей моды")

disp(y(im))

disp("Позиция начала")

disp(im)

disp("Длительность моды")

disp(mc)

else

disp('No mode')

end

2. Листинг результатов

Таблица 2 – Листинг времени поиска моды больших массивов

i	N	t, сек
1	10^4	0.0744531
2	10^5	0.733402
3	10^6	7.47025
4	10^7	76.6665

Таблица 3 – Определение зависимости времени сортировки от размера массива

i-j	Kn	Kt
1-2	10	9.85
1-3	100	100.33
1-4	1000	1029.73

4. Вывод

В ходе выполненной работы был изучен алгоритм поиска моды. Проведен алгоритм поиска моды для случайных отсортированных векторов. Проведен алгоритм больших массивов чисел и рассмотрена зависимость времени сортировки от количества элементов массива.

Определена зависимость Kt~Kn: при изменении размерности массива на порядок, время поиска моды так же увеличивается на порядок. Прямая линейная зависимость.