Главная | Обратная связь | Поможем написать вашу работу!

Складні (складені) типи.

Лабораторна робота № 4.

Масиви. Алгоритми сортування та пошуку.

Мета: Складні типи даних. Тип даних масиви. Лінійний та бінарний пошук елемента в масиві. Задачі сортування. Прості алгоритми сортування.

Короткі теоретичні відомості.

Складні (складені) типи.

У мові Pascal реалізований механізм визначення складних (складених) типів даних. Новий тип даних визначається як структурована сукупність даних-компонент стандартних або раніше визначених типів. Оскільки типи компонент можуть також складеними, можна будувати складні ієрархії типів. Методи структурування даних у мові дозволяють будувати масиви, записи, множини і файли. Ці методи називають статичними, оскільки їх опис здійснюється попередньо. Більш складні структури можна створити динамічно - у процесі виконання програми - за допомогою посилання. При вивченні складних типів основна увага приділяється способам конструювання даного і способам доступу до компонентів даного.

2. Регулярний тип. Масиви.

Прикладом складного (регулярного) типу являються масиви. Масив - це найбільш поширена структура даних. Масив - це послідовність однотипних даних, що об’єднана загальним іменем, елементи (компоненти) якої відрізняються (ідентифіцируються) індексами. Індекс елемента вказує місце (номер) елемента в масиві. Кількість елементів масиву фіксовано і визначено в його описі. Доступ до елемента масиву здійснюється обчисленням значення його індексу. Тому масиви - це структури даних з прямим (випадковим) доступом. Всі компоненти масиву є однаково доступними. При визначенні регулярного типу задається і тип компонент, і тип індексів. Саме визначення має вид:

<ім’я типу > = Array [< тип індексу >] of <тип компоненти >;

масив

Приклади:

а) Type LinearTable = Array [0..100] of Integer;

б) type Word = Array [1..20] of Letter;

Letter = ‘a’..’z’;

Order = Array [Letter] of Integer;

в) type Matrix = array [1..N] of array [1..M] of Real;

г) Tenzor = array [-10..10] of array [0..20] of array [0..3] of Real;

У прикладі в) М і N - константи цілого типу. Зверніть увагу на те, що значення типу Matrix - M*N матриці - визначаються як масиви, компонентами яких, в свою чергу, є масиви з дійсних чисел.

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

Type <ім’я> = Array [<Tип> {,<Tип>} ] of <тип компоненти>;

Наприклад:

а) Type matrica = array [1..N,1..M] of real;

б) Type Index1 = -10..10;

Index2 = 0..20;

Index3 = 0..3;

Tenzor = Array [Index1, Index2, Index3] of Real;

в) Type Labyrinth = array [1..100,1..100] of Boolean;

Типи Real і Integer не можуть бути типами індексів!

Компонента змінної регулярного типу - компонента масиву явно позначається іменем змінної, за яким у квадратних дужках слідують індекси; індекси являються виразами типу індексу. Наприклад, Table[1, i+j ], T[2*i+1, (j*j) mod i], S[Monday, Friday]. Зверніть увагу на те, що на відміну від індексних виразів, межі індексів у змінних - масивах повинні бути константами. Значення індексних виразів повинні бути значеннями типу індексу, тобто знаходитись в межах, що визначені межами індексів.

Розглянемо приклад:

Приклад 1. Програма обчислює скалярний добуток вектора V і вектора V`, отриманого з V перестановкою координат у зворотному порядку.

Program ScalarMult;

Const n = 10;

Type Vector = array[1..n] of Real;

Var V: Vector; Summa: Real; i: Integer;

Begin

For i:= 1 to n do begin { блок читання вихідного вектора }

Write(‘Введіть координату вектора: ‘); Readln(V[i]);

end;

Summa:= 0; { блок обчислень}

For i:= 1 to n do

Summa:= Summa + V[i]*V[n-i+1];

write(‘ Результат: ‘, Summa)

End.

Блок обчислень можна оптимізувати за часом. Зазначимо, що Summa обчислюється за формулою:: Summa = V[1]*V[n] + V[2]*V[n-1] +...+ V[2]*V[n-1] + V[1]*V[n]. Отже, її доданки, рівновіддалені від кінців, рівні. Тому кількість повторень циклу можна зменшити вдвоє. При цьому необхідно враховувати парність числа n:

{Program ScalarMult1;}

For i:= 1 to n div 2 do Summa:= Summa + V[i]*V[n-i+1];

If Odd(n)

then Summa:= 2*Summa

else Summa:= 2*(Summa + V[n div 2 + 1];

3. Пошук елемента в масиві.

Задача пошуку елемента в послідовності - одна з важливих задач програмування як з теоретичної, так і практичної точок зору. Ось її формулювання:

Нехай A = {a₁, a₂,...} - послідовність однотипних елементів і b - деякий елемент, який володіє властивістю P. Знайти місце елемента b в послідовності А. Оскільки представлення послідовності в пам’яті може бути здійснено в виді масиву, задачі можуть бути уточнені як задачі пошуку елемента в масиві A:

1.Знайти максимальний елемент масиву;

2.Знайти даний елемент масиву;

3.Знайти k -тий за величиною елемент масиву;

Найбільш прості і часто оптимальні алгоритми основані на послідовному перегляді масиву A з перевіркою властивості P на кожному елементі.

Приклад 2. Пошук мінімального елемента в масиві.

Рrogram MinItem;

Const n = 23;

Var A: Array [1..n] of Real;

Min, Item: Real; Index, i: Integer;

Begin

{Блок введення масиву}

Index:= 1; Min:= A[1];

For i:= 1 to n do begin

Item:= A[i];

If Min > Item

then begin Index:= i; Min:= Item end

end;

{Виведення значень Index, Min}

End.

Змінна Item введена для того, щоб уникнути повторних обчислень індексного виразу в A[i]. Ми пропонуємо читачу розглянути поведінку цього алгоритму і його модифікації у випадку, коли мінімальних елементів у масиві декілька і треба знайти перший, останній, а також всі мінімальні елементи.

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

4. Постановка задачі сортування.

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

Цікаво, що задача сортування є ідеальним прикладом великої кількості різноманітних алгоритмів, розв’язування одної і тої ж задачі. Розглядаючи різні методи сортування, ми побачимо, як зміна алгоритму приводить до нових, більш ефективних у порівнянні з простими, розв’язувань задачі сортування.

Крім цього, послідовності можна представити (реалізувати) в пам’яті різними структурами даних. Як і слід очікувати, ефективність алгоритмів стає дуже залежною від реалізації послідовності.

Нехай дана послідовність елементів a₁, a₂,..., a_n. Елементи цієї послідовності - дані довільного типу, на якому визначено відношення порядку “<<” (менше) таке, що будь-які два різні елементи можна порівняти.

Сортування означає перестановку елементів послідовності a_k1, a_k2,..., a_kn таку, що a_k1 << a_k2 <<... << a_kn.

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

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

Якщо послідовність a₁, a₂,..., a_n реалізована як масив А [1..n], вся вона розміщена в адресованій пам’яті. Тому наряду з вимогами ефективності за часом основна вимога - економне використання пам’яті. Це означає, що алгоритм не повинен використовувати додаткові масиви і пересилки з масиву А в ці масиви.

Постановка задачі сортування в загальному виді передбачає, що існують тільки два типи дій з даними сортованого типу: порівняння двох елементів (x << y) і пересилання елемента (x:= y). Тому зручна міра складності алгоритму сортування масиву А [1..n] за часом - кількість порівнянь C(n) і кількість пересилань M(n).

Прості алгоритми сортування.

Прості алгоритми сортування можна класифікувати як сортування обміном, сортування вибором і сортування вставками.

Сортування обмінами.

Основна дія сортування обмінами - порівняння двох елементів і, якщо результат порівняння від’ємний, перестановка їх місцями:

Якщо при i < j a[i] > a[j] то переставити a[i] і a[j].

В найбільш простому варіанті порівнюються елементи a[j] і a[j+1], що стоять поряд:

Приклад 3.

Program BublSort;

Const n = 100;

Var a: array[1..n] of Real;

i, j: Integer;

TempMem: Real;

Begin

{ Блок введення масиву }

For i:= n - 1 downto 1 do

For j:= 1 to i do

If a[j] > a[j+1]

then begin

TempMem:= a[j+1]; a[j+1]:= a[j]; a[j]:= TempMem end;

{ Блок виведення масиву }

End.

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

Приклад 4.

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

For i:= 1 to n - 1 do begin

k:= Індекс(Min(a[i],..., a[n]));

Переставити a[i], a[k]

end;

Program SelectSort;

Const n = 10;

Var a: array[1..n] of Real;

i, j, MinIndex: Integer;

TempMem: Real;

Begin

{Блок введення масиву}

For i:= 1 to n - 1 do begin

{ пошук мінімального елемента }

MinIndex:= i;

for j:= i + 1 to n do

If a[j] < a[MinIndex] then MinIndex:= j;

{перестановка елементів}

TempMem:= a[MinIndex]; a[MinIndex]:= a[i]; a[i]:= TempMem

end;

{Блок виведення масиву}

End.

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

Ще один простий алгоритм сортування - сортування вставками базується на наступній ідеї: припустимо, що перші k елементи масиву A [1..n] вже упорядковані:

A[1] £ A[2] £... £ A[k], A[k+1],..., A[n]

Знайдемо місце елемента A [k+1] в початковому відрізку A [1],...,A[k] і вставимо елемент на своє місце, отримавши упорядковану послідовність довжини k +1. Оскільки початковий відрізок масиву упорядкований, пошук треба реалізувати як бінарний. Вставці елемента на своє місце повинна передувати процедура зсуву “хвоста” початкового відрізка для звільнення місця.

Program InsSort;

Const n = 100;

Var A: array[1..n] of Integer;

k: Integer;

l, r, i, j: Integer;

b: Integer;

Begin

{Блок читання масиву A}

For k:= 1 to n-1 do begin

b:= A[k+1];

If b < A[k]

then begin

l:= 1; r:= k; {Бінарний пошук}

Repeat

j:= (l + r) div 2;

If b < A[j] then r:= j else l:= j + 1;

until (l = j);{ Зсув “хвоста” масиву на 1 позицію праворуч}

For i:= k downto j do A[i+1]:= A[i];

A[j]:= b; { Пересилання елемента на своє місце}

end

end;

{Блок виведення масиву A}

End.

Оцінимо ефективність алгоритму. Пошук міста елемента A[k+1] потребує, як показано вище, O(log₂k) порівнянь. Тому у гіршому випадку кількість порівнянь С (n) є

C(n) = O(log₂2) +... + O(log₂(n-1)) + O(log₂n) = O(n log₂n)

Зсув “хвоста” на кожному кроку зовнішнього циклу у гіршому випадку потребує k перестановок. Тому у гіршому випадку

M(n) = 1 +... + (n-2) + (n-1) = n*(n-1)/2 = O(n²)

Таким чином, алгоритм сортування вставками значно ефективніший, ніж всі розглянуті раніше алгоритми за числом порівнянь. Однак число перестановок у гіршому випадку також буде значним, як і у самому неефективному алгоритмі - сортуванню простими обмінами.

Хід роботи.

1. Написати в редакторі програми (виконати свій варіант із завдання № 1, 2, 3).

2. Зберегти їх.

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

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

1. Що таке масиви, як з ними працюють?

2. Як описати масив?

3. Як виконується операція пошуку елемента в масиві?

4. Як ви розумієте задачу сортування масивів.

5. Описати прості алгоритми сортування.

6. Дати характеристику алгоритму сортування обмінами.

7. Дати характеристику алгоритму сортування вибором.

8. Дати характеристику алгоритму сортування вставками.

Завдання 1.

1. Дано масив А[1..n]. Скласти програму, яка друкує ті елементи масиву, індекси яких є степенями двійки.

2. Дано масив А[1..n]. Скласти програму підрахунку суми всіх елементів, що знаходяться між елементами А[1] і А[n].

3. Дано масив А[1..n]. Скласти програму підрахунку середніх арифметичних всіх від’ємних та всіх додатніх його чисел.

4. Послідовність з n точок площини задана масивами Х[1..n] та Y[1..n] координат. Скласти програму пошуку точки, що найменш віддалена від початку координат.

5. Дані масиви А[1.. n] та В[1.. n]. Скласти програму побудови масиву С такого, що C_i=max(A_i, B_i).

6. Дані масиви А[1.. n] та В[1.. n]. Скласти програму пошуку елементів А, що входять в В.

7. Дано масив А[1..n]. Скласти програму пошуку номерів всіх його елементів, більших ніж попередні.

8. Дані масиви А[1.. n] та В[1.. n]. Скласти програму побудови масиву С такого, що C_i=min(A_i, B_i).

9. Дано масив А[1..n]. Скласти програму пошуку всіх його елементів, що знаходяться між a та b.

10. Дані масиви А[1..n] та В[1..m]. Скласти програму побудови масиву С, що складається з елементів А, які не входять до В.

11. Дано масив А[1..n]. Скласти програму, яка друкує ті елементи масиву, індекси яких є повними квадратами.

12. Дано масив А[1..n]. Скласти програму пошуку всіх його елементів, менших за всі його попередні.

13. Дано масив А[1.. 2n+1]. Скласти програму пошуку середнього по величині елементу в масиві А.

14. Дано масив А[1..n]. Скласти програму що знаходить, скільки разів в масиві зустрічається максимальне по величині число.

15. Дано масив А[1..n]. Скласти програму яка в масиві всі додатні числа збільшує на 2, а всі від’ємні числа зменшує на 2.

16. Дано масив А[1..n]. Скласти програму пошуку кількості елементів масиву які кратні 3 і некратні 5.

17. Дано масив А[1..n]. Скласти програму побудови масиву В[1..n], елементи якого вдвічі більші за елементи масиву А.

18. Дані впорядковані по зростанню масиви А[1..n] та В[1..m]. Скласти програму, яка з цих двох масивів робить третій С, також впорядкований в зростаючому порядку.

19. Дано масив А[1..n]. Скласти програму підрахування числа різних елементів масиву.

20. Дано масив А[1..n], в якому кожен елемент дорівнює 0, 1, або 2. Скласти програму що розміщує елементи масиву в зростаючому порядку.

21. Дано масив А[1..n]. Знайти кількість різних чисел серед елементів цього масиву.

22. Дано масив A[1..n]. Знайти в цьому масиві найбільшу за кількістю елементів зростаючу підпослідовність елементів, що йдуть підряд.

Завдання 2.

1. Дано масив А[1.. n, 1.. n]. Скласти програму пошуку всіх індексів елементів [i, j] таких, що A_ij=A_ji.

2. Дано масив А[1..n, 1..m]. Скласти програму пошуку всіх елементів масиву А, що менші ніж усі сусідні.

3. Дано масив А[1..n, 1..m]. Скласти програму пошуку всіх елементів масиву А мінімальних у свому рядку.

4. Дано масив А[1..n, 1..m]. Скласти програму пошуку всіх елементів масиву А максимальних у соєму стовбці.

5. Дано масив А[1..n, 1..m]. Скласти програму пошуку сідлової точки (максимальної в рядку і мінімальної в стовбці).

6. Дані масиви А[1..n] та В[1..m]. Скласти програму побудови масиву С, що складається з елементів масиву А, які співпадають з елементами В.

7. Дано масив А[1..n, 1..n]. Скласти програму пошуку всіх його елементів менших за суму діагональних елементів.

8. Дано масив А[1..n, 1..n]. Скласти програму пошуку всіх його елементів більших за суму елементів, що знаходяться на побічній діагоналі.

9. Дано масив А[1..n, 1..m]. Скласти програму пошуку всіх його елементів, що знаходяться між а та b.

10. Дано масив А[1..n, 1..m]. Скласти програму пошуку стовпця, сума квадратів елементів якого мінімальна.

11. Дано масив А[1..18, 1.. n] та натуральне число n. Скласти програму пошуку найбільшого по модулю елементу масиву, а також індексу цього елементу.

12. Дано масив А[1..n, 1..m]. Скласти програму пошуку середнього арифметичного найбільшого та найменшого значень елементів масиву.

13. Дано масив А[1.. n, 1.. m]. Скласти програму пошуку середнього арифметичного кожного зі стовбців.

14. Дано масив А[1..n, 1..m]. Скласти програму пошуку рядка, сума квадратів елементів якого максимальна.

15. Дано масив А[1..n, 1.. m]. В кожному рядку вибирається мінімальне число, а потім серед цих чисел вибирається максимальне. Вивести на екран номер рядка в якому знаходиться це число.

16. Дано масив А[1..n, 1.. 9]. Знайти середнє арифметичне кожного із стовпців, що мають парні номери.

17. Дано масив А[1..n, 1..m]. Скласти програму пошуку сідлової точки (максимальної в рядку і мінімальної в стовбці).

18. Дано масив А[1..n, 1.. m]. Відомо, що серед його елементів два і тільки два рівні між собою. Скласти програму яка знаходить індекси цих елементів.

19. Дано масив А[1..n, 1..m]. У даному масиві поміняти місцями рядок, що містить елемент з найбільшим значенням з рядком, що містить елемент з найменшим значенням. Передбачається, що ці елементи єдині.

20. Дано масив А[1..n, 1..m]. Отримати масив В[1.. n], де В _k – це найбільше із значень елементів к- го рядка.

21. Дано масив А[1..n, 1..m]. Отримати масив В[1.. n], де В _k – добуток квадратів тих елементів к- го рядка, модулі яких належать відрізку [1, 1,5].

22. Дано масив А[1..n, 1..n]. Знайти номери рядків, всі елементи яких парні.

Завдання 3. За допомогою програмного комплекса «Відеоінтерпретатор алгоритмів пошуку та сортування» завантажити з бібліотеки алгоритмів наступні алгоритми та прослідкувати їх виконання.

Пошук мінімального елементу в масиві.
Пошук елемента в упорядкованому масиві.
Злиття двох упорядкованих масивів.
Упорядкування «двохкольорового» масиву.
Сортування масиву обмінами за зростанням.
Сортування масиву вибором за спаданням.
Сортування масиву вставками.

Завдання 4. Скласти алгоритми за наступними завданнями та за допомогою програмного комплекса «Відеоінтерпретатор алгоритмів пошуку та сортування» перевірити правильність їх написання:

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