Циклічні алгоритми

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

Організація циклу вимагає встановлення початкових значень тим змінним, які використовуються в циклі. Такі дії зображуються блоком «початкові надання» (блоком ініціалізації). Дії, описані блоком «початко­ві надання», виконуються тільки один раз і в подальшій роботі циклу участі не беруть.

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

Кожного разу після виконання тіла циклу робиться перевірка умови виходу з циклу за допомогою блоку «умова». Вихід з циклу відбувається після досягнення лічильником циклів заданого значення або після вико­нання заданої умови

Блоки «початкові надання», «тіло циклу» та «умова» є складовими частинами циклу.

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

Цикли бувають двох видів:

· цикл «До» (з післяумовою);

· цикл «Поки» (з передумовою);

Цикл «До». Застосовується при необ­хідності виконати «тіло циклу» кілька разів до виконання заданої «умови». Особ­ливість цього циклу полягає в тому, що він виконується хоча б один раз і цикл закінчується, як тільки умова виконається (стане істинною).

Цикл «Поки». Застосовується при не­обхідності спочатку перевірити «умову» і, можливо, потім виконати «тіло циклу». Якщо при першій перевірці «умови» вона не вико­нається (виявиться хибною), то «тіло циклу» не виконається ні разу, а виконуватись «тіло циклу» буде доти, поки умова істинна. Цикл закінчиться, коли умова стане хибною (не виконається).

При логічних помилках в циклічних алгоритмах може виникнути ситуація, коли тіло циклу виконується раз за разом, а умо­ва припинення циклу не настає. Така ситуа­ція називається «зациклювання». Роботу таких програм доводиться припиняти штучно і шукати помилку.

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

1. Лінійний алгоритм – алгоритм, в якому використовується тільки структура «слідування».

2. Алгоритмом з розгалуженням – алгоритм, в основі якого лежить структура «розгалуження».

3. Циклічний алгоритм – алгоритм, в основі якого лежить структура «повторення».

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

Структурне програмування – це процес побудови алгоритмів та програм, що виконується в такій послідовності:

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

2. Послідовна (зверху донизу) деталізація частин та складання програм для кожного змодулів. Виділяють основну частину та частини нижнього рівня. Кож­ну частину розробляють окремо: спочатку частини верхнього рівня, а потім – нижнього. У кінці частини з’єднують між собою.

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

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

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

Модуль – це послідовність логічно зв’язаних операцій, яка оформлена у вигляді окремої частини програми.

Великі алгоритми проекту­ють так. Спочатку аналізують умову задачі. Складають загальний план її розв’язування. Якщо задача складна, то її розбивають на декілька простіших підзадач. Проектують модульну структуру алгоритму: описують призначення головного та допоміжних алгоритмів, дають їм назви. Потім деталізують (створюють, уточнюють) необхідні допоміжні алгоритми для розв’язування підзадач. Маючи допоміжні алгоритми, записують головний алгоритм, який складатиметься з команд викликів допоміжних. Отже, великі алгоритми утворюють з готових модулів подібно до того, як будинки будують з готових блоків, а машини збирають з окремих деталей.

Аналіз алгоритму – це структурний контроль правильності алгоритму: виділення основних складових елементів, їх структури і взаємозв’язку.

Створення алгоритму

Будь-який алгоритм треба розглядати як опис процедури, яка обробляє вхідні дані й отримує вихідні дані. Вхідні дані ще називають входом алгоритму, або його аргументами, а вихідні дані − виходом алгоритму, або результатом.

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

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

Виникає запитання: а як дізнатися, правильний чи непра­вильний алгоритм ми створили? Як перевірити, зупиниться він чи ні? Можна проаналізувати алгоритм, виконуючи по кроках записані у ньому дії. Але це реально лише для невели­ких вхідних даних. Однак не завжди така перевірка дасть остаточну відповідь. Інший вихід полягає в тому, щоб записати алгоритм обраною мовою програмування і виконати програму на комп’ютері.

Усі алгоритми поділяються на два великі класи. Це алго­ритми з повтореннями та рекурсивні алгоритми.

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

Рекурсивні алгоритми поділяють велику задачу на підзадачі, до кожної з яких окремо знову застосовуються ці самі алго­ритми. Такі алгоритми ще відносять до алгоритмів, основою створення яких є ідея «розділяй і володарюй». Перевагою та­ких алгоритмів є невеликий, простий і зрозумілий запис. Ана­ліз рекурсивних алгоритмів вимагає підрахунку кількості опе­рацій, необхідних для поділу задачі на підзадачі, виконання алгоритму в кожній із них та об’єднання отриманих резуль­татів для розв’язування задачі в цілому.

Отже, створення алгоритму − це один з етапів розв’язування поставленої задачі. Але він не відокремлений від усіх інших етапів, таких як:

ü визначення моделі задачі, що розв’язується;

ü запис алгоритму мовою програмування;

ü тестування програми на комп’ютері;

ü отримання розв’язку поставленої задачі шляхом виконан­ня завершеної програми.

Математична модель, вибір структури даних

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

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

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

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

Є і складніші структури даних. Знання всіх можливих структур даних значно роз­ширить коло задач, які ви зможете розв’язувати.

Дата добавления: 2013-12-13