Альметьєвська державний нафтовий інститут
Кафедра інформатики
Курсова робота
З ДИСЦИПЛІНИ «ІНФОРМАТИКА»
РОЗДІЛ: Алгоритмічна мова Pascal
НА ТЕМУ:
«Розробка в середовищі Turbo Pascal програми сортування елементів рядків матриці»
Алмет'евськ 2010
Рішення задачі графічним та програмним способами за темою «двовимірні масиви»
Тема курсової роботи: «Розробка в середовищі Turbo Pascal програми сортування елементів рядків матриці».
Постановка завдання
Елементи парних рядків матриці розміром nxm порядок за зростанням, елементи непарних рядків-за спаданням. Для налагодження програми елементи двовимірного масиву сформувати за допомогою генератора випадкових чисел.
Вихідними даними є елементи двовимірного масиву, які повинні бути створені за умовою задачі за допомогою генератора випадкових чисел 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] <min порівнюються два елементи одного рядка. Якщо умова виконується то в мінімальний присвоюється наступний елемент min: = A [i, j]. Потім міняємо місцями ці елементи. Змінна S використовуємо проміжний елемент для зберігання елемента масиву S: = A [i, k]. Потім заносимо в масив A [i, k] мінімальний елемент A [i, k]: = min, а в масив A [i, l] відновлюємо значення з змінної S (A [i, l]: = S).
Якщо перша умова не виповнилося 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] <min then
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] <min then
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.