C _Учебник_МОНУ

Згідно до рисунка й таблиці, якщо автомат перебуває у стані А, за елементів 1, 2 він залишиться у тому ж стані, а за елемента 0 він перейде до стану В.

Текст функції та програми для командної кно пки:

AnsiString Automat2(AnsiString s)

{enum conditions {A,B,C}; conditions sit=A; sit=A;

for(int i=1; i<=s.Length();i++)

switch (sit)

{ case A: { if(s[i]=='0') { sit=B; s[i]='1'; } else

if(s[i]=='2') s[i]='0'; break;

}

case B: { if(s[i]=='1') s[i]='0'; else

{sit=A;

if(s[i]=='0') s[i]='1';

}

break;

}

}

return s;

}

void __fastcall TForm1::Button1Click(TObject *Sender)

{AnsiString s=Edit1->Text; Edit2->Text= Automat2(s);

}

void __fastcall TForm1::Edit1KeyPress(TObject *Sender, char &Key) { // Користувач не зможе ввести символ вхідного алфавіту відмінний від 0, 1 чи 2

if(Key<'0' || Key>'2') Key=0;

}

13.7.3 Асинхронні автомати

Автомат називається асинхронним, якщо вхідна послідовність може бути перетворена ним на послідовність іншої довжини, тобто один символ може бути перетворено у довільну кількість символів.

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

Текст функції та програми для командної кно пки:

AnsiString Assinhr1(AnsiString S)

{enum conditions {A, B}; // Перераховний тип даних conditions sit=A;

{case A:

{if(S[1]=='0'){T=T+"11"; sit=B;} else

if(S[1]=='1'){T=T+"101"; sit=B;} else T=T+"2";

}// end case A case B:

{if(S[1]=='0') T=T+"0"; else

{if(S[1]=='1'){T=T+"01"; sit=A;} else

if(S.Length()>1)

{String sub=S.SubString(1,2); if(sub=="20") T=T+"00"; else if(sub=="21")T=T+"11"; else

if(sub=="22") T=T+"2"; sit=A;

}}

if((S[1]=='2')&&(S.Length()>=1))S.Delete(1,2); else S.Delete(1,1);

break;

}// end case B

}// switch

}// while

return T;

}

void __fastcall TForm1::BitBtn1Click(TObject *Sender)

{AnsiString s=Edit1->Text; Edit2->Text=Assinhr1(s);

}

Слід зазначити, що задані в такий спосіб асинхронні автомати у певному розумінні не є строго коректними, оскільки автомат не завжди має можливість за вхідною послідовністю однозначно видати вихідну послідовність. Наприклад, як було зазначено вище, якщо в нашому автоматі вхідна послідовність є S="02", то перший символ видасть вихідну послідовність "11", а другий – не видасть жодного результату. Такі автомати є частково визначеними. Але вони є невизначені лише на малих “залишках” вхідної послідовності. Природно, що автомати використовують на текстах досить

{ T=T+"22"; sit=A;} break;

} // end case B }// switch

return T;

}

//------------------------------------------------------------

void __fastcall TForm1::BitBtn1Click(TObject *Sender)

{String s=Edit1->Text; Edit2->Text= Assinhr2(s);

}

//------------------------------------------------------------

void __fastcall TForm1::Edit1KeyPress(TObject *Sender, char &Key) { if(Key<'0' || Key>'2') Key=0;

}

13.7.4 Композиція автоматів

Вище було розглянуто приклади роботи різних автоматів. Але теорія автоматів здебільшого має справу не з одним автоматом, а з множиною автоматів. Наприклад, для заданих автоматів M та K можна утворити новий автомат N, який є результатом композиції цих двох автоматів. X, Y – відповідно вхідний і вихідний алфавіти автомата M; Y, Z – вхідний і вихідний алфавіти автомата K. Для автомата N, який є композицією автоматів M та K, будуть виконуватись такі перетворення. Спочатку автомат N перетворить вхідний рядок алфавіту Х, як це робить автомат M, потім автомат N перетворить дістаний текст алфавіту Y на текст алфавіту Z, як це робить автомат K. Якщо вхідний і вихідний алфавіти автомату M збігаються (X=Y), то можна розглянути композицію автомата M на самого себе. Тоді N=M2. Аналогічно утворюються інші степені автомата. Комбінуючи дії автоматів M та K, можна утворити нескінченну кількість нових автоматів.

Приклад 13.15 Нехай задано два асинхронні автомати K та M з алфавітами X=Y={0, 1, 2} і двома станами А та В (див. приклади 13.13 та 13.14). Створити новий автомат N як композицію автоматів K та M. Порядок використання автоматів у композиції (зліва-направо) задано послідовністю елементів алфавіту {K, M}.

Розв‟язок. У запропонованій програмі організовано два рядки: S – вхідна послідовність символів множини {'0', '1', '2'}; T – послідовність дії автоматів K та M. Результатом є перетворений рядок вихідного алфавіту множини символів {'0', '1', '2'}, який отримується після дії композиції автоматів.

Програма використовуватиме функції Assinhr1() й Assinhr2() з прикладів 13.13 та 13.14.

Питання та завдання для самоконтролю

1)Дайте означення лінійного списку.

2)Дайте означення циклічного списку.

3)Які є різновиди списків?

4)Що зберігає елемент списку?

5)Наведіть оголошення елемента лінійного однозв‟язного списку, який містить дійсні числа.

6)Як звернутися до другого елемента списку, оголошеного у завданні 5?

7)Елемент якого списку “знає”, де розташовано попередній і наступний елементи? Наведіть оголошення елемента такого списку.

8)Як звернутися до передостаннього елемента списку, оголошеного у завданні 5?

9)Нехай у програмі список оголошено в такий спосіб:

struct List { char c; List n; } first;

Цей список містить такі значення: 'd', 'y', '5', '*', '2', 'h'. Поясніть значення наступних виразів:

а) first->n->c; б) first->n->n; в) first->n->n->c;

10) Наведіть оголошення елемента однозв‟язного списку, який “знає”, де розташовано попередній елемент.

11) В який спосіб можна вилучити з двонапрямленого списку елемент із заданим номером.

12) Дайте визначення стека і черги.

13) Які дії можна виконувати при роботі зі стеком і чергою?

14) Які вказівники треба використовувати для роботи зі стеком і чергою? 15) Яким чином долучити та вилучити перший, останній і довільний еле-

менти лінійного списку?

16) Які елементи заборонено вилучати з черги?

17) Які елементи заборонено вилучати зі стека?

18) Чим дерево відрізняється від лінійних списків?

19) Дайте визначення листа та кореня дерева.

20) У чому полягає особливість бінарних дерев?

21) Як долучаються вузли до дерева?

22) Як вилучаються вузли з дерева?

23) В якому дереві вузли не містять більше двох посилань? 24) Як називається вузол дерева, що не має предків?

25) Як називається вузол дерева, що не має нащадків?

26) Зобразити бінарне дерево, обхід якого зліва направо формує таку пос-

лідовність значень: 27, 11, 19, 18, 49, 32, 53, 67, 72, 60, 81, 97, 91, 98.

27) Дайте визначення автомата.

28) Чим відрізняється синхронний автомат від асинхронного?

29)Чи можуть збігатися вхідний і вихідний алфавіти автомата?

30)Чи може асинхронний автомат перетворювати послідовність елементів у послідовність тої самої довжини?

Розділ 14

Об’єктно-орієнтоване програмування

14.1 Модульне й об’єктно-орієнтоване програмування

Об‟єктно-орієнтований підхід до програмування є пріоритетним при створюванні переважної більшості програмних проектів.

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

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

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

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

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

Введення поняття класу є розвитком ідей модульності. У класі поєднуються структури даних і функції їхнього опрацювання. Класи дуже схожі на структури, які було розглянуто у підрозд. 11.2. Ідея класів є підґрунтям об‟єктно-орієнтованого програмування (ООП). Програми на C++ широко використовують класи.

Клас є типом даних, який визначає користувач. У класі задаються властивості та характер певного предмета чи процесу у вигляді полів даних (аналогічно до структури) і функцій для роботи з ними. Наприклад, клас телефон може мати поля даних: номер, тип телефону (кнопковий чи дисковий) і функції роботи з телефоном: дзвінок, набирання номера, з‟єднання з абонентом тощо. Групування даних про об‟єкт та кодування їх однією змінною спрощує процес програмування та збільшує можливість повторного використання коду.

Суттєвою властивістю класу є те, що деталі його реалізації приховано від користувачів класу за інтерфейсом. Це захищає їх від випадкових змінювань. Інтерфейсом класу є заголовки його методів.

Ідея класів відображає будову об‟єктів реального світу. Адже кожен об‟єкт чи процес має набір певних характеристик чи відмінностей, інакше кажучи, певні властивості й поведінку. Так характеристиками автомобіля є марка, колір, максимальна швидкість, потужність двигуна тощо; характеристиками посилювача є частотний діапазон, потужність, коефіцієнт нелінійних перекручувань тощо. Функціональні можливості об‟єктів теж відрізняються: автомобіль може їздити, посилювач – підвищувати рівень сигналів. А користуватись об‟єктами можна, не знаючи їхньої внутрішньої будови. Наприклад, керувати автомобілем можна, не маючи жодного уявлення про будову його двигуна чи будь-яких інших його частин.

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

Основними поняттями, на яких базується ООП, є:

інкапсуляція;

успадкування;

поліморфізм.

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

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

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

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

Існує три групи мов програмування, які пов‟язані з поняттям клас: об‟єктно-орієнтовані, об‟єктні, об‟єктно-базовані. Об‟єктно-орієнтовані мови у повному обсязі підтримують парадигму ООП: інкапсуляцію, успадкування та поліморфізм. Типовими представниками таких мов є C++, Java, C#. До об‟єктних мов відносять мови програмування, які підтримують тільки інкапсуляцію та дозволяють створювати об‟єкти; це мови Visual Basic (до шостої версії включно) та Ada. До об‟єктно-базованих мов програмування відносять мови, які можуть використовувати існуючі об‟єкти, але не мають механізму створення об‟єктів користувача. Мова JavaScript є об‟єктно-базованою мовою програ-