Контрольні питання

1. Дайте визначення поняття масива.

2. Які оголошується одновимірний масив? Наведіть приклади.

3. Як визначають кількість елементів у масиві? Наведіть приклади.

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

ІНСТРУКЦІЙНА КАРТКА №6

до навчальної практики

з дисципліни «Алгоритми та структури даних»

Тема. Обробка масивів. Двовимірні масиви.

Мета: навчитися розробляти алгоритми та програми обробки масивів даних: оволодіти основними методами обробки масивів (пошук, впорядкування, нагромадження сум залежно від умови, формування нових масивів).

Матеріально-технічне оснащення робочого місця:

1. Інструкційна картка;

2. ПК.

Короткі теоретичні відомості з теоретичної частини роботи.

Масив – це поіменована сукупність однорідних (однотипних) значень.

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

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

Кожен масив визначається:

1. іменем (ідентифікатором);

2. типом його елементів;

3. вимірністю (кількістю індексів);

4. мінімальним значенням кожного індексу.

Описати масив можна у розділі опису типів type, у розділі констант const, або у розділі оголошення змінних var.

Мовою Паскаль двовимірний масив описується аналогічно, причому (зверніть увагу) значення індексів можуть бути не тільки натуральними:

а) var

M:array [1..10, - 5..-1] of real;

б) const n=10; k= - 5;

var

M:array [1..n, k.. – 1] of real;

в) const n=10; k= - 5;

type arr=array [1..10, k.. – 1] of real;

var M: arr;

Як і в попередньому випадку, всі три методи описують один і той самий за розміром двовимірний масив (10 рядків, 5 стовпчиків) дійсних чисел.

Формат команди алгоритмічною мовою:

тип ТАБ ім’я масиву [ тип індексу рядка, тип індексу стовпця ]

Як і для одновимірного масиву, ми будемо розглядати < тип індексу> діапазон: m1:n1, m2:n2, де m1 – початковий порядковий номер рядка, а n1 – кінцевий, m2 – початковий порядковий номер стовпчика, а n2 – кінцевий.

Наприклад: дійсн таб B[1:10, 1:12], літ таб C[1:3, 1:3], ціл таб A[1:m, 1:n].

Кількість елементів у двовимірному масиві обчислюється за формулою:

(n1 – m1+1)*(n2 – m2+1).

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

У роботі з масивами необхідно використовувати цикли. Для доступу до елементів двовимірного масиву – два: один цикл по рядках, а інший по стовпчиках.

Можливі два методи заповнення масиву:

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

Const n=10; k=8; var A:array [1..n, 1..k] of real; i, j: word; begin for i:=1 to n do for j:=1 to k do begin write(‘ Введіть значення ‘); readln(A[I,j]); end; end.

Const n=10; k=8; var A:array[1..n, 1..k] integer; i, j: word; begin for i:=1 to n do begin for j:=1 to k do begin A[i, j]:=random(100); write(A[i, j]:8:2); end; end; writeln; end.

Зверніть увагу, що для другого випадку після заповнення значення елементу відразу виводиться на екран для контролю: для двовимірного – прямокутною матрицею.

Сортування масивів. При розв’язанні задачі сортування звичайно висувається вимога мінімального використовування додаткової пам’яті, з якої випливає недопустимість застосування додаткових (допоміжних) масивів.

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

Всі методи сортування можна поділити на дві великі групи: прямі методи сортування та поліпшені методи сортування.

Прямі методи сортування по принципу, який лежить в основі методу, в свою чергу поділяються на три підгрупи:

- сортування вставкою (включенням).

- сортування вибором (виділенням).

- сортування обміном (сортування (‘бульбашки’).

Поліпшені методи сортування грунтуються на тих же самих принципах, що і прямі, але використовують деякі оригінальні ідеї для прискорення процесу сортування. Прямі методи на практиці використовуються дуже рідко, бо мають відносно низьку швидкодію. Однак вони добре показують суть заснованих на них поліпшених методів. Окрім того, у деяких випадках (як правило, при невеликій довжині масиву і(або) особливому вихідному розташуванню елементів масиву) деякі із прямих методів можуть навіть перевершити поліпшені методи.

Сортування вставкою. Масив поділяється на дві частини: відсортовану і невідсортовану. Елементи із невідсортованої частини почергово вибираються та вставляються у відсортовану частину так, щоб не порушити в ній упорядкованість елементів. На початку роботи алгоритму у якості відсортованої частини масиву приймають тільки один перший елемент, а у якості невідсортованої частини – всі інші елементи.

Таким чином, алгоритм буде складатися із (n-1)-го проходу (n – розмірність масиву), кожний з яких буде включати чотири дії:

- взяття чергового і-того невідсортованого елементу та зберігання його у допоміжній змінній;

- пошук позиції j у відсортованій частині масиву, в якій присутність взятого елементу не порушує упорядкованості елементів;

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

- вставка взятого елементу у знайдену j-ту позицію.

Для того, щоб реалізувати даний метод, можна запропонувати кілька алгоритмів, які будуть відрізнятися способом пошуку позиції вставки.

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

Сортування обміном. Зліва направо почергово, порівнюємо два сусідніх елемента, і якщо їх взаєморозташування не відповідає заданій умові упорядкованості, то вони змінюються містами. Після одного такого обходу на останній n-тій позиції масиву буде стояти найбільший або найменший елемент (в залежності від умови упорядкування), тобто ‘спливає’ перша ’бульбашка’. Кожний наступний обхід обмінів виконується тільки до вже упорядкованої частини масиву.