ЗМІСТ
1 Поняття алгоритму і його характеристики.
2 Форми подання алгоритмів.
3 Основні алгоритмічні структури.
4. Структурне програмування.
5. Подієво-орієнтоване програмування
6. Об'єктно-орієнтоване програмування.
1 Поняття алгоритму і його характеристики.
2 Форми подання алгоритмів.
3 Основні алгоритмічні структури.
4. Структурне програмування.
5. Подієво-орієнтоване програмування
6. Об'єктно-орієнтоване програмування.
1. Поняття алгоритму і його характеристики
Підготовка завдання для вирішення на ЕОМ складається з кількох етапів:
формулювання умови задачі;
вибір методу її рішення (наприклад, чисельного для математичних задач);
розробка схеми алгоритму;
складання програми на алгоритмічній мові.
Алгоритм - це система правил, що описує послідовність дій, які необхідно виконати, щоб вирішити завдання [3]. Алгоритм - деяка послідовність приписів (правил), однозначно визначають процес перетворення вихідних і проміжних даних в результат рішення задачі.
Поняття алгоритму в інформатиці є фундаментальним, таким, яким є поняття точки, прямої і площини в геометрії, множини - в математиці, простору і часу - у фізиці, речовини - в хімії. Як і для будь-якого фундаментального поняття, для алгоритму неможливо дати абсолютно строгого визначення. Тому формулювання, наведені вище, лише наближено описують алгоритм.
Основні характеристики алгоритму: дискретність, визначеність, результативність, масовість.
Дискретність означає, що виконання алгоритму розбивається на послідовність закінчених дій - кроків. Кожна дія має бути завершене виконавцем перш, ніж він перейде до виконання наступного. Значення величин у кожному кроці алгоритму виходять за певними правилами із значення величин, визначених на попередньому кроці.
Під визначеністю розуміється та обставина, що кожне правило алгоритму настільки чітко і однозначно, що значення величин, що отримуються на будь-якому кроці, однозначно визначаються значеннями величин, отриманими на попередньому кроці, і при цьому точно відомо, який крок буде виконаний таким.
Результативність (або кінцівку) алгоритму припускає, що його виконання зводиться до виконання кінцевого числа дій і завжди призводить до деякого результату. У якості одного з можливих результатів є встановлення того факту, що задача не має рішень.
Під масовістю розуміється, що алгоритм розв'язання задачі розробляється в загальному вигляді так, щоб його можна було застосувати для цілого класу задач, що розрізняються лише наборами вихідних даних. У цю властивість і укладена основна практична цінність алгоритму.
Підготовка завдання для вирішення на ЕОМ складається з кількох етапів:
формулювання умови задачі;
вибір методу її рішення (наприклад, чисельного для математичних задач);
розробка схеми алгоритму;
складання програми на алгоритмічній мові.
Алгоритм - це система правил, що описує послідовність дій, які необхідно виконати, щоб вирішити завдання [3]. Алгоритм - деяка послідовність приписів (правил), однозначно визначають процес перетворення вихідних і проміжних даних в результат рішення задачі.
Поняття алгоритму в інформатиці є фундаментальним, таким, яким є поняття точки, прямої і площини в геометрії, множини - в математиці, простору і часу - у фізиці, речовини - в хімії. Як і для будь-якого фундаментального поняття, для алгоритму неможливо дати абсолютно строгого визначення. Тому формулювання, наведені вище, лише наближено описують алгоритм.
Основні характеристики алгоритму: дискретність, визначеність, результативність, масовість.
Дискретність означає, що виконання алгоритму розбивається на послідовність закінчених дій - кроків. Кожна дія має бути завершене виконавцем перш, ніж він перейде до виконання наступного. Значення величин у кожному кроці алгоритму виходять за певними правилами із значення величин, визначених на попередньому кроці.
Під визначеністю розуміється та обставина, що кожне правило алгоритму настільки чітко і однозначно, що значення величин, що отримуються на будь-якому кроці, однозначно визначаються значеннями величин, отриманими на попередньому кроці, і при цьому точно відомо, який крок буде виконаний таким.
Результативність (або кінцівку) алгоритму припускає, що його виконання зводиться до виконання кінцевого числа дій і завжди призводить до деякого результату. У якості одного з можливих результатів є встановлення того факту, що задача не має рішень.
Під масовістю розуміється, що алгоритм розв'язання задачі розробляється в загальному вигляді так, щоб його можна було застосувати для цілого класу задач, що розрізняються лише наборами вихідних даних. У цю властивість і укладена основна практична цінність алгоритму.
2. Форми подання алгоритмів
Існують різні форми подання алгоритмів:
· Словесний опис алгоритму на природній мові (вербальна форма);
· Прогресивна запис алгоритму;
· Схема алгоритму;
· Запис на якому-небудь мові програмування.
Розглянемо особливості перших двох форм на прикладі алгоритму Евкліда - знаходження найбільшого загального дільника (НСД) для двох цілих позитивних чисел.
Словесний опис має мінімум обмежень і є найменш формалізованим. Однак при цьому алгоритм виходить і найменш суворим, що допускає появу невизначеностей. Також в цій формі алгоритм може виявитися дуже об'ємним і складним для сприйняття людиною.
Наприклад, якщо числа рівні, НОД дорівнює одному з них. В іншому випадку треба з більшого числа відняти менше, отриману різницю запам'ятати замість значення більшого числа і повторити все спочатку.
Прогресивний запис алгоритму - це запис природною мовою, але з дотриманням деяких додаткових правил:
· Кроки (приписи) нумеруються;
· Виконання кроків відбувається у порядку зростання номерів кроків, починаючи з першого (якщо не зустрічається ніяких спеціальних вказівок);
· Типовими кроками є читання (введення) даних, обробка даних (обчислення) за формулами; повідомлення (висновок) результату; перевірка умови; перехід до кроку з номером N; кінець обчислень.
Приклад: [1] Читання А, В
[2] Якщо А = В, йти до [8]
[3] Якщо А> В, йти до [6]
[4] В = В-А
[5] Йти до [2]
[6] А = А-В
[7] Йти до [2]
[8] НОД = А
[9] Запис НОД
[10] Кінець
Прогресивний запис алгоритму дозволяє уникнути невизначеностей в алгоритмі, не вимагає, по суті, ніяких спеціальних знань і в той же час забезпечує відпрацювання навичок логічно суворого викладу ходу рішення задачі (послідовність обчислень, можливих варіантів переходу до різних кроків алгоритму і т.д.) і полегшує подальше вивчення алгоритмічних мов. Однак прогресивна запис алгоритму сприймається людиною дуже важко і вимагає великої уваги при записі.
Найбільш наочний спосіб представлення алгоритмів - їх зображення у вигляді схем - послідовності блоків (рис.14), розпорядчих виконання певних функцій, і зв'язків між ними [6]. Усередині блоків вказується пояснюючий інформація, що характеризує їх ними дії. Конфігурацію і розмір блоків, а також порядок побудови схем визначає ГОСТ 19002 і 19003.
Виконання алгоритму завжди починається з блоку початку і закінчується при попаданні на блок кінця. Порядок обчислення визначається стрілками.
У блоці обробки даних міститься опис тих дій, які повинні бути виконані над об'єктами при попаданні на цей по входить до нього стрілкою. Тут обчислюються вираження і присвоюються нові значення змінних.
Перевірка умови зображується за допомогою блоку прийняття рішення, всередині якого записується цю умову. У результаті перевірки вибирається одна з двох стрілок, що визначає напрям подальших обчислень.
Усередині блоку введення перераховуються змінні, значення яких повинні бути введені в даному місці схеми.
Усередині блоку виводу перераховуються змінні, значення яких повинні бути виведені в даному місці схеми, або надрукований результат.
Коментарі використовуються в тих випадках, коли пояснення не поміщається всередині блоку. Сукупність коментарів повинна робити схему алгоритму зрозумілою для будь-якого користувача.
Нерідко виникає необхідність застосування вже наявних (може розроблених кимось) алгоритмів. У цьому випадку можна використовувати блок «зумовлений процес».
При великій насиченості схеми блоками допускається переривати стрілки, а потім продовжувати їх у потрібному місці. У цьому випадку початок і кінець віддалених ділянок позначаються з'єднувачами, всередині яких записуються для кожної перерваної стрілки одні й ті ж позначення.
Блок модифікація задає умови для виконання однієї і тієї ж послідовності кроків із змінною інформацією.
Існують різні форми подання алгоритмів:
· Словесний опис алгоритму на природній мові (вербальна форма);
· Прогресивна запис алгоритму;
· Схема алгоритму;
· Запис на якому-небудь мові програмування.
Розглянемо особливості перших двох форм на прикладі алгоритму Евкліда - знаходження найбільшого загального дільника (НСД) для двох цілих позитивних чисел.
Словесний опис має мінімум обмежень і є найменш формалізованим. Однак при цьому алгоритм виходить і найменш суворим, що допускає появу невизначеностей. Також в цій формі алгоритм може виявитися дуже об'ємним і складним для сприйняття людиною.
Наприклад, якщо числа рівні, НОД дорівнює одному з них. В іншому випадку треба з більшого числа відняти менше, отриману різницю запам'ятати замість значення більшого числа і повторити все спочатку.
Прогресивний запис алгоритму - це запис природною мовою, але з дотриманням деяких додаткових правил:
· Кроки (приписи) нумеруються;
· Виконання кроків відбувається у порядку зростання номерів кроків, починаючи з першого (якщо не зустрічається ніяких спеціальних вказівок);
· Типовими кроками є читання (введення) даних, обробка даних (обчислення) за формулами; повідомлення (висновок) результату; перевірка умови; перехід до кроку з номером N; кінець обчислень.
Приклад: [1] Читання А, В
[2] Якщо А = В, йти до [8]
[3] Якщо А> В, йти до [6]
[4] В = В-А
[5] Йти до [2]
[6] А = А-В
[7] Йти до [2]
[8] НОД = А
[9] Запис НОД
[10] Кінець
Прогресивний запис алгоритму дозволяє уникнути невизначеностей в алгоритмі, не вимагає, по суті, ніяких спеціальних знань і в той же час забезпечує відпрацювання навичок логічно суворого викладу ходу рішення задачі (послідовність обчислень, можливих варіантів переходу до різних кроків алгоритму і т.д.) і полегшує подальше вивчення алгоритмічних мов. Однак прогресивна запис алгоритму сприймається людиною дуже важко і вимагає великої уваги при записі.
Найбільш наочний спосіб представлення алгоритмів - їх зображення у вигляді схем - послідовності блоків (рис.14), розпорядчих виконання певних функцій, і зв'язків між ними [6]. Усередині блоків вказується пояснюючий інформація, що характеризує їх ними дії. Конфігурацію і розмір блоків, а також порядок побудови схем визначає ГОСТ 19002 і 19003.
Виконання алгоритму завжди починається з блоку початку і закінчується при попаданні на блок кінця. Порядок обчислення визначається стрілками.
У блоці обробки даних міститься опис тих дій, які повинні бути виконані над об'єктами при попаданні на цей по входить до нього стрілкою. Тут обчислюються вираження і присвоюються нові значення змінних.
Перевірка умови зображується за допомогою блоку прийняття рішення, всередині якого записується цю умову. У результаті перевірки вибирається одна з двох стрілок, що визначає напрям подальших обчислень.
Усередині блоку введення перераховуються змінні, значення яких повинні бути введені в даному місці схеми.
Усередині блоку виводу перераховуються змінні, значення яких повинні бути виведені в даному місці схеми, або надрукований результат.
Коментарі використовуються в тих випадках, коли пояснення не поміщається всередині блоку. Сукупність коментарів повинна робити схему алгоритму зрозумілою для будь-якого користувача.
Нерідко виникає необхідність застосування вже наявних (може розроблених кимось) алгоритмів. У цьому випадку можна використовувати блок «зумовлений процес».
При великій насиченості схеми блоками допускається переривати стрілки, а потім продовжувати їх у потрібному місці. У цьому випадку початок і кінець віддалених ділянок позначаються з'єднувачами, всередині яких записуються для кожної перерваної стрілки одні й ті ж позначення.
Блок модифікація задає умови для виконання однієї і тієї ж послідовності кроків із змінною інформацією.
3.Основні алгоритмічні структури
До основних типів алгоритмічних структур належать: лінійна, розгалужуються і циклічна.
· Лінійний обчислювальний процес - це процес, блоки якого виконуються послідовно один за одним (порядок виконання блоків природний).
Наприклад, скласти структурну схему алгоритму для обчислення за формулою:
Обчислення за формулою є лінійний обчислювальний процес. Вихідні дані a, b, c, x. Cтруктурно схема алгоритму представлена на рис. 15.
· Розгалужуються структура використовується тоді, коли виникає необхідність в залежності від вихідних даних або від отриманих проміжних результатів здійснювати обчислення по одним або іншим формулами, тобто залежно від виконання якогось логічного умови обчислювальний процес повинен йти по одній або іншій гілці. Такий процес називають розгалужуються.
· Циклічна структура. Дуже часто зустрічаються процеси, коли рішення задачі зводиться до багаторазового вирахування з одним і тим же математичним залежностям при різних вхідних в них величинах. Багаторазово повторювані ділянки цього обчислювального процесу називають циклами, а сам процес - циклічним.
Схема циклічного процесу в загальному вигляді наведена на рис.17.
У даній схемі блоки мають таке призначення:
1 - блок завдання початкового значення параметра циклу;
2 - тіло циклу, тобто ділянка обчислювального процесу, який багато разів повторюється;
3 - блок зміни параметра циклу;
4 - блок перевірки умови виходу з циклу.
· Циклічна розгалужуються структура
Схема алгоритму циклічного разветвляющегося процесу представлена на рис.19.
До основних типів алгоритмічних структур належать: лінійна, розгалужуються і циклічна.
· Лінійний обчислювальний процес - це процес, блоки якого виконуються послідовно один за одним (порядок виконання блоків природний).
Наприклад, скласти структурну схему алгоритму для обчислення за формулою:
Обчислення за формулою є лінійний обчислювальний процес. Вихідні дані a, b, c, x. Cтруктурно схема алгоритму представлена на рис. 15.
· Розгалужуються структура використовується тоді, коли виникає необхідність в залежності від вихідних даних або від отриманих проміжних результатів здійснювати обчислення по одним або іншим формулами, тобто залежно від виконання якогось логічного умови обчислювальний процес повинен йти по одній або іншій гілці. Такий процес називають розгалужуються.
· Циклічна структура. Дуже часто зустрічаються процеси, коли рішення задачі зводиться до багаторазового вирахування з одним і тим же математичним залежностям при різних вхідних в них величинах. Багаторазово повторювані ділянки цього обчислювального процесу називають циклами, а сам процес - циклічним.
Схема циклічного процесу в загальному вигляді наведена на рис.17.
У даній схемі блоки мають таке призначення:
1 - блок завдання початкового значення параметра циклу;
2 - тіло циклу, тобто ділянка обчислювального процесу, який багато разів повторюється;
3 - блок зміни параметра циклу;
4 - блок перевірки умови виходу з циклу.
· Циклічна розгалужуються структура
Схема алгоритму циклічного разветвляющегося процесу представлена на рис.19.
4. Структурне програмування
4.1. Розробка алгоритмів «зверху - вниз»
Для спеціалістів, які вирішують за допомогою ЕОМ ті чи інші завдання, розробка алгоритму рішення є найважливішою справою. Існують різні методи розробки алгоритмів (і програм), але найбільш важливим є метод покрокової деталізації (або метод розробки «зверху - вниз»). При цьому методі спочатку продумується і фіксується безліч даних і результатів алгоритму без детального опрацювання окремих частин.
Задачу розбивають на автономні частини, кожна з яких істотно простіше. Може виявитися необхідним повторювати процес деталізації багато разів, але це визначається тільки складністю розв'язуваних завдань. Кінцевим рівнем деталізації алгоритму можна вважати такий, при якому в алгоритмі немає дій більших, ніж: звернення до готового алгоритму; обчислення арифметичного виразу і присвоювання значення змінної; порівняння арифметичних виразів (або змінних); купівлю (продаж) даних і т.п.
Головною вимогою до алгоритму, безсумнівно, є його працездатність. Однак створюючи алгоритм, необхідно пам'ятати про подальшу роботу над ним, про налагодження програми, яка буде створена за цим алгоритмом, а також про ймовірні користувачів, яким, можливо, буде потрібно цей алгоритм. Тому одним з найважливіших вимог до алгоритму є його простота і зрозумілість.
Виходячи з цих вимог, особливо зручним представляється при розробці алгоритмів використання основних алгоритмічних структур. Їх важливою особливістю є те, що вони мають один вхід і один вихід і можуть з'єднуватися один з одним в будь-якій послідовності. Це дає наочну і просту структуру алгоритму, за якою легше скласти програму.
Одним з основних вимог до програм є її адаптованість. Програма є адаптируемой, якщо вона допускає швидку модифікацію з метою пристосування до мінливих умов функціонування. Адаптованість означає, що внесення невеликих змін не потребуватиме кардинальної переробки всього програмного продукту. Адаптованість визначається багатьма факторами, причому одним з найважливіших є понимаемость вихідного тексту.
Зазвичай при складанні схеми алгоритму процес обчислення йде зверху вниз, повертаючись назад тільки в циклах, що дозволяє аналізувати алгоритм як звичайний текст, тобто зверху вниз.
Якщо технологію розробки алгоритмів «зверху - вниз» поєднати з використанням тільки структурних схем, то вийде нова технологія, яка називається структурним програмуванням зверху - вниз, ідея якого полягає в тому, що структура програми має відображати структуру розв'язуваної задачі, щоб алгоритм рішення був ясно видно з вихідного тексту. Для цього треба мати кошти для створення програми не тільки з допомогою трьох простих операторів, але і за допомогою засобів, більш точно відображають конкретну структуру алгоритму. З цією метою в програмування введено поняття підпрограми - набору операторів, які виконують потрібну дію і не залежать від інших частин вихідного коду. Програма розбивається на безліч дрібних підпрограм (посідають до 50 операторів - критичний поріг для швидкого розуміння мети підпрограми), кожна з яких виконує одну з дій, передбачених вихідним завданням. Комбінуючи ці підпрограми, вдається формувати підсумковий алгоритм вже не з простих операторів, а з закінчених блоків коду, що мають певне смислове навантаження, причому звертатися до таких блокам можна за назвами. Виходить, що підпрограми - це нові оператори або операції мови, визначаються програмістом.
Можливість застосування підпрограм відносить мову програмування до класу процедурних мов.
4.2. Низхідний проектування
Наявність підпрограм дозволяє вести проектування і розробку програми зверху вниз - такий підхід називається низхідним проектуванням. Спочатку виділяється кілька підпрограм, вирішують самі глобальні завдання (наприклад, ініціалізація даних, головна частина і завершення), потім кожен з цих модулів деталізується на більш низькому рівні, розбиваючись у свою чергу на невелику кількість інших підпрограм, і так відбувається до тих пір, поки вся завдання не виявиться реалізованою.
Такий підхід зручний тим, що дозволяє людині постійно мислити на предметному рівні, не опускаючись до конкретних операторів і змінних. Крім того, з'являється можливість деякі підпрограми не реалізовувати відразу, а тимчасово відкладати, поки не будуть закінчені інші частини. Наприклад, якщо є необхідність обчислення складної математичної функції, то виділяється окрема підпрограма такого обчислення, але реалізується вона тимчасово одним оператором, який просто привласнює заздалегідь вибране значення (наприклад, 5). Коли весь додаток буде написано і налагоджено, тоді можна приступити до реалізації цієї функції.
Важливо, що невеликі підпрограми значно простіше налагоджувати, що істотно підвищує загальну надійність всієї програми.
Дуже важлива характеристика підпрограм - це можливість їх повторного використання. З інтегрованими системами програмування поставляються великі бібліотеки стандартних підпрограм, які дозволяють значно підвищити продуктивність праці за рахунок використання чужої роботи зі створення часто застосовуваних підпрограм.
Підпрограми бувають двох видів - процедури та функції. Відрізняються вони тим, що процедура просто виконує групу операторів, а функція того ж обчислює деяке значення і передає його назад в головну програму (повертає значення). Це значення має певний тип (кажуть, що функція має такий-то тип).
Щоб робота підпрограми мала сенс, їй треба отримати дані з зовнішньої програми, яка цю підпрограму викликає. Дані передаються підпрограмі у вигляді параметрів або аргументів, які зазвичай описуються в її заголовку так само, як змінні.
Підпрограми викликаються, як правило, шляхом простого запису їх назви з потрібними параметрами. У Бейсіку є оператор CALL для явної вказівки того, що відбувається виклик підпрограми.
Підпрограми активізуються тільки у момент їх виклику. Оператори, що знаходяться усередині підпрограми, виконуються, тільки якщо ця підпрограма явно викликана. Поки виконання підпрограми повністю не закінчиться, оператор головної програми, наступний за командою виклику підпрограми, виконуватися не буде.
Підпрограми можуть бути вкладеними - допускається виклик підпрограми не тільки з головної програми, але і з будь-яких інших підпрограм.
У деяких мовах програмування допускається виклик підпрограми з себе самої. Такий прийом називається рекурсією і потенційно небезпечний тим, що може привести до зациклення - безкінечного самовизову.
Підпрограма складається з декількох частин: заголовка з параметрами, тіла підпрограми (операторів, які будуть виконуватися при її виклику) і завершення підпрограми.
Локальні змінні, оголошені усередині підпрограми, мають областю дії тільки її тіло.
Після того як функція розрахувала потрібне значення, їй потрібно явно повернути його в зухвалу програму. Для цього може використовуватися спеціальний оператор (return в Сі + +) або особлива форма оператора присвоєння, коли в лівій частині вказується ім'я функції, а праворуч - значення, що повертається.
Приклад функції, що обчислює значення квадрата аргументу на Бейсіку:
FUNCTION SQR% (X AS INTEGER)
SQR% = X * X
END FUNCTION
Під час створення підпрограми заздалегідь не відомо, які конкретно параметри вона може і буде отримувати. Тому в якості змінних, які виступають в ролі її аргументів у заголовку, можуть використовуватися довільні допустимі назви, навіть збігаються з вже наявними. Компілятор все одно зрозуміє, що це не одне і те ж.
Параметри, які вказуються в заголовку підпрограми, називаються формальними. Вони потрібні тільки для опису тіла підпрограми. А параметри (конкретні значення), які зазначаються в момент виклику підпрограми, називаються фактичними параметрами. При виконанні операторів підпрограми формальні параметри як би тимчасово заміняться на фактичні.
Приклад.
int а, у;
а = 5;
у = SQR (a);
Програма викликає функцію SQR () з одним фактичним параметром «а». Усередині підпрограми формальний параметр «х» отримує значення змінної «а» і зводиться в квадрат. Результат повертається назад у програму і присвоюється змінної «у».
4.1. Розробка алгоритмів «зверху - вниз»
Для спеціалістів, які вирішують за допомогою ЕОМ ті чи інші завдання, розробка алгоритму рішення є найважливішою справою. Існують різні методи розробки алгоритмів (і програм), але найбільш важливим є метод покрокової деталізації (або метод розробки «зверху - вниз»). При цьому методі спочатку продумується і фіксується безліч даних і результатів алгоритму без детального опрацювання окремих частин.
Задачу розбивають на автономні частини, кожна з яких істотно простіше. Може виявитися необхідним повторювати процес деталізації багато разів, але це визначається тільки складністю розв'язуваних завдань. Кінцевим рівнем деталізації алгоритму можна вважати такий, при якому в алгоритмі немає дій більших, ніж: звернення до готового алгоритму; обчислення арифметичного виразу і присвоювання значення змінної; порівняння арифметичних виразів (або змінних); купівлю (продаж) даних і т.п.
Головною вимогою до алгоритму, безсумнівно, є його працездатність. Однак створюючи алгоритм, необхідно пам'ятати про подальшу роботу над ним, про налагодження програми, яка буде створена за цим алгоритмом, а також про ймовірні користувачів, яким, можливо, буде потрібно цей алгоритм. Тому одним з найважливіших вимог до алгоритму є його простота і зрозумілість.
Виходячи з цих вимог, особливо зручним представляється при розробці алгоритмів використання основних алгоритмічних структур. Їх важливою особливістю є те, що вони мають один вхід і один вихід і можуть з'єднуватися один з одним в будь-якій послідовності. Це дає наочну і просту структуру алгоритму, за якою легше скласти програму.
Одним з основних вимог до програм є її адаптованість. Програма є адаптируемой, якщо вона допускає швидку модифікацію з метою пристосування до мінливих умов функціонування. Адаптованість означає, що внесення невеликих змін не потребуватиме кардинальної переробки всього програмного продукту. Адаптованість визначається багатьма факторами, причому одним з найважливіших є понимаемость вихідного тексту.
Зазвичай при складанні схеми алгоритму процес обчислення йде зверху вниз, повертаючись назад тільки в циклах, що дозволяє аналізувати алгоритм як звичайний текст, тобто зверху вниз.
Якщо технологію розробки алгоритмів «зверху - вниз» поєднати з використанням тільки структурних схем, то вийде нова технологія, яка називається структурним програмуванням зверху - вниз, ідея якого полягає в тому, що структура програми має відображати структуру розв'язуваної задачі, щоб алгоритм рішення був ясно видно з вихідного тексту. Для цього треба мати кошти для створення програми не тільки з допомогою трьох простих операторів, але і за допомогою засобів, більш точно відображають конкретну структуру алгоритму. З цією метою в програмування введено поняття підпрограми - набору операторів, які виконують потрібну дію і не залежать від інших частин вихідного коду. Програма розбивається на безліч дрібних підпрограм (посідають до 50 операторів - критичний поріг для швидкого розуміння мети підпрограми), кожна з яких виконує одну з дій, передбачених вихідним завданням. Комбінуючи ці підпрограми, вдається формувати підсумковий алгоритм вже не з простих операторів, а з закінчених блоків коду, що мають певне смислове навантаження, причому звертатися до таких блокам можна за назвами. Виходить, що підпрограми - це нові оператори або операції мови, визначаються програмістом.
Можливість застосування підпрограм відносить мову програмування до класу процедурних мов.
4.2. Низхідний проектування
Наявність підпрограм дозволяє вести проектування і розробку програми зверху вниз - такий підхід називається низхідним проектуванням. Спочатку виділяється кілька підпрограм, вирішують самі глобальні завдання (наприклад, ініціалізація даних, головна частина і завершення), потім кожен з цих модулів деталізується на більш низькому рівні, розбиваючись у свою чергу на невелику кількість інших підпрограм, і так відбувається до тих пір, поки вся завдання не виявиться реалізованою.
Такий підхід зручний тим, що дозволяє людині постійно мислити на предметному рівні, не опускаючись до конкретних операторів і змінних. Крім того, з'являється можливість деякі підпрограми не реалізовувати відразу, а тимчасово відкладати, поки не будуть закінчені інші частини. Наприклад, якщо є необхідність обчислення складної математичної функції, то виділяється окрема підпрограма такого обчислення, але реалізується вона тимчасово одним оператором, який просто привласнює заздалегідь вибране значення (наприклад, 5). Коли весь додаток буде написано і налагоджено, тоді можна приступити до реалізації цієї функції.
Важливо, що невеликі підпрограми значно простіше налагоджувати, що істотно підвищує загальну надійність всієї програми.
Дуже важлива характеристика підпрограм - це можливість їх повторного використання. З інтегрованими системами програмування поставляються великі бібліотеки стандартних підпрограм, які дозволяють значно підвищити продуктивність праці за рахунок використання чужої роботи зі створення часто застосовуваних підпрограм.
Підпрограми бувають двох видів - процедури та функції. Відрізняються вони тим, що процедура просто виконує групу операторів, а функція того ж обчислює деяке значення і передає його назад в головну програму (повертає значення). Це значення має певний тип (кажуть, що функція має такий-то тип).
Щоб робота підпрограми мала сенс, їй треба отримати дані з зовнішньої програми, яка цю підпрограму викликає. Дані передаються підпрограмі у вигляді параметрів або аргументів, які зазвичай описуються в її заголовку так само, як змінні.
Підпрограми викликаються, як правило, шляхом простого запису їх назви з потрібними параметрами. У Бейсіку є оператор CALL для явної вказівки того, що відбувається виклик підпрограми.
Підпрограми активізуються тільки у момент їх виклику. Оператори, що знаходяться усередині підпрограми, виконуються, тільки якщо ця підпрограма явно викликана. Поки виконання підпрограми повністю не закінчиться, оператор головної програми, наступний за командою виклику підпрограми, виконуватися не буде.
Підпрограми можуть бути вкладеними - допускається виклик підпрограми не тільки з головної програми, але і з будь-яких інших підпрограм.
У деяких мовах програмування допускається виклик підпрограми з себе самої. Такий прийом називається рекурсією і потенційно небезпечний тим, що може привести до зациклення - безкінечного самовизову.
Підпрограма складається з декількох частин: заголовка з параметрами, тіла підпрограми (операторів, які будуть виконуватися при її виклику) і завершення підпрограми.
Локальні змінні, оголошені усередині підпрограми, мають областю дії тільки її тіло.
Після того як функція розрахувала потрібне значення, їй потрібно явно повернути його в зухвалу програму. Для цього може використовуватися спеціальний оператор (return в Сі + +) або особлива форма оператора присвоєння, коли в лівій частині вказується ім'я функції, а праворуч - значення, що повертається.
Приклад функції, що обчислює значення квадрата аргументу на Бейсіку:
FUNCTION SQR% (X AS INTEGER)
SQR% = X * X
END FUNCTION
Під час створення підпрограми заздалегідь не відомо, які конкретно параметри вона може і буде отримувати. Тому в якості змінних, які виступають в ролі її аргументів у заголовку, можуть використовуватися довільні допустимі назви, навіть збігаються з вже наявними. Компілятор все одно зрозуміє, що це не одне і те ж.
Параметри, які вказуються в заголовку підпрограми, називаються формальними. Вони потрібні тільки для опису тіла підпрограми. А параметри (конкретні значення), які зазначаються в момент виклику підпрограми, називаються фактичними параметрами. При виконанні операторів підпрограми формальні параметри як би тимчасово заміняться на фактичні.
Приклад.
int а, у;
а = 5;
у = SQR (a);
Програма викликає функцію SQR () з одним фактичним параметром «а». Усередині підпрограми формальний параметр «х» отримує значення змінної «а» і зводиться в квадрат. Результат повертається назад у програму і присвоюється змінної «у».
5. Подієво-орієнтоване програмування
З активним поширенням системи Windows і появою візуальних RAD-середовищ широку популярність придбав подієвий підхід до створення програм - подієво-орієнтоване програмування.
Ідеологія системи Windows заснована на подіях. Клацнув людина на кнопці, вибрав пункт меню, натиснув на клавішу або кнопку миші - в Windows генерується підходяще повідомлення, яке надсилається вікна відповідної програми.
Структура програми, створеної за допомогою подієвого програмування, наступна. Головна частина являє собою один нескінченний цикл, який опитує Windows, стежачи за тим, чи не з'явилося нове повідомлення. При його виявленні викликається підпрограма, відповідальна за обробку відповідної події (обробляються не всі події, їх сотні, а тільки потрібні), і подібний цикл опитування триває, поки не буде отримано повідомлення «Завершити роботу»,
Події можуть бути призначеними для користувача, що виникли в результаті дій користувача, системними, що виникають в операційній системі (наприклад, повідомлення від таймера), та програмними, що генеруються самою програмою (наприклад, виявлена помилка і її треба обробити).
Подієве програмування є розвитком ідей спадного проектування, коли поступово визначаються і деталізуються реакції програми на різні події.
З активним поширенням системи Windows і появою візуальних RAD-середовищ широку популярність придбав подієвий підхід до створення програм - подієво-орієнтоване програмування.
Ідеологія системи Windows заснована на подіях. Клацнув людина на кнопці, вибрав пункт меню, натиснув на клавішу або кнопку миші - в Windows генерується підходяще повідомлення, яке надсилається вікна відповідної програми.
Структура програми, створеної за допомогою подієвого програмування, наступна. Головна частина являє собою один нескінченний цикл, який опитує Windows, стежачи за тим, чи не з'явилося нове повідомлення. При його виявленні викликається підпрограма, відповідальна за обробку відповідної події (обробляються не всі події, їх сотні, а тільки потрібні), і подібний цикл опитування триває, поки не буде отримано повідомлення «Завершити роботу»,
Події можуть бути призначеними для користувача, що виникли в результаті дій користувача, системними, що виникають в операційній системі (наприклад, повідомлення від таймера), та програмними, що генеруються самою програмою (наприклад, виявлена помилка і її треба обробити).
Подієве програмування є розвитком ідей спадного проектування, коли поступово визначаються і деталізуються реакції програми на різні події.
6. Об'єктно-орієнтоване програмування.
6.1. Поняття об'єкта
Розвиток ідей структурного і подієвого програмування істотно підняло продуктивність праці програмістів і дозволило в розумні строки (кілька місяців) створювати додатки обсягом у сотні тисяч рядків. Однак такий обсяг вже наблизився до межі можливостей людини, і потрібні були нові технології розробки програм.
На початку 80-х років в програмуванні виник новий напрям, заснований на понятті об'єкта. До того часу основні обмеження на можливість створення великих систем накладала роз'єднаність у програмі даних і методів їх обробки.
Реальні об'єкти навколишнього світу володіють трьома базовими характеристиками: вони мають набір властивостей, здатні різними методами змінювати ці властивості і реагувати на події, що виникають як в навколишньому світі, так і всередині самого об'єкта. Саме в такому вигляді в мовах програмування і реалізовано поняття об'єкта як сукупності властивостей (структур даних, характерних для цього об'єкта), методів їх обробки (підпрограм зміни властивостей) і подій, на які даний об'єкт може реагувати і які приводять, як правило, до зміни властивостей об'єкта.
Поява можливості створення об'єктів в програмах якісно вплинуло на продуктивність праці програмістів. Максимальний обсяг додатків, які стали доступні для створення групою програмістів з 10 чоловік, за кілька років збільшився до мільйонів рядків коду, при цьому одночасно вдалося добитися високої надійності програм і, що важливо, повторно використовувати раніше створені об'єкти в інших завданнях.
Об'єкти можуть мати ідентичну структуру і відрізнятися тільки значеннями властивостей. У таких випадках в програмі створюється новий тип, заснований на єдиній структурі об'єкта (за аналогією з тим, як створюються нові типи для структур даних). Він називається класом, а кожен конкретний об'єкт, який має структуру цього класу, називається екземпляром класу.
Опис нового класу схоже на опис нової структури даних, тільки до полів (властивостями) додаються методи - підпрограми.
При визначенні підпрограм, що належать конкретному класу, його методів, в заголовку підпрограми перед її назвою явно вказується, до якого класу вона належить.
Клас - це тип даних, такий же, як будь-який інший базовий чи складний тип. На його основі можна описувати конкретні об'єкти (екземпляри класів).
Об'єктно-орієнтоване програмування базується на трьох ключових концепціях - інкапсуляції, успадкування та поліморфізм.
Об'єднання даних з методами в одному типі (класі) називається інкапсуляцією. Крім об'єднання, інкапсуляція дозволяє обмежувати доступ до даних об'єктів і реалізації методів класів. У результаті у програмістів з'являється можливість використання готових класів у своїх додатках на основі тільки описів цих класів.
Найважливіша характеристика класу - можливість створення на його основі нових класів з успадкуванням всіх його властивостей і методів і додаванням власних. Клас, що не має попередника, називається базовим.
Наприклад, клас «тварина» має властивості «назва», «розмір», методи «йти» і «розмножуватися». Створений на його основі клас «кішка» успадковує всі ці властивості і методи, до яких додатково додається властивість «забарвлення» і метод «пити».
Успадкування дозволяє створювати нові класи, повторно використовуючи вже готовий вихідний код і не витрачаючи часу на його переписування.
У більшості випадків методи базового класу в класів - спадкоємців доводиться перевизначати - об'єкт класу «кішка» виконує метод «йти» зовсім не так, як об'єкт класу «амеба». Всі перевизначати методи з написання (назвою) будуть збігатися з методами базового об'єкту, однак компілятор за типом об'єкта (його класу) розпізнає, який конкретно метод треба використовувати, і не викличе для об'єкта класу «кішка» метод «йти» класу «тварина». Така властивість об'єктів перевизначати методи успадкованого класу і коректно їх використовувати називається поліморфізмом.
Технології об'єктного, подієвого і структурного програмування сьогодні об'єднані в RAD-системах, які містять безліч готових класів, представлених у вигляді візуальних компонентів, які додаються в програму одним клацанням миші. Програмісту треба тільки спроектувати зовнішній вигляд вікон свого застосування і визначити обробку основних подій - які оператори будуть виконуватися при натисканні на кнопки, при виборі пунктів меню або щигликах мишкою. Весь допоміжний вихідний код середу згенерує сама, дозволяючи програмістові повністю зосередитися тільки на реалізації алгоритму.
6.1. Поняття об'єкта
Розвиток ідей структурного і подієвого програмування істотно підняло продуктивність праці програмістів і дозволило в розумні строки (кілька місяців) створювати додатки обсягом у сотні тисяч рядків. Однак такий обсяг вже наблизився до межі можливостей людини, і потрібні були нові технології розробки програм.
На початку 80-х років в програмуванні виник новий напрям, заснований на понятті об'єкта. До того часу основні обмеження на можливість створення великих систем накладала роз'єднаність у програмі даних і методів їх обробки.
Реальні об'єкти навколишнього світу володіють трьома базовими характеристиками: вони мають набір властивостей, здатні різними методами змінювати ці властивості і реагувати на події, що виникають як в навколишньому світі, так і всередині самого об'єкта. Саме в такому вигляді в мовах програмування і реалізовано поняття об'єкта як сукупності властивостей (структур даних, характерних для цього об'єкта), методів їх обробки (підпрограм зміни властивостей) і подій, на які даний об'єкт може реагувати і які приводять, як правило, до зміни властивостей об'єкта.
Поява можливості створення об'єктів в програмах якісно вплинуло на продуктивність праці програмістів. Максимальний обсяг додатків, які стали доступні для створення групою програмістів з 10 чоловік, за кілька років збільшився до мільйонів рядків коду, при цьому одночасно вдалося добитися високої надійності програм і, що важливо, повторно використовувати раніше створені об'єкти в інших завданнях.
Об'єкти можуть мати ідентичну структуру і відрізнятися тільки значеннями властивостей. У таких випадках в програмі створюється новий тип, заснований на єдиній структурі об'єкта (за аналогією з тим, як створюються нові типи для структур даних). Він називається класом, а кожен конкретний об'єкт, який має структуру цього класу, називається екземпляром класу.
Опис нового класу схоже на опис нової структури даних, тільки до полів (властивостями) додаються методи - підпрограми.
При визначенні підпрограм, що належать конкретному класу, його методів, в заголовку підпрограми перед її назвою явно вказується, до якого класу вона належить.
Клас - це тип даних, такий же, як будь-який інший базовий чи складний тип. На його основі можна описувати конкретні об'єкти (екземпляри класів).
Об'єктно-орієнтоване програмування базується на трьох ключових концепціях - інкапсуляції, успадкування та поліморфізм.
Об'єднання даних з методами в одному типі (класі) називається інкапсуляцією. Крім об'єднання, інкапсуляція дозволяє обмежувати доступ до даних об'єктів і реалізації методів класів. У результаті у програмістів з'являється можливість використання готових класів у своїх додатках на основі тільки описів цих класів.
Найважливіша характеристика класу - можливість створення на його основі нових класів з успадкуванням всіх його властивостей і методів і додаванням власних. Клас, що не має попередника, називається базовим.
Наприклад, клас «тварина» має властивості «назва», «розмір», методи «йти» і «розмножуватися». Створений на його основі клас «кішка» успадковує всі ці властивості і методи, до яких додатково додається властивість «забарвлення» і метод «пити».
Успадкування дозволяє створювати нові класи, повторно використовуючи вже готовий вихідний код і не витрачаючи часу на його переписування.
У більшості випадків методи базового класу в класів - спадкоємців доводиться перевизначати - об'єкт класу «кішка» виконує метод «йти» зовсім не так, як об'єкт класу «амеба». Всі перевизначати методи з написання (назвою) будуть збігатися з методами базового об'єкту, однак компілятор за типом об'єкта (його класу) розпізнає, який конкретно метод треба використовувати, і не викличе для об'єкта класу «кішка» метод «йти» класу «тварина». Така властивість об'єктів перевизначати методи успадкованого класу і коректно їх використовувати називається поліморфізмом.
Технології об'єктного, подієвого і структурного програмування сьогодні об'єднані в RAD-системах, які містять безліч готових класів, представлених у вигляді візуальних компонентів, які додаються в програму одним клацанням миші. Програмісту треба тільки спроектувати зовнішній вигляд вікон свого застосування і визначити обробку основних подій - які оператори будуть виконуватися при натисканні на кнопки, при виборі пунктів меню або щигликах мишкою. Весь допоміжний вихідний код середу згенерує сама, дозволяючи програмістові повністю зосередитися тільки на реалізації алгоритму.