Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютеризовані системи
Кафедра:
Не вказано
Інформація про роботу
Рік:
2001
Тип роботи:
Інші
Предмет:
Алгоритмічні мови та програмування
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний університет «Львівська політехніка»
РОБОТА З МАСИВАМИ. ВИКОРИСТАННЯ ПРОЦЕДУР ТА ФУНКЦІЙ
ІНСТРУКЦІЯ ДО ЛАБОРАТОРНОЇ РОБОТИ № 3
З КУРСУ «АЛГОРИТМІЧНІ МОВИ І ПРОГРАМУВАННЯ»
для студентів спеціальності 6.0914
«Комп’ютеризовані системи, автоматика і управління»
Затверджено
на засiданнi кафедри
«Автоматика та телемеханiка»
Протокол № 11 вiд 15.03.2001 p.
Львів 2001
Робота з масивами. Використання процедур та функцій: Інструкція до лабораторної роботи №3 з курсу «Алгоритмічні мови і програмування» для студентів спеціальності 6.0914 «Комп’ютеризовані системи, автоматика і управління» / Укл.: Р.А.Гордійчук, В.І.Отенко, А.Е.Лагун – Львів: НУЛП, 2001.- 16 с.
Укладачі: Р.А.Гордійчук, ст. викладач,
В.І.Отенко, канд. техн. наук, доцент
А.Е.Лагун, асистент.
Вiдповiдальний за випуск І.М. Ковела, канд.техн.наук, доцент
Рецензенти: В.В.Самотий, доктор техн. наук, професор
Мета роботи - вивчити синтаксис опису і використання в програмах змінних типу масив, навчитися використовувати масиви для оброблення матриць, вивчити основні алгоритми сортування масивів; навчитися описувати та застосовувати у програмах процедури і функції для виконання логічно закінчених алгоритмів.
1. КОРОТКІ ТЕОРЕТИЧНІ ДАНІ
1.1. Масиви.
Масив - це сукупність елементів одного типу, доступ до кожного з яких забезпечується вказанням ідентифікатора масиву і порядкового номера (індексу) елемента в масиві. Кількість елементів у масиві задається під час описання змінної-масиву і надалі в програмі змінюватися не може. Розмір масиву не може перевищувати 64 кбайт (65535 байт). Оперативна пам'ять, виділена для локальної змінної-масиву при її описі, як правило, звільняється після закінчення виконання процедури (функції), в якій вона описана.
Для опису змінної типу масив, як правило, спочатку описують тип-масив в розділі опису типів, після чого в розділі опису змінних описують змінну-масив, використовуючи ім'я описаного типу-масиву:
type
<ім'я_типу> = array[<тип_індексу>{,<тип_індексу>}] of <тип_елементів>;
...
var
<ім'я_змінної> : <ім'я_типу>;
де array, of - зарезервовані слова Турбо-Паскаля;
<ім'я_типу>, <ім'я_змінної> - ідентифікатори мови Турбо-Паскаль;
<тип_індексу> - будь-який порядковий тип, крім longint і типів-діапазон з базовим типом longint.
Як правило, використовується тип-діапазон;
<тип_елементів> - будь-який тип мови Турбо-Паскаль, зокрема структурований.
Використовується також спрощена форма опису змінної-масиву:
var
<ім'я_змінної> : array[<тип_індекса>{,<тип_індекса>}] of <тип_елементів>;
В оперативній пам'яті комп'ютера елементи масиву розташовані один за одним так, що при переході від молодших до старших адрес у першу чергу змінюється крайній правий індекс масиву.
Алгоритми оброблення масивів програмуються, як правило, з використанням оператора циклу for.
Нижче наведена програма, яка вводить елементи двовимірного масиву з клавіатури і виводить на екран квадрати їх значень.
program Array_Demo;
const
N=5;
M=10;
type
Matrix=array[1..N,1..M] of real;
var
a : Matrix;
i,j : integer;
BEGIN
writeln('Введіть елементи матриці :');
for i:=1 to N do
for j:=1 to M do
begin
write (' а[',i,j,']= ');
read (a[i,j])
end;
writeln('Значення елементів матриці, піднесених до квадрата :');
for i:=1 to N do
for j:=1 to M do
writeln (' квадрат а[',i,j,']= ', sqr(a[i,j]));
END.
1.2. Процедури і функції.
Засобами структурних методів розроблення програмного забезпечення в мові Турбо-Паскаль є процедури і функції.
Різниця між функцією і процедурою полягає в тому, що результатом виклику функції (виконання послідовності її внутрішніх операторів) є значення деякого типу, вказаного при її описі. Тому виклик функції може використовуватися тільки як операнд виразу або фактичний параметр. Процедура в зовнішню програму безпосередньо значення не повертає. Якщо необхідно, це можна зробити через параметр-змінну. Процедура не може використовуватися як операнд виразу.
Описуються процедури і функції в програмі, як правило, після опису глобальних змінних. Якщо в тілі однієї процедури (функції) P1 викликається процедура (функція) P2, то P2 повинна бути описана до свого виклику. Винятком з цього правила є попередня декларація.
Опис процедури:
procedure <ім'я_процедури>[({[var]<змінна>{,<змінна>}:<тип>[;]})];
[<опис локальних імен>]
begin
<послідовність операторів> {тіло процедури}
end;
Опис функції:
function <ім'я_функції>[({[var]<змінна>{,<змінна>}:<тип>[;]})]: <тип>;
[<опис локальних імен>]
begin
<послідовність операторів> {тіло функції}
end;
де <ім'я_процедури>,<ім'я_функції> - ідентифікатори мови Турбо-Паскаль;
<змінна> - ім'я локальної змінної, яку називають формальним параметром і через яку процедурі (функції) при її виклику з зовнішньої програми передаються вхідні дані, які називають фактичними параметрами;
<тип> - ім'я стандартного типу, або типу, попередньо оголошеного в розділі type.
Символ-розділювач «;» після оголошення останнього формального параметра (перед круглою дужкою, що закриває, в заголовку процедури (функції)) не ставиться.
Кількість та типи формальних і фактичних параметрів повинні збігатися.
Якщо перед <змінною> не стоїть зарезервоване слово var, то вона визначена як параметр-значення. В такому випадку фактичним параметром є значення виразу, що відповідає формальному параметру при виклику процедури (функції). Якщо фактичним параметром є глобальна (зовнішня) змінна, то процедура (функція) не може змінити її значення, оскільки їй буде передана тільки копія цієї глобальної змінної.
Якщо перед <змінною> стоїть зарезервоване слово var, то вона визначена як параметр-змінна. В такому випадку як фактичний параметр можуть бути застосовані лише ідентифікатори глобальних змінних (використання виразів не допускається). При цьому процедура (функція) отримує доступ до комірки пам'яті, в якій зберігається глобальна змінна, і може змінити її значення.
Процедура може повернути результат свого виконання тільки через параметр-змінну. Передавати дані у функцію рекомендується через параметри-значення;
<опис локальних імен> - опис локальних (внутрішніх) типів, констант, змінних, процедур і функцій, які доступні для використання тільки в даній процедурі (функції), і термін існування яких в оперативній пам'яті комп'ютера визначається часом виконання цієї процедури (функції) після її виклику. Описувати типи всередині процедури (функції) не рекомендується;
<послідовність операторів> - послідовність операторів мови Турбо-Паскаль, а також виклики процедур (функцій).
Тіло функції повинно містити оператор присвоєння вигляду <ім'я_функції>:=<вираз>, де <вираз>- вираз мови Турбо-Паскаль, значення якого буде повернуте функцією в зовнішню програму і тип якого повинен бути сумісним з типом, що повертається функцією і вказаний при її описі.
Оголошення типів у заголовку процедури (функції) не допускається. Конструкції
procedure Sort_Array ( var a: array[1..10] of real );
function Sum_String_of_Matrix ( a: array[1..5,1..10 ): array[1..5] of double;
є забороненими, оскільки оголошуються типи-діапазони, які вказують межі індексів масивів. Синтаксично правильними є такі конструкції:
type
Array10_Type = array[1..10] of real;
Array5_Type = array[1..5] of double;
Matrix_5x10_Type = array[1..5,1..10] of real;
procedure Sort_Array ( var a:Array10_Type );
begin
...
end;
function Sum_String_of_Matrix (a:Matrix_5x10_Type):Array5_Type;
var
sum : Array5_Type;
begin
...
Sum_String_of_Matrix:=sum
end;
...
1.3. Основні алгоритми сортування масивів.
Сортування вставкою . На і-му кроці значення і-го елемента масиву тимчасово запам'ятовується в змінній x і послідовно порівнюється з j-ми елементами в бік першого елемента за встановленим критерієм (наприклад, x<аj при сортуванні за зростанням). Поки критерій справджується, j-ті елементи масиву послідовно переміщуються в бік і-го елемента. Значення і-го елемента, записане в змінній x, вставляється в масив після j-го елемента, для якого заданий критерій порівняння не справджується. На кожному кроці зона порівняння збільшується на один елемент в бік кінця масиву. Блок-схема алгоритму наведена на рис. 1. Порівняння за заданим критерієм здійснює функція f(aj,x), яка повертає тип boolean.
Рис.1. Блок-схема алгоритму сортування вставкою
Сортування вибором. На і-му кроці серед (n-i) елементів, послідовно порівнюючи елементи в бік останнього елемента масиву, шукається елемент, значення якого найкраще задовольняє заданому критерію (наприклад, найменше). Значення знайденого таким чином елемента міняється місцями із значенням і-го елемента. На кожному наступному кроці зона пошуку зменшується на один елемент від початку масиву. Блок-схема алгоритму наведена на рис. 2. Порівняння за заданим критерієм здійснює функція f(aj,x), яка повертає значення типу boolean.
Рис.2. Блок-схема алгоритму сортування вибором
Сортування обміном (бульбашкове сортування). На і-му кроці порівнюються за визначеним критерієм (наприклад, аj <aj-1) значення всіх сусідніх пар з (n-i) елементів від кінця масиву до і-го елементу. Якщо для поточної пари критерій справджується, то елементи міняються місцями. Після (n-1) проходів масив стає відсортованим. Блок-схема алгоритму наведена на рис. 3. Порівняння за заданим критерієм здійснює функція f(aj,aj-1), яка повертає тип boolean.
Рис.3. Блок-схема алгоритму сортування обміном
2. ЗАВДАННЯ
2.1. Домашня пiдготовка до роботи
1. Вивчити правила опису та використання змінних-масивів в програмах, написаних алгоритмічною мовою Турбо-Паскаль.
2. Вивчити правила опису та виклику процедур і функцій в програмах, написаних алгоритмічною мовою Турбо-Паскаль.
3. Вивчити основні алгоритми сортування масивів.
4. Написати програму алгоритмічною мовою Турбо-Паскаль згідно з завданням, отриманим від викладача за табл. 1: задану прямокутну матрицю A={aij} відсортувати за вказаним алгоритмом; для відсортованої матриці знайти значення функції F(fi(aij)); алгоритм сортування оформити у вигляді процедури; обчислення fi(aij) оформити у вигляді функції; елементи матриці вводити з клавіатури; програма повинна вивести на екран відсортовану матрицю, всі значення fi(aij) та значення функції F(fi(aij)).
Таблиця 1
№ п/п
Алгоритм впорядкування матриці
Алгоритм для розрахунку fi(aij) та F(fi(aij))
Матриця
1
Впорядкувати елементи стовпців матриці за спаданням їх значень методом вставки
fi(aij)-максимальний елемент у кожному рядку матриці; F(fi(aij))-сума fi(aij).
-12 7 23 13 4
67 15 34 -5 9
2 5 17 -23 45
26 -6 23 -5 -9
18 37 -8 26 12
2
Впорядкувати елементи рядкв матриці за зростанням їх значень методом обміну
fi(aij)-мінімальний елемент у кожному стовпці матриці; F(fi(aij))-добуток fi(aij)
34 -8 27 7 12
-5 23 45 67 -2
13 -12 34 -3 25
17 56 -6 17 21
0 15 4 9 -14
3
Впорядкувати елементи
стовпців матриці за зростанням їх значень методом вибору
fi(aij)-сума елементів у кожному рядку матриці; F(fi(aij))-середнє геометричне значення fi(aij)
2 0 33 -1 -21
78 7 -4 -3 11
-2 -7 -1 -9 0
13 61 60 42 -10
1 0 4 0 16
4
Впорядкувати елементи рядків матриці за спаданням їх значень методом вставки
fi(aij)-добуток елементів у кожному стовпці матриці; F(fi(aij))-середнє арифме-тичне значення fi(aij)
90 7 89 -2 17
1 -4 8 56 32
-4 -6 -99 19 39
2 4 -7 0 75
11 41 22 80 -5
5
Впорядкувати елементи стовпців матриці за зростанням їх значень методом обміну
fi(aij)-середнє арифметичне значення елементів у кожному рядку матриці; F(fi(aij))-добуток fi(aij)
40 72 6 92 98
18 -33 -48 81 26
1 -4 6 -2 0
36 9 0 4 1
-55 2 66 70 -3
6
Впорядкувати елементи рядків матриці за спаданням їх значень методом вибору
fi(aij)-середнє геометричне значення елементів у кожному стовпці матриці; F(fi(aij))-сума fi(aij)
-3 -5 -45 -71 -5
0 1 3 2 7
11 9 45 0 4
9 19 55 44 90
-3 -4 -1 -5 0
7
Впорядкувати елементи стовпців матриці за зростанням їх значень методом вставки
fi(aij)-добуток елементів у кожному рядку під головною діагоналлю матриці; F(fi(aij))-сума fi(aij)
6 34 12 70 -1
-7 97 80 99 -99
1 6 -3 2 -8
3 33 -1 0 -78
-3 -5 -8 -56 -23
8
Впорядкувати елементи рядків матриці за спаданням їх значень методом обміну
fi(aij)-сума елементів у кожному стовпці над головною діагоналлю матриці; F(fi(aij))-добуток fi(aij)
9 67 -65 45 1
12 61 48 -5 -1
0 39 0 41 2
36 95 -8 -5 0
11 22 71 3 63
9
Впорядкувати елементи рядків матриці за зростанням їх значень методом вибору
fi(aij)-сума елементів у кожному стовпці над допоміжною діагоналлю матриці; F(fi(aij))-середнє геометричне значення fi(aij)
44 -2 -5 38 -91
2 0 6 3 22
13 1 -4 90 11
-3 -6 -98 -23 -24
10 34 32 31 69
10
Впорядкувати елементи стовпців матриці за спаданням їх значень методом обміну
fi(aij)-добуток елементів у кожному рядку під допоміжною діагоналлю матриці; F(fi(aij))-середнє арифметичне значення fi(aij)
-1 -5 -47 -8 -1
-4 -98 -90 -45 -78
-3 -2 -5 -9 -4
-8 -67 -33 -91 -40
-2 -58 -11 -65 -77
11
Впорядкувати елементи рядків матриці за зростанням їх значень методом вставки
fi(aij)-середнє арифметичне значення елементів у кожному стовпці під головною діагоналлю матриці; F(fi(aij))-добуток fi(aij)
1 16 21 11 6
2 17 22 12 7
3 18 23 13 8
4 19 24 14 9
5 20 25 15 10
12
Впорядкувати елементи стовпців матриці за спаданням їх значень методом обміну
fi(aij)-середнє геометричне значення елементів в кожному рядку над голов-ною діагоналлю матриці; F(fi(aij))-сума fi(aij)
0 2 -2 89 21
-1 -4 36 41 71
56 93 51 -2 -51
1 3 -8 0 9
23 41 5 8 -2
13
Впорядкувати елементи рядків матриц за спаданням їх значень методом вставки
fi(aij)-середнє арифметичне значення елементів у кожному стовпці над допоміжною діагоналлю матриці; F(fi(aij))-добуток fi(aij)
12 46 -23 72 -5
59 7 -8 0 67
7 -8 -4 -97 -55
77 -1 -5 34 -8
0 22 27 24 24
14
Впорядкувати елементи рядків матриці за зростанням їх значень методом обміну
fi(aij)-сума елементів у кожному стовпці під допоміжною діагоналлю матриці; F(fi(aij)) –середнє геометричне значення fi(aij)
87 98 57 29 95
-8 59 -2 9 -11
6 10 20 59 -23
12 13 51 46 -7
-2 87 69 90 -3
15
Впорядкувати елементи стовпців матриці за зростанням їх значень методом вибору
fi(aij)-добуток елементів у кожному рядку над головною діагоналлю; F(fi(aij))-середнє арифметичне значення fi(aij)
50 98 -4 85 -8
40 73 -2 -9 -19
1 6 73 21 0
0 25 2 -5 -3
99 19 95 92 -7
16
Впорядкувати елементи рядків матриці за спаданням їх значень методом вставки
fi(aij)-сума елементів у кожному стовпці під головною діагоналлю матриці; F(fi(aij))-середнє геометричне значення fi(aij)
3 5 9 24 2
-23 0 37 29 10
0 1 4 -2 -5
-5 -83 -74 82 -1
11 88 -5 81 -39
17
Впорядкувати елементи стовпців матриці за зростанням їх значень методом обміну
fi(aij)-середнє геометричне значення елементів у кожному рядку матриці; F(fi(aij))-середнє арифметичне значення fi(aij)
66 21 -3 -1 90
1 74 -2 80 -1
10 30 20 -50 91
2 4 5 81 0
33 69 -5 51 24
18
Впорядкувати елементи рядків матриці за спаданням їх значень методом вибору
fi(aij)-середнє арифметичне значення елементів у кожному стовпці над допоміжною діагоналлю; F(fi(aij))- добуток fi(aij)
33 -5 -9 -20 -11
0 -42 86 83 71
-6 -9 33 13 22
52 -5 -7 53 19
-3 98 72 68 0
19
Впорядкувати елементи стовпців матриці за зростанням їх значень методом вставки
fi(aij)-середнє геометричне значення елементів у кожному рядку над головною діагоналлю; F(fi(aij))-сума fi(aij)
34 45 65 23 98
1 -4 67 -3 -18
23 -5 -1 94 -25
2 24 -4 79 -63
10 29 25 30 -6
20
Впорядкувати елементи рядків матриці за спаданням їх значень методом обміну
fi(aij)-добуток елементів у кожному стовпці під головною діагоналлю матриці; F(fi(aij))-середнє арифметичне значення fi(aij)
19 62 -45 -1 84
23 54 -4 -2 68
36 39 96 94 97
-3 -8 -4 -6 -22
98 -5 -3 0 11
21
Впорядкувати елементи стовпців матриці за зростанням їх значень методом вибору
fi(aij)-добуток елементів у кожному рядку над допо-міжною діагоналлю матриці; F(fi(aij))-сума fi(aij)
22 41 45 -45 -49
5 1 3 -2 0
34 97 48 72 -1
-3 -7 5 92 20
0 -3 -57 9 1
22
Впорядкувати елементи рядків матриці за спаданням їх значень методом обміну
fi(aij)-середнє арифметичне значення елементів у кожному стовпці матриці; F(fi(aij))-середнє геометричне значення fi(aij)
30 31 36 63 -2
2 24 -3 -7 -1
45 28 -98 2 -8
0 -1 -2 -3 93
11 10 72 85 66
23
Впорядкувати елементи стовпців матриці за зростанням їх значень методом вставки
fi(aij)-сума елементів у кожному рядку над головною діагоналлю матриці; F(fi(aij))-середнє геометричне значення fi(aij)
31 65 -83 -2 -85
9 -2 11 -4 70
52 73 -8 -1 60
57 83 -1 82 50
1 -3 -2 78 -9
24
Впорядкувати елементи рядків матриці за спаданням їх значень методом обміну
fi(aij)-добуток елементів у кожному стовпці під допоміжною діагоналлю матриці; F(fi(aij))-середнє арифметичне значення fi(aij)
10 32 1 -8 -1
2 4 91 -82 96
33 62 -1 -8 0
5 -5 6 -6 7
-19 0 3 -22 -3
25
Впорядкувати елементи стовпців матриці за спаданням їх значень методом вставки
fi(aij)-середнє геометричне значення елементів у кожному рядку під головною діагоналлю матриці; F(fi(aij))-сума fi(aij)
9 24 -2 86 -3
40 49 -4 -3 0
27 -76 77 -1 69
71 -89 -94 -51 50
2 96 42 36 -1
2.2. Робота в лабораторiї
1. Ввести в комп'ютер програму, написану мовою Турбо-Паскаль згідно з отриманим завданням.
2. Відлагодити введену програму, виправивши виявлені компілятором помилки.
3. Виконати програму. Остаточний текст відлагодженої програми та отримані результати занести в звіт по лабораторній роботі.
3. ЗМIСТ ЗВIТУ
1. Повний текст завдання.
2. Блок-схема алгоритму програми.
3. Список ідентифікаторів констант, змінних, процедур і функцій, використаних в програмі, та їх пояснення.
4. Остаточно відлагоджений текст програми згідно з отриманим завданням.
5. Результати виконання програми.
4. КОНТРОЛЬНI ЗАПИТАННЯ
1. Поясніть, як можна описати змінну-масив мовою Турбо-Паскаль.
2. Як здійснюється доступ до елементів масиву ?
3. Як описуються процедури і функції мовою Турбо-Паскаль? В чому полягає різниця між процедурою і функцією ?
4. Як передаються фактичні параметри при виклику процедур і функцій ?
5. Який з простих методів сортування, на Ваш погляд, є найкращим, а який найгіршим ? Поясніть чому ?
СПИСОК ЛIТЕРАТУРИ
1. Фаронов В.В. Программирование на персональных ЭВМ в среде Турбо-Паскаль.- 2-е изд. - М.: Изд-во МГТУ, 1992.
2. Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка.- М.: Финансы и статистика, 1982.
3. Сердюченко В.Я. Розробка алгоритмів та програмування на мові Turbo Pascal: Навчальний посібник для техн. вузів - Х.: ВКП "Парітет" ЛТД, 1995.
4. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985.
5. Гроного П. Программирование на языке Паскаль. - М.: Мир, 1982.
Навчальне видання
Робота з масивами. Використання процедур та функцій: Інструкція до лабораторної роботи №3 з курсу «Алгоритмічні мови і програмування» для студентів спеціальності 6.0914 «Комп’ютеризовані системи, автоматика і управління»
Укладачі: Гордійчук Роман Анатолійович,
Отенко Віктор Іванович,
Лагун Андрій Едуардович.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора