по дисциплине «Теория алгоритмов»
Выполнил: ст-ты гр. 20КП01
Климочкин Д. Ю, Танин М. В.
Проверил: доцент каф. ИВС
Дрождин В.В.
1 Формулировка задачи
Сгенерируйте последовательность A размера n (3 ≤ n ≤ 10000) случайных вещественных чисел, содержащих 3 знака после десятичной точки. Выведите эту последовательность в обратном порядке, поменяв местами в каждом числе целую и дробную части.
2 Техническое задание
2.1 Требования к программе
Программа должна случайным образом сгенерировать элементы последовательности A в виде вещественных чисел и вывести эту последовательность в обратном порядке, поменяв местами в каждом числе целую и дробную части.
2.2 Порядок контроля и приёмки
Для контроля правильности работы программы необходимо ввести размер последовательности n, после чего программа выдает результат виде сгенерированной и упорядоченной последовательностей. Если результат совпадет с результатами визуальной проверки, то это означает, что программа работает корректно.
3 Описание программы
3.1 Общие сведения
Программа разработана в среде Pascal. Текст приведен в приложении А.
3.2 Функциональное назначение
Программа предназначена для генерации последовательности и ее упорядочивания убыванию.
3.3 Описание логической структуры
Решение задачи выполняется в несколько этапов:
1. Ввод исходных данных: размер последовательности n.
2. Генерация последовательности A из n элементов.
3. Сортировка (упорядочивание) последовательности по убыванию.
4. Замена местами в каждом числе целую и дробную части.
5. Вывод сгенерированной и отсортированной последовательностей.
Для генерации элементов последовательности будем использовать формулу random(n) – (random()*n*1000)/1000-n.
Для упорядочивания последовательности целесообразно использовать наиболее простой метод – сортировку методом пузырька, и для определенности будем реализовывать сортировку по убыванию. Сортировка пузырьком заключается в следующем: сначала сравниваются 1 и 2 элементы и, если 1 элемент больше, то они меняются местами, затем сравниваются 2 и 3 элементы и т.д., пока не сравнятся n-1 и n элементы. После первого прохода самый большой элемент будет перемещен на последнее место. Далее выполняется второй проход и второй максимальный элемент будет помещен на n-1 место. И так далее, пока все элементы не будут помещены в соответствующее место.
Вывод осуществляется следующим образом: в процессе генерации последовательно выдаются сгенерированные элементы исходной последовательности, а после сортировки выдается упорядоченная последовательность, причем при выводе последовательности по возрастанию результирующая последовательность выводится с 1 по n элементы, а убывающая – с n по 1 элементы. Такой подход позволяет использовать только один способ сортировки (по возрастанию), что уменьшает алгоритмическую и емкостную сложности программы и немного снижает временную сложность.
Алгоритм решения задачи на псевдокоде представлен на рисунке 1.
Начало
Данные:
n, i, j, p – целые
k – вещественные
m – массив [1...10000] вещественных
a, a1 – строка
Выполнить:
ввод n
вывод 'Исходная последовательность:'
для i от 1 доn
m[i] = (random()*n*1000)/1000-n
вывод m[i]:6:3,' '
преобразование числа в строку m[i]:3:3,a
преобразование строки в число copy(a,pos('.',a)+1,1000),j,p
если m[i] меньше 0 тогда
a1 = '-'
вывод '-',j,'.',copy(a,2,pos('.',a)-2),' '
иначе
a1 = ' '
вывод j,'.',copy(a,1,pos('.',a)-1),' '
a1 = a1+copy(a,pos('.',a)+1,1000)+'.'+copy(a,2,pos('.',a)-2)
преобразование строки в число a1,m[i]
конец_для
вывод 'Упорядоченная последовательность:'
для i от n до 1
вывод m[i]:4:1,' '
Конец.
Рисунок 1 – Алгоритм на псевдокоде
Решение задачи начинается с ввода размера последовательности n. Далее выполняется цикл для_i, в котором генерируется m[i] элемент последовательности вещественных чисел и выводится на экран. После генерации всей последовательности циклы для_i и для_j меняют местами, в каждом числе, целую и дробную части и выполняют сортировку последовательности m по убыванию. Далее оператор если определяет, если m[i] элемент последовательности меньше нуля, то перед числами ставиться знак '-', если m[i] больше нуля, то перед числами ставиться ' '.
Текст программы в форме консольного приложения приведен в приложении А.
В разделе описания переменных программы объявлены:
n: integer – размер последовательности m;
i, j, k: integer – внутренние переменные;
m: array [1..10000] of real – последовательность максимального размера;
a, a1: string – строковые переменные.
Исполняемая часть программы начинается с ввода n, задающих размер реальной последовательности. Цикл с параметром for i:= 1 to n do генерирует элементы последовательности m и выдает их на экран. После этого цикл с параметром for i:=n downto 1 do выполняет сортировку элементов последовательности путем сравнения и обмена соседних элементов. Вывод последовательности m осуществляется по убыванию выводом элементов m[i]. После вывода последовательности m программа завершает свою работу.
4 Программа и методика испытаний
Так как случайную последовательность повторить невозможно, то проверку правильности работы программы будем выполнять визуально. Для этого необходимо запустить программу на выполнение, ввести значение размера последовательности и получить результат работы программы.
При проверке работы программы получены результаты, приведенные в приложении Б, в которых количество и значения элементов в исходной и упорядоченной последовательностях совпадают. Таким образом, можно сделать вывод, что программа работает корректно.
5 Описание применения
После запуска программы на выполнение на экране появляются запросы на ввод размера последовательности (см. Приложение Б). После ввода исходных данных выдаются сгенерированная и результирующая последовательность.
Заключение
В ходе выполнения лабораторной работы разработано техническое задание на решение задачи, разработан алгоритм решения задачи, генерирующий исходную случайную последовательность, меняющую местами в числе целую и дробную части и упорядочивающий ее убыванию, составлена и отлажена программа, и оформлена программная документация. Проведенные испытания показали, что программа работает корректно.
ТЕКСТ ПРОГРАММЫ
Приложение А
(обязательное)
program sort;
// Сортировка последовательности методом пузырька
var
n,i,j,p:integer;
k:real;
m:array [1..10000] of real;
a,a1:string;
begin
repeat
write('Размер последовательности(3<=n<=10000)n=');
readln(n);
until (3<=n) and (n<=10000);
writeln ('Исходная последовательность');
randomize;
for i:=1 to n do
begin
m[i]:=(random()*n*1000)/1000-n;
write(m[i]:6:3,' ');
str(m[i]:3:3,a);
val (copy(a,pos('.',a)+1,1000),j,p);
if m[i]<0 then
a1:='-'
// write('-',j,'.',copy(a,2,pos('.',a)-2),' ')
else
a1:='';
// write(j,'.',copy(a,1,pos('.',a)-1),' ');
a1:=a1+copy(a,pos('.',a)+1,1000)+'.'+copy(a,2,pos('.',a)-2);
val(a1,m[i]);
end;
writeln;
writeln('Упорядоченная последовательность');
for i:=n downto 1 do
write(m[i]:4:1,' ');
writeln;
end.
РЕЗУЛЬТАТЫИСПЫТАНИЙ
Приложение Б
(обязательное)
Размер последовательности (3 <= n <= 10000) n = 6
Исходная последовательность:
Упорядоченная последовательность:
Рисунок Б.1
Размер последовательности (3 <= n <= 10000) n = 17
Исходная последовательность:
Упорядоченная последовательность:
Рисунок Б.2
Размер последовательности (3 <= n <= 10000) n = 30
Исходная последовательность:
Упорядоченная последовательность:
Рисунок Б.3
Размер последовательности (3 <= n <= 10000) n = 40
Исходная последовательность:
Упорядоченная последовательность:
Рисунок Б.4