по дисциплине «Теория алгоритмов»
Выполнил: ст-т гр. 19КП1
Иванов И.И.
Проверил: доцент каф. ИВС
Дрождин В.В.
1 Формулировка задачи
Напишите программу, генерирующую последовательность M случайных целых чисел со значениями в интервале [- n /2.. n /2] размера n (3 ≤ n ≤ 10000) и упорядочивающую ее по возрастанию или убыванию.
2 Техническое задание
2.1 Требования к программе
Программа должна случайным образом сгенерировать элементы последовательности M в виде целых чисел из интервала [- n /2.. n /2] и упорядочить ее по возрастанию или убыванию.
2.2 Порядок контроля и приёмки
Для контроля правильности работы программы необходимо ввести размер последовательности n и признак упорядочивания (в – по возрастанию, у – по убыванию), после чего программа выдает результат виде сгенерированной и упорядоченной последовательностей. Если результат совпадет с результатами визуальной проверки, то это означает, что программа работает корректно.
3 Описание программы
3.1 Общие сведения
Программа разработана в среде Lazarus. Текст приведен в приложении А.
3.2 Функциональное назначение
Программа предназначена для генерации последовательности и ее упорядочивания по возрастанию или убыванию.
3.3 Описание логической структуры
Решение задачи выполняется в несколько этапов:
1. Ввод исходных данных: размер последовательности n и признак упорядочивания u.
2. Генерация последовательности M из n элементов.
3. Сортировка (упорядочивание) последовательности по возрастанию.
4. Вывод сгенерированной и отсортированной последовательностей.
Для генерации элементов последовательности в интервале [- n /2.. n /2] будем использовать формулу random(n) – n/5.
Для упорядочивания последовательности целесообразно использовать наиболее простой метод – сортировку методом пузырька, и для определенности будем реализовывать сортировку по возрастанию. Сортировка пузырьком заключается в следующем: сначала сравниваются 1 и 2 элементы и, если 1 элемент больше, то они меняются местами, затем сравниваются 2 и 3 элементы и т.д., пока не сравнятся n-1 и n элементы. После первого прохода самый большой элемент будет перемещен на последнее место. Далее выполняется второй проход и второй максимальный элемент будет помещен на n-1 место. И так далее, пока все элементы не будут помещены в соответствующее место.
Вывод осуществляется следующим образом: в процессе генерации последовательно выдаются сгенерированные элементы исходной последовательности, а после сортировки выдается упорядоченная последовательность, причем при выводе последовательности по возрастанию результирующая последовательность выводится с 1 по n элементы, а убывающая – с n по 1 элементы. Такой подход позволяет использовать только один способ сортировки (по возрастанию), что уменьшает алгоритмическую и емкостную сложности программы и немного снижает временную сложность.
Алгоритм решения задачи на псевдокоде представлен на рисунке 1.
Начало
Данные:
n, i, j, k – целые
m – массив [1...10000] целых
u – символ
Выполнить:
ввод n, u
вывод 'Исходная последовательность:'
для i от 1 доn
m[i] = round(random() * n - n / 2)
вывод m[i], ' '
конец_для
вывод 'Упорядоченная последовательность:'
для i от 1 доn-1
для j от 1 доn-i
если m[j] > m[j + 1]
обмен m[j] с m[j + 1]
конец_если
конец_для_j
конец_для_i
если u = 'в'
вывод m по возрастанию
иначе
вывод m по возрастанию
конец_если
Конец.
Рисунок 1 – Алгоритм на псевдокоде
Решение задачи начинается с ввода размера последовательности n и признака упорядочивания u. Далее выполняется цикл для_i, в котором генерируется m[i] элемент последовательности и выводится на экран. После генерации всей последовательности циклы для_i и для_j выполняют сортировку последовательности m по возрастанию. Далее оператор если определяет, если требуется вывод последовательности по возрастанию, то результирующая последовательность выводится по возрастанию, в противном случае – по убыванию и алгоритм завершает свою работу.
Текст программы в форме консольного приложения приведен в приложении А.
В разделе описания переменных программы объявлены:
n: integer – размер последовательности m;
i, j, k: integer – внутренние переменные;
m: array [1..10000] of integer – последовательность максимального размера;
u: char – признак упорядочивания (по возрастанию или убыванию).
Исполняемая часть программы начинается с ввода n и u, задающих размер реальной последовательности и признак упорядочивания. Цикл с параметром for i:= 1 to n do генерирует элементы последовательности m и выдает их на экран. После этого циклы с параметром for i:= 1 to n-1 do и for j:= 1 to n-i do выполняют сортировку элементов последовательности путем сравнения и обмена соседних элементов. Вывод последовательности m осуществляется в зависимости от значения признака u: при u = ‘в’ – по возрастанию, иначе – по убыванию с помощью цикла for i:= 1 to n do с выводом элементов m[i]. После вывода последовательности m программа завершает свою работу.
4 Программа и методика испытаний
Так как случайную последовательность повторить невозможно, то проверку правильности работы программы будем выполнять визуально. Для этого необходимо запустить программу на выполнение, ввести значение размера последовательности и признака упорядочивания ‘в’ или ‘у’ и получить результат работы программы.
При проверке работы программы получены результаты, приведенные в приложении Б, в которых количество и значения элементов в исходной и упорядоченной последовательностях совпадают. Таким образом, можно сделать вывод, что программа работает корректно.
5 Описание применения
После запуска программы на выполнение на экране появляются запросы на ввод размера последовательности и признака упорядочивания (см. Приложение Б). После ввода исходных данных выдаются сгенерированная и результирующая последовательности.
Заключение
В ходе выполнения лабораторной работы разработано техническое задание на решение задачи, разработан алгоритм решения задачи, генерирующий исходную случайную последовательность и упорядочивающий ее по возрастанию или убыванию, составлена и отлажена программа, и оформлена программная документация. Проведенные испытания показали, что программа работает корректно.
ТЕКСТ ПРОГРАММЫ
Приложение А
(обязательное)
program sort;
// Сортировка последовательности методом пузырька
Var
n, i, j, k: integer;
m: array [1..10000] of integer;
u: char;
Begin
Repeat
write('Размер последовательности (3 <= n <= 10000) n = ');
readln(n);
until (3 <= n) and (n <= 10000);
Repeat
write('Упорядочивание (в - по возрастанию, у - по убыванию) = ');
readln(u);
until (u = 'в') or (u = 'у');
writeln('Исходная последовательность:');
randomize;
for i:= 1 to n do
Begin
m[i]:= round(random() * n - n / 2);
write(m[i], ' ');
end;
writeln;
writeln('Упорядоченная последовательность:');
for i:= 1 to n - 1 do
for j:= 1 to n - i do
if m[j] > m[j + 1] then
Begin
k:= m[j];
m[j]:= m[j + 1];
m[j + 1]:= k;
end;
if u = 'в' then
for i:= 1 to n do
write(m[i], ' ')
Else
for i:= n downto 1 do
write(m[i], ' ');
writeln;
end.
РЕЗУЛЬТАТЫИСПЫТАНИЙ
Приложение Б
(обязательное)
Размер последовательности (3 <= n <= 10000) n = 5
Упорядочивание (в - по возрастанию, у - по убыванию) = в
Исходная последовательность:
2 2 2 2 0
Упорядоченная последовательность:
0 2 2 2 2
Рисунок Б.1
Размер последовательности (3 <= n <= 10000) n = 10
Упорядочивание (в - по возрастанию, у - по убыванию) = в
Исходная последовательность:
5 -4 1 -1 -3 -4 5 1 -4 0
Упорядоченная последовательность:
-4 -4 -4 -3 -1 0 1 1 5 5
Рисунок Б.2
Размер последовательности (3 <= n <= 10000) n = 24
Упорядочивание (в - по возрастанию, у - по убыванию) = у
Исходная последовательность:
-11 -8 10 3 11 -4 7 -12 0 0 -10 7 -11 11 8 4 1 -6 -3 -3 -6 -5 5 -6
Упорядоченная последовательность:
11 11 10 8 7 7 5 4 3 1 0 0 -3 -3 -4 -5 -6 -6 -6 -8 -10 -11 -11 -12
Рисунок Б.3
Размер последовательности (3 <= n <= 10000) n = 35
Упорядочивание (в - по возрастанию, у - по убыванию) = у
Исходная последовательность:
6 3 -3 -9 6 13 -15 -1 5 -10 10 13 2 5 11 17 14 -17 10 9 9 1 -16 10 -10 -17 10 10 12 1 8 2 -7 1 11
Упорядоченная последовательность:
17 14 13 13 12 11 11 10 10 10 10 10 9 9 8 6 6 5 5 3 2 2 1 1 1 -1 -3 -7 -9 -10 -10 -15 -16 -17 -17
Рисунок Б.4