_TPLab_My_Посібник

3. ТИПОВІ ЗАДАЧІ ОПРАЦЮВАННЯ МАСИВІВ.

3.1. Сортування масиву.

Означення. Сортування масиву даних – це впорядкування елементів масиву за певним критерієм, тобто розташування компонент масиву в певному порядку.

Задача сортування (впорядкування) є однією з типових задач опрацювання масивів даних. Якщо елементи масиву містять декілька полів, то поле, яке слугує критерієм порядку, називається ключем сортування. В масивах даних, елементи яких є прості, критерієм порядку є, власне, значення елемента, тобто, ключем сортування є сам елемент.

Алгоритми сортування оцінюються за швидкістю виконання та ефективністю використання

характеристику алгоритмів сортування також називають обчислювальною складністю.

Для значної кількості алгоритмів середній і найгірший час впорядкування n-елементного масиву є O(n2), це пов'язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між

В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.

Теорема про найкращий час сортування

Якщо алгоритм сортування в своїй роботі спирається тільки на операції порівняння двох об'єктів (≤) і не враховує жодної додаткової інформації про елементи, то він не може впорядкувати масив елементів швидше ніж за O(nLogn) в найгіршому випадку [Вікіпедія].

Пам’ять – ряд алгоритмів сортування вимагає виділення додаткової пам’яті для тимчасового зберігання даних. Як правило, ці алгоритми вимагають O(nLogn) пам’яті. Алгоритми сортування, які не використовують додаткову пам’ять, відносяться до сортувань на місці.

Крім вищевказаних характеристиками алгоритмів сортування є стабільність (чи нестабільність)

та використання (чи без використання) додаткової інформації про елементи. Означення. Стабільним називається такий алгоритм сортування, що не змінює порядок елементів з однаковим ключем.

На сьогодні розроблено багато алгоритмів сортування масивів даних. Далі розглядаються одні з найпростіших алгоритмів – сортування вибором екстремальних елементів та «бульбашкове»

сортування.

Алгоритм сортування вибором екстремальних елементів є нестабільним і неефективним для великих масивів даних – має складність O(n2).

Алгоритм «бульбашкового» сортування є стабільним але його складність також O(n2).

Приклади.

Для виконання сортування масив зручно представити у вигляді послідовності комірок, в яких зберігаються компоненти масиву.

Масив Mas:

Сортування за зростанням вибором мінімального елементу:

Знайти в масиві найменший елемент та його номер i поставити його на 1-ше місце, а 1-й елемент - на місце, де був знайдений найменший елемент. У даному прикладі найменшим є 5-й елемент.

Після перестановки масив буде мати такий вигляд:

Тепер аналогічні дії можна повторити, але пошук мінімального i перестановку треба почати з другого елементу. В даному випадку мінімальним буде 9-й елемент. Після перестановки масив буде мати такий вигляд:

-65 -47 13 0 -3 11 37 71 17 1 значення

51

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Таким чином, описані дії треба повторювати доти, доки не буде досягнуто 10-го елементу. Після цього масив буде відсортовано за зростанням. Отже, якщо масив містить N елементів, то треба створити два вкладених цикли. У внутрішньому циклі виконується пошук найменшого елементу і його індексу (номеру). А після закінчення внутрішнього циклу потрібно виконувати дві дії:

-робити перестановку знайденого мінімального елементу з елементом, що знаходиться на початку чергового пошуку;

-збільшувати на 1 (одиницю) значення допоміжної змінної j, яке рівне індексу елемента, з якого розпочинається наступний пошук мінімального елементу.

Наприклад:

{починаємо шукати з 1 елемента : }

For i 1 To 10 Do {1} Begin

{ за мін.елем. приймаємо перший елемент підмасиву від i до 10} k i; {номер мiн. елемента = i }

Min Mas[i]; {значення мін.елем. }

For j i +1 To 10 Do

{знайдемо мін. елем. в підмасиві від i до 10 }

If Min>Mas[j] Then Begin

k j;{запишемо номер мін.елем.} Min Mas[j] { і його значення }

End;

{ поміняємо місцями знайдений мін.елем. Mas[k] } { і перший елемент з підмасиву Min[i] } Mas[k] Mas[i];

Mas[i] Min;

End; {For 1}

«Бульбашкове» сортування полягає в тому, що елементи масиву порівнюються послідовно та попарно, i якщо наступний буде меншим за попередній, то вони міняються місцями. Тобто більший з двох елементів «випливає» як бульбашка - просувається в бік зростання значень масиву. Тому цей метод називається «бульбашковий». Порівняння починається з перших двох елементів. У даному випадку перший елемент менший ніж другий, отже, перестановку (обмін) не виконуємо. Після цього порівнюємо другий i третій елементи. Необхідна перестановка елементів, після якої масив матиме вигляд:

Цю процедуру (операції порівняння та обміну) виконуємо до досягнення кінця масиву, а потім її потрібно повторити ще 9 разів.

Якщо масив містить N елементів, то необхідно створити два вкладених цикли з кількістю проходів N-1 кожний. У внутрішньому циклі будуть порівнюватись та переставлятись за необхідністю сусідні елементи, а зовнішній має його повторити N-1 разів.

52

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

3.1. Знаходження максимального елемента масиву.

Нехай елементи рядка з максимальним елементом матриці випадкових цілих чисел необхідно переписати в одномірний масив.

a) Аналіз вимог користувача (аналіз задачі на змістовому рівні).

Необхідно сформувати двомірний масив (матрицю) випадкових чисел (використаємо функцію RANDOM); знайти максимальний елемент, запам’ятавши його перший індекс – номер рядка; сформувати одномірний масив з елементів визначеного рядка матриці, кількість цих елементів рівна кількості стовпців матриці.

b) Математична модель об’єктів дослідження.

Двомірний масив (матриця):

А=||aij||nm = { aij = RANDOM (С), i =1,2,…,n , j =1,2,…,m }; Одномірний масив (вектор):

B=||bk||m = { bk , k =1,2,…,m} c) Інформаційна модель задачі.

Максимальний елемент:

Max = aps , 1≤p≤n, 1≤s≤m, i p j s aij < aps Формування одномірного масиву:

bk = apk , k = 1,2,..3,m

d) Обґрунтування способу розв’язку задачі.

Максимальний елемент знаходимо наступним чином: прийнявши за максимальний елемент Max перший елемент а11 матриці А, порівнюємо його з кожним наступним елементом матриці. Якщо Max менший деякого поточного елемента матриці, то за максимальний елемент приймаємо цей поточний елемент.

Max = а11; аij > Max Max аij, i=1,2,…n; j=1,2,…,m; e) Обґрунтування структури алгоритму.

Для формування матриці А використаємо базову структуру циклу із заданим числом повторень – один цикл з числом повторень n, другий – з числом повторень m.

Таку ж конструкцію (подвійний цикл) використаємо для знаходження максимального елемента матриці. Для порівняння максимального з іншими елементами матриці і можливого перевизначення максимального використаємо базову структуру єдиного вибору.

Для формування масиву В використаємо один цикл з числом повторень m.

f)Блок-схема алгоритму приведена на Рис.1.

g)Обґрунтування структури програми.

Перший блок програми призначений для формування матриці А за допомогою вбудованої функції RANDOM(С), де С – деяке ціле число, яке вводиться користувачем з клавіатури. Подвійний цикл реалізуємо двома операторами For…To…Do. Одночасно з формуванням будемо виводити (друкувати) елементи матриці.

Вдругому блоці програми реалізуємо пошук максимального елемента матриці в подвійному циклі For…To…Do. Для реалізації структури єдиного вибору використаємо скорочений умовний оператор If…Then. Необхідно використати допоміжну змінну для запам’ятовування номера рядка максимального елемента.

Втретьому блоці з одним циклом For…To…Do (з числом повторень m) сформуємо і виведемо елементи масиву В.

h)Специфікація змінних.

53

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

i)Специфікація процедур і функцій.

Впрограмі буде використана вбудована функція RANDOM(С), де С – деяке ціле число, яке вводиться користувачем з клавіатури.

Стандартна процедура Write (Writeln) використовується для виведення інструкцій користувачу та масивів А і В.

Стандартна процедура Read (Readln) використовується для введення (зчитування) з клавіатури кількості рядків і стовпців матриці А та цілого числа С для генерування (обмеження значень) елементів матриці А.

j)Текст програми.

Program Maximum; Uses CRT;

Const D=25;

Var A: Array [1..D,1..D] Of Integer;

B: Array [1..D] Of Integer; i, j, N, M, p, Max, C: Integer;

Begin

ClrScr; {очистка екрану} {інтерфейс користувача}

Writeln (‘Лабораторна робота №4’);

Writeln (‘Формування одномірного масиву з елементів рядка матриці, який містить максимальний елемент ‘);

Writeln (‘Виконав ст. гр. 2АМ Петренко Петро ’); Write (‘Введіть кількість рядків матриці N≤25, N=’); Readln (N);

Write (‘Введіть кількість стовпців матриці M≤25, M=’); Readln (M);

Write (‘Введіть ціле число обмежуюче значення елементів матриці згори C=’); Readln (C);

For i 1 To N Do

Begin

Writeln; {перехід на новий рядок}

For j 1 To M Do

Begin

a[i,j] Random(C); Write (a[i,j]:3)

End; {For j}

End; {For i}

Max a[1,1]; {максимальний – перший елемент} p 1; {номер рядка з максимальним елементом} {пошук максимального елемента}

For i 1 To N Do For j 1 To M Do

If a[i,j]> Max Then Begin

Max a[i,j]; p i

End;

{формування одномірного масиву}

For j 1 To M Do Begin

b[j] a[p,j];

54

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Рисунок 1. Блок-схема алгоритму.

КОНТРОЛЬНІ ЗАПИТАННЯ:

1.Які типи даних називаються регулярними?

2.Які існують способи опису масивів?

3.Що таке індекс i для чого він використовується?

4.Які типи даних можна використовувати в якості індексів масивів?

5.Яким чином здійснюється доступ до компонент масиву?

6.Чому при опрацюванні масивів необхідно використовувати цикли?

7.Наведіть приклади з життя, в яких можна було б використовувати масиви.

8.В чому суть методу послідовного пошуку екстремальних елементів при сортуванні масивів?

9.В чому суть «бульбашкового методу» при сортуванні масивів?

10.Чому в «бульбашковому» методі потрібно повторювати (скільки разів?) процедуру перестановки елементів?

11.Порівняйте кількість проходів для першого i другого методів сортування масивів.

12.Як за допомогою функції RANDOM сформувати масив цілих (дійсних) чисел тільки з від’ємними елементами? З додатними і від’ємними елементами?

ЗАВДАННЯ ДЛЯ САМОСТІЙНОГО ВИКОНАННЯ.

Завдання 1.

Створити масив з 10-ти цілих чисел (типу INTEGER). Заповнити масив за допомогою процедури RANDOMIZE та генератора випадкових чисел RANDOM. Впорядкувати (відсортувати) масив згідно варіанту завдання. Провести спостереження процесу сортування в режимі відлагодження (DEBUG). Вивести на екран відсортований масив у вигляді стовпця, де в кожному рядку виводиться ім’я, індекс та значення компоненти масиву. Наприклад, U[3]=-67.

Варіанти завдань.

1.Виконати сортування елементів масиву за зменшенням, використовуючи «бульбашковий метод».

2.Виконати сортування елементів масиву за зростанням, використовуючи метод вибору (послідовного пошуку) екстремальних елементів.

3.Виконати сортування елементів масиву за зменшенням, використовуючи метод вибору екстремальних елементів.

4.Виконати сортування елементів масиву за зростанням, використовуючи «бульбашковий метод».

Завдання 2.

Сформувати квадратну матрицю (двомірний масив) з елементами xjk = RANDOM (7*i ) ± N, де і

– номер варіанту, N – деяке довільне ціле число, j,k =1..5. Вивести на екран початковий та опрацьований масиви у вигляді матриці, а також результати виконання завдання свого варіанту.

Примітка. При формуванні масиву необхідно врахувати, що функція RANDOM повертає тільки додатні значення, але деякі з наведених нижче завдань вимагають існування в масиві від’ємних значень. В такому випадку можна використати наступну формулу генерування значень елементів масиву:

xjk = RANDOM (17*i) - N,

Варіанти завдань.

1.Знайти середнє арифметичне елементів матриці, відкинувши найбільший та найменший елементи.

2.Всі від’ємні елементи матриці, які знаходяться вище головної діагоналі, піднести до квадрату та знайти максимальний з них.

3.Знайти кількість нульових i суму від’ємних елементів матриці.

4.Визначити максимальний з мінімальних елементів усіх рядків матриці та його індекси.

5.Визначити мінімальний елемент матриці i записати нулі в ті рядок i стовпець, на перетині яких він знаходиться.

6.Обчислити суму елементів матриці, які знаходяться над головною діагоналлю та кількість елементів, значення яких менші, ніж 4.

7.Обчислити добуток та кількість від’ємних елементів матриці, які знаходяться під головною діагоналлю.

56

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

8.Обчислити добуток елементів матриці, які знаходяться на головній діагоналі та визначити максимальний з них.

9.Обчислити суму елементів 1-го, 3-го i 5-го рядків матриці i поділити її на суму елементів 3-го стовпця.

10.Обчислити середнє арифметичне елементів кожного рядка матриці та суму цих середніх арифметичних.

11.Визначити максимальний та мінімальний елементи матриці, їх індекси та обчислити їх добуток.

12.Обчислити середнє геометричне додатних елементів матриці, які задовольняють умову xnk < 3.

13.Визначити чотири найбільші елементи матриці та їх індекси.

14.Обчислити середнє арифметичне максимального та мінімального елементів матриці.

15.Обчислити середнє арифметичне додатних елементів матриці.

16.Обнулити (присвоїти значення нуль) компоненти матриці менші заданого числа.

17.Рядок з максимальним елементом поміняти місцями з рядком з мінімальним елементом.

18.Переписати в одновимірний масив елементи головної діагоналі та елементи стовпця з мінімальним елементом.

19.Сформувати одномірний масив, елементи якого визначають кількість додатних елементів у кожному рядку матриці.

20.Замінити на 1 всі додатні елементи під головною діагоналлю, а максимальний з них – на 7.

21.Підрахувати кількість елементів більших за сусідні (справа і зліва) та вивести їх значення з індексами.

22.Знати найближче найменше число, якого немає в матриці.

23.Знайти число, яке повторюється максимальну кількість разів. Якщо таких чисел декілька, то одне з них.

24.Обчислити суму кубів елементів, значення яких більшізаданого числа.

25.Поміняти місцями стовпець з мінімальним елементом масиву та стовпець, мінімальний елемент якого менший заданого числа.

57

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

ЛАБОРАТОРНА РОБОТА № 5 Проектування та відлагодження програм опрацювання рядкових типів даних

МЕТА РОБОТИ: Навчитись проектувати алгоритми та програми опрацювання рядкових типів даних з використанням вивчених операторів (присвоєння, розгалуження, циклу) та вбудованих функцій опрацювання рядків.

ЗАВДАННЯ:

Спроектувати алгоритми та програми розв’язання задач опрацювання рядкових типів даних за варіантами завдань, номери яких визначає викладач.

МЕТОДИЧНІ ВКАЗІВКИ

1.Перед виконанням роботи необхідно пригадати:

логічну структуру програми на мові Turbo Pascal;

правила опису простих типів даних та масивів;

правила запису виразів;

синтаксис основних операторів;

синтаксис опису та правила застосування стандартних (бібліотечних) процедур і функцій.

2.Перед виконанням цієї роботи необхідно вивчити:

правила опису рядкових змінних;

способи ініціалізації рядкових змінних

правила звертання до окремих символів рядка;

допустимі операції над рядковими змінними;

стандартні процедури і функції опрацювання рядків.

3.Перевірка правильності роботи програми здійснюється шляхом аналізу отриманих результатів та порівняння вихідного і результуючих рядків.

ВІДОМОСТІ З ТЕОРІЇ Рядковий тип є одним із найбільш корисних і важливих типів даних і широко використовується

для опрацювання текстів.

Означення 1. Рядок – це послідовність символів кодової таблиці комп’ютера (елементів типу Char) певної довжини.

Рядок - це елементарна конструкція мови Turbo Pascal. Кількість символів в рядку (максимальна довжина рядка) може змінюватись від 0 до 255. Символьний рядок може бути рядковою константою або рядковою змінною. Для опису рядкових змінних в Turbo Pascal введений тип String.

Формат опису:

Type <ім’я_нов_типу> = String [макс_ довжина_ рядка]; Var <ідентифікатор_1> : <ім’я_нов_типу>;

<ідентифікатор_2> : String [макс_довж_ рядка]; Наприклад.

Type line = String[80];

Var R1: String[10]; R2 : String[4]; R3 : line;

Максимальна довжина рядка для змінної R1=10, для R2=4, для R3=80.

В Turbo Pascal визначене поняття рядка змінної довжини, у цьому випадку його опис задається як

Type s = String;

Якщо довжина рядка не вказана, то вона автоматично приймає максимальне значення – 255 байт. Тип String без вказівки довжини сумісний з усіма типами рядків.

Особливістю рядкових змінних є те, що до них можна звертатись як до скалярних змінних, так і як до масивів. У другому випадку рядок трактується як послідовність символів і застосовується конструкція «змінна з індексом», що забезпечує доступ до окремих символів рядка, тобто, до будьякого символу в рядку можна звернутися точно так само, як до компоненти одномірного масиву Array [0..N] Of Char. Наприклад: R1[5].

Рядкові величини можна використовувати в програмі і у вигляді констант. Рядкова константа – це послідовність символів, укладена в апострофи. Рядкові константи можуть входити до складу виразів. Як і числові константи, вони можуть бути описані в розділі опису констант.

58

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Наприклад:

Const name = 'інформатика'; name1: string[6] = 'фізика';

Найважливішою відмінністю рядків від символьного масиву є те, що рядки можуть динамічно змінювати свою довжину. При цьому необхідно пам'ятати, що пам'ять виділяється по максимуму. У пам'яті комп’ютера рядок займає кількість байтів, на одиницю більше його довжини. Найперший байт у рядку має індекс 0 і містить поточну довжину рядка: Ord(st[0]) = Length(st).

Ініціалізація рядкових змінних.

Ініціалізація рядкових змінних здійснюється одним з нижче приведених способів.

1.Введення (зчитування) рядка з клавіатури:

Var St: String; Begin

Read (St);

.....

2.Присвоєння значення рядковій змінній за допомогою оператора присвоювання: St = 'інформатика';

3.Ініціалізація за допомогою типізованих констант:

Type Line1 = String[10];

const St1: Line1='11111111'; St2: String[9] = 'IBM PC/AT'; 4. Ініціалізація за допомогою різновидності процедури

FillChar ( var V; NBytes: Word; C: Char );

Наприклад:

FillChar (St, SizeOf(St), '0');

Операції над рядками.

Для рядків визначені операції присвоювання, злиття (конкатенації) і порівняння.

Операція конкатенація, позначувана символом '+', зміст якої полягає у формуванні нового символьного рядка, значенням якого будуть рядки-операнди, розташовані послідовно один за одним.

Наприклад: St St + '-іспит';

При виведенні St отримаємо рядок: 'інформатика-іспит'.

Для порівняння рядків застосовуються всі операції відношення (<, <=, >, >=, =, <>), при виконанні яких діють наступні правила: більш короткий рядок завжди менший довшого; якщо довжини порівнюваних рядків рівні, то відбувається поелементне порівняння символів цих рядків, починаючи з першого символу. Якщо два порівнювані рядки мають різну довжину, але збігаються аж до останнього символу більше короткого рядка, останній рядок вважається меншим. Два рядки вважаються рівними тільки тоді, коли вони мають однакову довжину і всі їхні символи співпадають.

Рядки можуть бути елементами списку введення-виведення, при цьому записується ім'я рядка без індексу.

Процедури для опрацювання рядків:

59

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)

Модуль Strings забезпечує підтримку нового класу символьних рядків - рядків із завершальним нулем (Nil) і надає користувачу ще 22 функції для опрацювання рядків.

Їх імена, синтаксис та приклади застосування можна переглянути в довідці про модуль Strings

(Help → Contents → Модули → Strings).

Розглянемо приклад програми, яка підраховує кількість символів і слів в довільному рядку символів:

Print to PDF without this message by purchasing novaPDF (http://www.novapdf.com/)