Альметьевский государственный нефтяной институт
Кафедра информатики
КУРСОВЯ РАБОТА
ПО ДИСЦИПЛИНЕ «ИНФОРМАТИКА»
РАЗДЕЛ: Алгоритмический язык Pascal
НА ТЕМУ:
«Разработка в среде Turbo Pascal программы сортировки элементов строк матрицы»
Альметьевск 2010 год
Решения задачи графическим и программным способами по теме «двумерные массивы»
Тема курсовой работы: «Разработка в среде Turbo Pascal программы сортировки элементов строк матрицы».
Постановка задачи
Элементы четных строк матрицы размером n x m упорядочить по возрастанию, элементы нечетных строк- по убыванию. Для отладки программы элементы двумерного массива сформировать с помощью генератора случайных чисел.
Исходными данными являются элементы двумерного массива, которые должны быть созданы по условию задачи с помощью генератора случайных чисел Random. Функция Random без параметра формирует вещественные числа в диапазоне [0,1]. Так как по условию задачи элементами массива должны быть целые числа, то воспользуемся формулой Random(b-a+1)+a, которая будет выдавать случайные целые числа из диапазона [a,b].
В результате решения задачи будет найден четные строки матрицы, элементы которой будут упорядочены по возрастания, и найдены нечетные строки, элементы которой будут упорядочены по убыванию. Для сортировки (упорядочивания) строки массива по возрастанию или убыванию используем алгоритм сортировки обменом.
Описание алгоритма решения задачи графическим способом
Укрупненная схема алгоритма
Детализация укрупненной схемы алгоритма
В программе решается 3 подзадачи:
Заполнение двумерного массива;
Сортирование элементов четных строк по возрастанию, нечетных строк по убыванию;
Вывод преобразованного массива.
Ввод элементов двумерного массива
Как оговаривалось в постановке задачи, ввод элементов двумерного массива будем осуществлять с помощью генератора случайных чисел. Возьмем, к примеру, интервал от -5 до 15. Тогда, используя формулу Random(b-a+1)+a, получим Random(21)-5. Таким образом, каждый очередной элемент массива будет представлять собой целое число из диапазона [-5, 15] и выводится на экран. Цикл работает до достижения переменной i значения n, то есть до конца массива. Алгоритм заполнения массива соответствующими числами указан ниже:
Сортирование элементов четных строк по возрастанию, нечетных строк по убыванию
Сортирование элементов четных строк по возрастанию работает следующим образом: в начале определяем, является ли строка четной. Это определяется с помощью условия If I mod 2 =0, если строка четная, то номер строки делится на 2 без остатка.
В начале находим элемент с наименьшим значением (min) во всей строке и ставится на первое место, а первый элемент при этом ставится на место, где располагался наименьший элемент. Затем наименьший элемент отыскивается уже среди чисел со второго по n элемент, и также меняются местами минимальный среди них и второй элемент и т.д. Для того чтобы не терялись значение элементов массива вместо которых ставятся элементы с наименьшим значение, введена переменная S. Если условие If I mod 2 =0 произошло с остатком, то строка нечетная и начинается сортировка по убыванию. Находим элемент с наименьшим значение во всей строке. Ставим его на последнее место, а последний элемент при этом ставится на место, где располагался наименьший элемент. Чтобы элемент не терялся используем переменную S.
Вывод преобразованного массива
После сортировки выводим полученный массив на экран. Вывод элементов двумерного массива осуществляется при помощи цикла с параметром.
Блок-схема алгоритма
Разработка программы на языке Pascal
Программа начинается со служебного слова Program, после которого следует заголовок программы. В данном случае это massiv. Далее включаем раздел Uses для использования модуля CRT, который применяется для управления работой экрана в текстовом режиме. После названия программы и идентификации используемых модулей следует раздел объявления констант (const) и переменных (var).
В данной программе в разделе констант объявлены константы n=4 (количество строк массива) и m = 5 (количество столбцов массива). В разделе переменных описан целочисленный массив под именем a, целочисленные переменные i, j – счетчики циклов, min – минимальный элемент, imin – индекс минимального элемента, minst – минимальный элемент столбца, k – вспомогательная переменная для сортировки элементов.
Тело программы или раздел операторов начинается со слова begin и заканчивается end. В этом разделе описываем действия, которые должна выполнить программа согласно выбранного алгоритма. Так как в программе подразумевается ввод данных с экрана и вывод полученных результатов на экран, перед началом программы его необходимо очистить от ненужной информации. Это проделывает процедура clrscr, которая описана в модуле Crt.
Перед первым обращением к функции random необходимо с по-мощью вызова процедуры randomize инициализировать программный генератор случайных чисел, иначе при каждом запуске программы датчик будет выдавать одни и те же числа.
Описание блоков укрупненной схемы алгоритма на языке Pascal
Ввод элементов двумерного массива
Для того, чтобы прокомментировать, что вначале будет выведен исходный массив на экран, используем оператор writeln ('исходная матрица:').
Рассмотренный фрагмент блок-схемы для реализации ввода элементов двумерного массива на языке Pascal будет представлен в следующем виде:
for i:=1 to n do
begin
for i:=1 to n do begin
a[i,j]:=random(21)-5;
write(a[i,j]); end;
writeln;
end;
writeln;
Следующий далее оператор writeln без параметров просто переводит курсор на другую строку. Это необходимо для того, чтобы данные выводились на экран в виде матрицы. Добавим еще оператор writeln без параметров для более удобного восприятия информации с экрана.
Сортирование элементов четных строк по возрастанию, нечетных строк по убыванию
Далее начинаем обработку массива. Обработка массива осуществляется в цикле с параметром for i:=1 to n do по строкам массива. Далее с помощью условия определяем if i mod 2=0 then определяем четность строки.
Задаем цикл с параметром for k:=1 to m do, k это переменная для обозначение столбца массива. Определяем первый элемент массива как минимальный, для того чтобы можно было сравнивать с ним другие элементы и отыскать минимальный из них. Условием if a[i,j]--PAGE_BREAK--
Если первое условие не выполнилось if i mod 2=0 then то происходит сортировка нечетной строки по убыванию.
Обработка массива начинается с цикла с параметром. Задаем переменную max, в эту перемену присваиваем значение первого элемента max:=a[i,k]. Задаем цикл с параметром for j:=k to m do. Проверяем выполнения условия if a[i,j]>max, если условие выполняется то в переменную max заносим элемент массива a[i,j].
В переменную S заносим значение массиваA[i,k], в массив A[i,k] заносим значение максимального элемента max и восстанавливаем в переменную A[i,l]значение переменной S.
for i:=1 to n do begin
if i mod 2=0 then for k:=1 to m do begin
min:=a[i,k];
for j:=k to m do
if a[i,j]
begin min:=A[i,j]; l:=j;
S:=A[i,k];
A[i,k]:=min;
A[i,l]:=S end; end
else for k:=1 to m do begin
max:=a[i,k];
for j:=k to m do
if a[i,j]>max then
begin max:=A[i,j]; l:=j;
S:=A[i,k];
A[i,k]:=max;
A[i,l]:=S end; end;
end;
Вывод преобразованного массива
После сортировки выводим полученный массив на экран стандартными средствами вывода:
for i:=1 to n do
begin
for i:=1 to n do
write(a[i,j]:4);
writeln;
end;
где write(a[i,j]:4)– вывод элементов двумерного массива в строку
с указанием количества занимаемых позиций
Листинг программы
Program massiv;
Uses crt;
Const n=5; m=5;
Var a: array[1..n, 1..m] of integer;
i, j, k,min,max, l, s: integer;
Begin
Clrscr; randomize;
Writeln('исходный:'); begin
For i:=1 to n do
Begin
for j:=1 to m do begin
a[i,j]:=random(21)-5; write(a[i,j]:4); end;
writeln; End; Writeln;end;
for i:=1 to n do begin
if i mod 2=0 then for k:=1 to m do begin
min:=a[i,k];
for j:=k to m do
if a[i,j]
begin min:=A[i,j]; l:=j;
S:=A[i,k];
A[i,k]:=min;
A[i,l]:=S end; end
else for k:=1 to m do begin
max:=a[i,k];
for j:=k to m do
if a[i,j]>max then
begin max:=A[i,j]; l:=j;
S:=A[i,k];
A[i,k]:=max;
A[i,l]:=S end; end;
end;
begin
writeln(результат:'); For i:=1 to n do Begin
for j:=1 to n do write(a[i,j]:4);
Writeln;
end; end;
readln;
End.
Тестирование программы
Ниже приведены результаты выполнения программы на примере различных входных данных.
/>
/>
Список используемой литературы
1. А.И. Гусева. Учимся программировать: Pascal 7.0. М. диалог-мифи, 2000г.
2. А.Ф. Иванов, О.Н. Потапова, Г.Л. Салихова А. Основные алгоритмы языка Pascal, учебное пособие. 2007г.
3. А.Ф. Иванов А. Программирование на алгоритмическом языке Pascal, 2000г.
4. Семакин И.Г., Шестаков А.П. Основы программирования. М.: Академия, 2003г.