по дисциплине «Теория алгоритмов»
Выполнил: ст-ты гр. 20КП01
Климочкин Д. Ю, Танин М. В.
Проверил: доцент каф. ИВС
Дрождин В.В.
1 Формулировка задачи
Квадратную матрицу M размера n × n (3 ≤ n ≤ 1000) заполнить случайными целыми числами. Найти минимальный элемент главной диагонали и максимальный элемент побочной диагонали и поменять местами строки, в которых они находятся.
2 Техническое задание
2.1 Требования к программе
Программа должна заполнить случайными целыми числами квадратную матрицу М размера n × n. Найти минимальный элемент главной диагонали и максимальный элемент побочной диагонали и поменять местами строки, в которых они находятся.
2.2 Порядок контроля и приёмки
Для контроля правильности работы программы необходимо запустить программу, после чего программа выдает результат виде сгенерированной матрицы со случайными целыми числами и найденными минимальными элементами главной диагонали и максимальными элементами побочной диагонали. Далее программа предложит поменять местами строки. Если результат совпадет с результатами визуальной проверки, то это означает, что программа работает корректно.
3 Описание программы
3.1 Общие сведения
Программа разработана в среде Pascal. Текст приведен в приложении А.
3.2 Функциональное назначение
Программа предназначена для генерации квадратной матрицы M размера n × n, нахождение минимальных элементов главной диагонали и максимальных элементов побочной диагонали и замена местами строки, в которых они находятся.
3.3 Описание логической структуры
Решение задачи выполняется в несколько этапов:
1. Генерация матрицы М из n элементов.
2. Нахождение минимального элемента главной диагонали и максимального элемента побочной диагонали.
3. Замена местами строк в матрице.
4. Вывод сгенерированной и отсортированной матрицы.
Для генерации матрицы будем использовать формулу random(n) – random(100) - 50.
Для заполнения матрицы улиткой по часовой стрелке, начиная с ячейки [1, 1], разработаем способ решения задачи, заключается в том, что двумерная матрица будет заполняться с помощью одиночного цикла и выбираемого направления движения по матрице: слева направо (®), сверху вниз (¯), справа налево () и снизу вверх (). Это позволит уменьшить алгоритмическую сложность примерно в 2 раза и незначительно уменьшит временную сложность, вследствие отсутствия вложенного цикла.
Алгоритм решения задачи на псевдокоде представлен на рисунке 1.
Начало
Данные:
i, j, max, a, b, buff – целые
arr – массив [1..n,1..n] целых
Выполнить:
для i от 1 доn
для j от 1 до n
arr[i,i] = random(100) - 50
вывод arr[i,j]:4
для i от 1 доn
если arr[i,i] меньше 0 тогда
вывод arr[i,i]:4
max = arr[1,n]
для i от 1 доn
еслиarr[i,n-i+1] больше max тогда
max = arr[i,n-i+1]
вывод 'Макс. эл-т побочной диагонали = '
ввод 'Какие строки поменять местами: '
для j от 1 до n
Выполнить:
buff = arr[a,j];
arr[a,j] = arr[b,j];
arr[b,j] = buff;
конец_для
для i от 1 доn
Выполнить:
для j от 1 до n
ввод arr[i,j]:3
вывод
конец_для
Конец.
Рисунок 1 – Алгоритм на псевдокоде
Решение задачи начинается с ввода размера матрицы n. Далее выполняется цикл для_i, в котором генерируется arr[i,j] элемент матрицы целых чисел и выводится на экран. После генерации матрицы оператор если для_i и для_j ищет минимальные элементы главной последовательности. Далее оператор если для i и для j ищет максимальные элементы побочной последовательности. После нахождения минимальных и максимальных элементов выполняется цикл для_i и для_j, в котором меняет местами строки.
Текст программы в форме консольного приложения приведен в приложении А.
В разделе описания переменных программы объявлены:
i, j, max, a, b, buff: integer – внутренние переменные;
arr: array [1..N,1..N] of integer – матрица n × n;
Исполняемая часть программы начинается с запуска самой программы. Цикл с параметром for i:= 1 to n do генерирует матрицу размером n × n и заполняет случайными целыми числами. После этого цикл с параметром for i:=1 to n do выполняет поиск минимальных элементов главной последовательности и выводит их на экран. Далее цикл i:=1 to n do выполняет поиск максимальных элементов побочной последовательности и выводит их на экран. После вывода минимальных элементов главной диагонали и максимальных элементов побочной диагонали программа меняет строки местами и выводит на экран. После вывода изменённой матрицы программа завершает работу.
4 Программа и методика испытаний
Так как случайную последовательность повторить невозможно, то проверку правильности работы программы будем выполнять визуально. Для этого необходимо запустить программу на выполнение, ввести номера строк, которые мы хотим поменять и получить результат работы программы.
При проверке работы программы получены результаты, приведенные в приложении Б, в которых выведенные минимальные элементы главной диагонали и максимальные элементы побочной диагонали совпадают с элементами в матрице. Таким образом, можно сделать вывод, что программа работает корректно.
5 Описание применения
После запуска программы на выполнение на экране появляется запрос на ввод номеров строк для их перестановки местами (см. Приложение Б). После ввода исходных данных выдаются сгенерированная и результирующая матрица.
Заключение
В ходе выполнения лабораторной работы разработано техническое задание на решение задачи, разработан алгоритм решения задачи, генерирующая квадратную матрицу M размера n × n и заполняющая её случайными целыми числами. Нахождение минимального элемента главной диагонали и максимального элемента побочной диагонали и перестановка местами строк, в которых они находятся, составлена и отлажена программа, и оформлена программная документация. Проведенные испытания показали, что программа работает корректно.
ТЕКСТ ПРОГРАММЫ
Приложение А
(обязательное)
program sort;
// Сортировка последовательности методом пузырька
Const
N = 5;
Var
arr: array [1..N,1..N] of integer;
i,j,max,a,b,buff: integer;
Begin
randomize;
for i:=1 to N do begin // просто заполнение матрицы
for j:=1 to N do begin
arr[i,j]:= random(100) - 50;
write(arr[i,j]:4);
end;
writeln;
end;
writeln;
for i:=1 to N do // решение задачи
if arr[i,i] < 0 then
write(arr[i,i]:4);
writeln;
max:=arr[1,n];
For i:=1 to n do
If arr[i,n-i+1]>max Then max:=arr[i,n-i+1];
Writeln('Макс. эл-т побочной диагонали = ',max);
write('Какие строки поменять местами: ');
readln(a,b);
for j:=1 to N do begin
buff:= arr[a,j];
arr[a,j]:= arr[b,j];
arr[b,j]:= buff;
end;
for i:=1 to N do begin
for j:=1 to N do
write(arr[i,j]:3);
writeln;
end;
end.
РЕЗУЛЬТАТЫИСПЫТАНИЙ
Приложение Б
(обязательное)
Размер матрицы М (3 <= n <= 10000) n = 5
Рисунок Б.1
Размер матрицы М (3 <= n <= 10000) n = 7
Рисунок Б.2
Размер матрицы М (3 <= n <= 10000) n = 9
Рисунок Б.3
Размер матрицы М (3 <= n <= 10000) n = 3
Рисунок Б.4