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

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

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

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

Кафедра РТЭ

отчёт

по лабораторной работе №5

по дисциплине «Информационные технологии»

Тема: «Алгоритм поиска медианы и генерирования

перестановок»

Студентка гр.9283		Зикратова А. А.
Преподаватель		Кочунов К. В.

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

2020

Цель работы:

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

перестановок.

Ⅰ часть: ввести с клавиатуры элементы массива размерности N

(размерность так же задается пользователем вручную). Основываясь на

алгоритме, представленном в блок-схеме на рисунке 1, составить код

программы, реализующий алгоритм поиска медианы в заданном массиве.

Обратите внимание, что блок-схема составлена для языка С++ (в Matlab

нумерация идет с 1). В результате работы алгоритма должен происходить

вывод значения найденной медианы (медиана – значение центрального

элемента массива для массивов нечетной размерности, для четной

размерности – сумма двух центральных элементов деленная на 2).

Алгоритм поиска медианы (Ⅰ вариант с сортировкой выбором):

n=input('Введите n ');

A=input('Введите массив ');

if mod(n,2)~=0

for i=1:n

na=0;

ma=0;

for j=1:n

if A(j)~=A(i)

if A(j)>A(i)

na=na+1;

else

ma=ma+1;

end

end

end

if na==ma

disp(A(i))

end

end

end

if mod(n,2)==0

for i=1:(n-1)

for j=(i+1):n

q=i;

while A(j)<A(q)

q=j;

P=A(i);

A(i)=A(q);

A(q)=P;

end

end

end

disp((A(n/2)+A(n/2+1))/2)

end

Результаты работы программы:

Введите n 10 (кол-во элементов чётно)

Введите массив [3 1 9 8 45 61 2 0 7 61]

7.5000

Введите n 5 (кол-во элементов нечётно)

Введите массив [98 6 4 12 0]

6

Алгоритм поиска медианы (Ⅱ вариант)

n=input('Введите n ');

A=input('Введите массив ');

if mod(n,2)~=0

for i=1:n

na=0;

ma=0;

for j=1:n

if A(j)~=A(i)

if A(j)>A(i)

na=na+1;

else

ma=ma+1;

end

end

end

if na==ma

disp(A(i))

end

end

end

if mod(n,2)==0

for i=1:(n-1) % в циклах рассматриваются элементы массива за исключение последнего, т. е. ищется медиана массива без последнего элемента.

na=0;

ma=0;

for j=1:(n-1)

if A(j)~=A(i)

if A(j)>A(i)

na=na+1;

else

ma=ma+1;

end

end

end

if na==ma

disp(A(i)) % 1-я медиана.

end

end

for t=1:n % а в этих циклах найденная в предыдущей части медиана исключается из рассмотрения, а последний элемент присутствует. Снова ищется медиана, но уже другого массива.

if t==i

continue % элемент, который является медианой (1 часть) исключается. Цикл при t==i и d==i переходит на следующую итерацию.

end

w=0;

p=0;

for d=1:n

if d==i % переход на следующую итерацию, минуя значение d==i

continue % элемент-медиана (1 медиана) исключается из рассмотрения.

end

if A(d)~=A(t)

if A(d)>A(t)

w=w+1;

else

p=p+1;

end

end

end

if w==p

disp(A(t)) % 2-я медиана

disp((A(t)+A(i))/2) % медиана для массива с чётным кол-вом элементов.

end

end

end

Результаты работы программы:

Введите n 12 (кол-во элементов чётно)

Введите массив [1 4 3 26 5 8 0 9 31 11 7 6]

7 (1-я медиана)

6 (2-я медиана)

6.5000 (среднее значение 2-х медиан)

Введите n 7 (кол-во элементов нечётно)

Введите массив [54 108 63 87 53 13 45]

54

Алгоритм поиска медианы (Ⅲ вариант подходит только для небольших массивов с нечётным кол-вом элементов):

t = 1;

n = input (' Кол-во элементов массива : ');

I = zeros(1,n);

while t <= n

I(t) = input ('Введите элемент массива : ');

t = t + 1;

end

disp (I);

for i= 1:n

na=0;

ma=0;

for j=1:n

if I(j) ~= I(i)

if I(j) > I(i)

na = na + 1;

else

ma = ma + 1;

end

end

end

if na == ma

disp (I(i));

end

end

Результат работы программы:

Кол-во элементов массива : 5

Введите элемент массива : 98

Введите элемент массива : 6

Введите элемент массива : 4

Введите элемент массива : 12

Введите элемент массива : 0

98 6 4 12 0

6

У меня к Вам вопрос по поводу работы программ (Ⅰ и Ⅱ): почему медианы некоторых массивов не считаются?

Например, (Ⅱ программа)

Введите n 8

Введите массив [1 45 23 12 43 9 62 1]

23

12

37 (медиана исходного массива неправильно посчитана)

или

Введите n 8

Введите массив [7 1 3 9 8 0 4 7]

4 (выведена только 1-я медиана).

А у таких массивов:

Введите n 5

Введите массив [4 61 2 7 4]

и

Введите n 5

Введите массив [67 3 84 2 67], -

не выводится медиана ни у 1-ой программы, ни у 2-ой.

Ⅱ часть: ввести с клавиатуры размерность массива N. Автоматически

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

алгоритм генерации перестановок получить и вывести на экран все

возможные комбинации значений массива.

Рекурсивный алгоритм генерации перестановок:

global n;

global X;

n = input('Кол-во элементов в массиве: ');

X = [];

k=1;

while k<=n

X=[X k];

k=k+1;

end

disp('Все комбинации элементов введённого массива: ');

k=1;

generate(X, k, n);

function X = swap(X,a,b)

t = X(a);

X(a) = X(b);

X(b) = t;

end

function generate(X, k, n)

if k==n

disp(X);

else

for j=k:n

X = swap(X,k,j);

generate(X, k+1, n);

X = swap(X, k, j);

end

end

end

Результат работы программы:

Кол-во элементов в массиве: 3

Все комбинации элементов введённого массива:

1 2 3

1 3 2

2 1 3

2 3 1

3 2 1

3 1 2

Вывод: в ходе проделанной лабораторной работы были изучены алгоритм поиска медианы и рекурсивный алгоритм генерации перестановок.