Зубенко, Омельчук - Програмування. Поглиблений курс

Розділ ІІІ. МОВИ ПРОГРАМУВАННЯ С ТА С++

int x fun(i); //виклик функції

}

catch(CTestError e) {

//виклик функції обробки виняткової ситуації cout<<e.showReason<<endl;

}

catch(int k) {

//виклик функції обробки виняткової ситуації cout<<"ERROR"<<k<<endl;

}

■

*Література для CР: мова С++ – [57, 64, 70, 73, 96, 98, 102, 124].

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

1.Що таке шаблони функцій і як їх використовувати?

2.Що таке вбудований, зовнішній і перевантажений шаблони?

3.Що таке конкретизація (інстанціювання) шаблону?

4.Описати стандартну бібліотеку шаблонів STL.

5.Які особливості зведення типів у мові C++?

6.Які особливості примусового зведення типів зі специфікаторами: static-cast, dynamic-cast, const-cast та reinterpret-cast?

7.Що таке знижувальне зведення типу?

8.Яке призначення дружніх класів, методів і функцій?

9.Що таке перевантаження операцій?

10.Які операції можуть бути перевантажені?

11.Що таке виняткова ситуація?

12.Що таке виключення та його обробка?

13.Охарактеризувати конструкції throw, catch та try.

14.Написати програму, що задає як шаблон функції знахо- дження мінімуму, максимуму й суми й використовує ці ме- тоди для аргументів різних типів.

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

•каталог книг у бібліотеці;

•список студентів у групі;

•список товарів у магазині;

•список клієнтів банку;

•телефонний довідник.

16.Подати раціональні числа у вигляді класу з атрибутами цілих типів, що задають чисельник і знаменник. Реалізувати за до-

471

ПРОГРАМУВАННЯ

помогою перевантаження відповідних операторів основні арифметичні операції над раціональними числами й відно- шення на них.

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

18.У калькуляторі із вправи 22, підрозд. 3.11 передбачити детектор арифметичних помилок (ділення на 0 тощо), реалізувавши його за допомогою блока try-catch.

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

20.Для наведених функцій виконати перевірку параметрів, що передаються, і згенерувати виключення у випадку помилки:

• обчислення кореня лінійного рівняння ax +b = 0 ;

•обчислення периметра трикутника;

•переведення годин і хвилин у секунди;

•обчислення кореня квадратного рівняння ax2 +bx +c = 0 ;

•обчислення суми геометричної прогресії Sn =(a0 −anr)/(1−r).

472

ПРОГРАМУВАННЯ

у програмуванні. Методи їхнього розв'язання застосовують і для сор- тування загальних послідовностей.

Сформулюємо загальну задачу сортування. Нехай A – довільна базо- ва множина, а (K,≤) – довільна лінійно впорядкована множина елемен-

тів, які називаються ключами. Пов'яжемо з кожним базовим елементом певний ключ, і нехай f : A → K означає дану відповідність. Таким чи-

ном, f (a) є ключем елемента a A . Зазвичай базові елементи мають

певну структуру і ключами стають значення певного фіксованого еле- мента в ній. Типовим прикладом структурованих базових елементів є вектори фіксованої довжини з різнотипними компонентами. Як ми вже знаємо, у програмуванні подібні вектори називаються структурами, їхні координати – полями, а кортежі таких однотипних структур – табли- цями. У таблицях структури називаються рядками. За ключі рядків бе- руть значення певного фіксованого поля. Порядок на ключах елементів природно переноситься й на самі елементи, а саме: для довільних a,b A :a ≤ b f (a) ≤ f (b). Кортеж базових елементів (a1,...an ) назива-

ється відсортованим, якщо 1 ≤ i < n ai ≤ ai +1 .

Наприклад, є таблиця рядків про студентів факультету, що містить інформацію про прізвище, ім'я та по-батькові (ПІБ) студента, рік на- родження, курс тощо, яку необхідно відсортувати за курсом. Тоді ключем буде курс, а решта полів міститиме супутню інформацію.

Задача сортування. Задано довільний кортеж базових елементів (a1,...,an ). Необхідно знайти таку його перестановку (a1′,...,an′ ), після

якої їхні ключі f (ai′) розмістяться в неспадному порядку:

1 ≤ i < n f (ai′)≤ f (ai′+1 ).

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

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

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

(a1,...,an ) і ключ k K . Необхідно знайти всі або один з елементів ai в кортежі з ключем k , що задовольняє певну умову.

474

Розділ IV. АЛГОРИТМИ

4.1.1. ПОСЛІДОВНИЙ ПОШУК У МАСИВІ

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

що f (ai ) =k . Якщо достеменно невідомо, чи є такий елемент у масиві, то

необхідно стежити за тим, щоб пошук не вийшов за межі масиву. Приклад 4.1. Лінійний пошук:

Лістинг. s_search.c

/*послідовний пошук у символьному масиві a[] довжиною n*/

/*a – масив, в якому ведеться пошук, n – кількість елементів масиву, k – ключ для пошуку*/

int sequential_search(char *a, int n, char k)

{

register int i; for(i=0; t<n; ++t) if(k==a[i]) return i;

return -1; /*ключ не знайдено*/

}

■

Кількість порівнянь у алгоритмі лінійного пошуку становить O(n), де n – кількість елементів у масиві. При цьому максимальна кількість порівнянь збігається із n (коли елемент відсутній у масиві або розта- шований на останньому місці).

4.1.2. БІНАРНИЙ ПОШУК

Для впорядкованих масивів існують значно ефективніші алгорит- ми пошуку, але й для таких масивів можна застосовувати алгоритми послідовного пошуку. Бінарний пошук (інші назви – дихотомічний, логарифмічний, пошук діленням навпіл) полягає в тому, що ключ k порівнюється з ключем середнього елемента масиву. Якщо ці значен- ня рівні, то шуканий елемент знайдено, в іншому випадку пошук продовжується в одній із двох половин списку (якщо ключ k більше ключа середнього елемента – то в правій половині, інакше – у лівій).

Для знаходження елемента бінарним пошуком необхідна кількість порівнянь становить O(log2 n ), де n – кількість елементів у масиві.

475

ПРОГРАМУВАННЯ

Приклад 4.2. Бінарний пошук:

Лістинг. b_search.c

/*бінарний пошук у символьному масиві a[] довжиною n*/

/*a – масив, в якому ведеться пошук, n – кількість елементів масиву, k – ключ для пошуку*/

int binary_search(char *a, int n, char k)

{

/*low і high – перший і останній індекси поточного підмасиву, в якому ведеться пошук, mid – його середина*/

int low, high, mid; low=0; high=n-1; while(low<=high) {

mid=(low+high)/2; if(k<a[mid]) high=mid-1;

else if(k>a[mid]) low=mid+1;

else return mid; /*ключ знайдено*/

}

return -1;

}

■

4.1.3. БУЛЬБАШКОВЕ СОРТУВАННЯ

Серед усіх методів сортування масивів найвідомішим і найпрості- шим для реалізації й розуміння є обмінний алгоритм бульбашкового сортування (англ. – bubble sort).

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

Приклад 4.3. Бульбашкове сортування:

Лістинг. bubble.c

/*Бульбашкове сортування масиву a[] довжиною n*/ void bubbleSort(float a[], int n)

{

char is=1; int m=0;

476

Розділ IV. АЛГОРИТМИ

int i; float c;

while(is)

{is=0;

for (i=m+1; i<=n; i++) if (a[i]<a[i-1])

{ /*обмін елементами*/ c=a[i];

a[i]=a[i-1]; a[i-1]=c; is=1;

}

}

}

Сортування методом бульбашки для вхідного масиву [4.0, 5.0, 3.0, 10.0, 1.0]:

■

У найкращому випадку (масив уже відсортований) алгоритм вима- гає n −1 порівнянь і переміщень елементів. При першому проходжен- ні здійснюється n −1 порівнянь, при другому – n − 2 , на кожному на- ступному кроці кількість порівнянь зменшується на 1. Складність у найгіршому випадку задається формулою

Отже, алгоритм бульбашкового сортування ефективний лише для не- великих масивів, і його складність сягає O(n2 ) порівнянь і перемі- щень елементів.

4.1.4. СОРТУВАННЯ ВСТАВЛЕННЯМ

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

477

ПРОГРАМУВАННЯ

ваному початку масиву доти, доки набір вхідних даних не буде виче- рпано. Вибір чергового елемента зі вхідного підмасиву – довільний.

Приклад 4.4. Сортування вставленням:

Лістинг. insert.c

/*сортування вставленням масиву a довжиною n*/

void insertSort (float a[], int n)

{

int i, j; float value;

for (i=1; i<n; i++) { value=a[i];

for (j=i-1; (j>=0) && (a[j]>value); j--) { a[j+1]=a[j];

}

a[j+1]=value;

}

}

Тут обидва списки, вхідний і шуканий, розміщуються в масиві a, причому початковий список займає частину a з індексами від i до n, а вихідний – від 0 до i-1.

Для вхідного масиву [4.0, 5.0, 3.0, 10.0, 1.0] при сортуванні мето- дом вставлень маємо:

■

Розглянемо найгірший випадок застосування алгоритму сортуван- ня вставленням. Першим вставляється другий елемент списку. Він порівнюється з одним елементом. Кожний наступний елемент, що вставляється, порівнюється з усіма попередньо вставленими. Отже, i -й елемент, що вставляється, порівнюється з i попередніми, і цей процес повторюється n −1 разів. Складність цього алгоритму визна-

478

Розділ IV. АЛГОРИТМИ

4.1.5. СОРТУВАННЯ ЗЛИТТЯМ

Увсіх вищерозглянутих алгоритмів сортування є суттєвий недолік

–час їхнього виконання має порядок O(n2 ). Потрібно шукати кращі

алгоритми.

Попередній алгоритм діяв за принципом: додаємо елементи один за одним до відсортованої частини масиву. Застосуємо інший підхід

– "розділяй і володій", і побудуємо за його допомогою значно швид- ший алгоритм.

Нагадаємо, що ідея принципу "розділяй і володій" (див. підрозд. 2.2.2) полягає в: 1) розбитті задачі на менші підзадачі; 2) розв'язанні вибраних підзадач; 3) розв'язанні шляхом комбінації отриманих ре- зультатів загальної задачі.

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

Приклад 4.5. Сортування злиттям:

Лістинг. mergeSort.c

/*злиття двох відсортованих підмасивів масиву v з індексами від left до mid і від mid+1 до right у впорядкований глобальний масив b і копіювання його назад у v*/

void merge(float v[], int left, int mid, int right)

{

int i, m1, m2; i=m1=left; m2=mid+1;

float b[right-left+1];

while (m1<=mid && m2<=right) if (v[m1]<v[m2])

b[i++]=v[m1++]; else b[i++]=v[m2++];

while (m1<=mid) b[i++]=v[m1++]; while (m2<=right) b[i++]=v[m2++];

for (i=left; i<=right; i++) v[i]=b[i];

}

479

ПРОГРАМУВАННЯ

/*упорядкування за зростанням ділянки масиву v від left до right*/

/*масив v, left – початок ділянки, що сортується, right – кінець ділянки, що сортується, mid – середина*/

void mergeSort(float v[], int left, int right, int mid)

{

/*список порожній*/ if(left==right) return;

/*список складається з одного елемента – відсортований*/ if(left==right-1) return;

mergeSort(v, left, mid, (left+mid)/2); /*перша половина*/ mergeSort(v, mid+1, right, (mid+right+1)/2); /*друга половина*/

/*злиття двох відсортованих фрагментів масиву v (від left до mid) та (від mid+1 до right)*/

merge(v, left, mid, right);

}

Сортування вхідного масиву [4.0, 5.0, 3.0, 10.0, 1.0] методом злиття:

відсортована послідовність

злиття

■

Складність алгоритму оцінюється як O(n log2 n ), оскільки за одне про- ходження виконується n порівнянь, а всього потрібно logn проходжень. Для великих n сортування злиттям значно ефективніше за сортування вставленням чи методом бульбашки, які вимагають часу O(n2 ).

Розглянемо ще один відомий метод сортування, що вимагає

O(n log2 n ) часу – швидке сортування.

480