Базові структури алгоритму

Форми опису алгоритмів. Складання й запис алгоритмів. Базові алгоритмічні структури.

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

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

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

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

В останньому означенні використовується поняття "виконавець". Що це означає? Під виконавцем алгоритму ми розуміємо будь-яку істоту (живу чи неживу), яка спроможна виконати алгоритм. Все залежить від того, якої мети ми намагаємося досягнути. Наприклад: риття ями (виконавці - людина або екскаватор), покупка деяких товарів (один із членів родини), розв'язування математичної задачі (учень або комп'ютер) тощо.

Кожний алгоритм створюється з розрахунку на конкретного виконавця, тому можна сказати, що алгоритм — це точні розпорядження (указівки, команди, ?Алгоритм – послідовність дій, спрямованих на розв’язання поставленої задачі. ?Алгоритм — кінцева послідовність кроків у рішенні завдання, що приводить від вихідних даних до необхідного результату. ?Алгоритмом називається зрозуміле і точне розпорядження виконавцю виконати послідовність дій, спрямованих на досягнення зазначеної мети чи на розв'язання поставленої задачі. 2 операції, інструкції) виконавцеві здійснити послідовність дій, спрямованих на розв’язання поставленої задачі.

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

Система команд виконавця — сукупність команд, які можуть бути виконані виконавцем; кожна команда алгоритму входить до системи команд виконавця.

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

Властивості алгоритму

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

2. Дискретність. Алгоритм розв’язання задачі повинен складатися з послідовності окремих кроків — відокремлених одна від одної команд (указівок), кожна з яких виконується за кінцевий час. Тільки закінчивши виконання однієї команди, виконавець переходить до виконання іншої.

3. Визначеність (однозначність). Кожна команда алгоритму однозначно визначає дії виконавця і не припускає подвійного тлумачення. Суворо визначеним є й порядок виконання команд.

4. Формальність. Будь-який виконавець, який володіє заданою системою команд, може виконати заданий алгоритм, не вникаючи в суть задачі. 3

5. Скінченність алгоритму. Послідовність команд, які потрібно виконати, має бути скінченною.

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

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

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

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

2. Другий спосіб - це подача алгоритму у вигляді таблиць, формул, схем, малюнків тощо. Наприклад, всіх вас вчили в дитячому садочку правилам поведінки на дорозі. І найкраще діти, вочевидь, сприймають алгоритм, що поданий у вигляді схематичних малюнків. Дивлячись на них, дитина, а потім і доросла людина, відпрацьовує ту лінію поведінки, що їй пропонується. Аналогічно можна навести приклади алгоритмів, що записані у вигляді умовних позначок на купленому товарі, щодо його користування (заварювання чаю, прання білизни тощо). У математиці наявність формул дозволяє розв'язати задачу, навіть "не використовуючи слів".

3. Третій спосіб - запис алгоритмів за допомогою блок-схеми. Цей метод був запропонований в інформатиці для наочності представлення алгоритму за допомогою набору спеціальних блоків. Основні з цих блоків наступні:

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

4. Четвертий спосіб - навчальні алгоритмічні мови (псевдокоди). Ці мови мають жорстко визначений синтаксис і вже максимально наближені до машинної мови (мови програмування). Але створені вони з навчальною метою, тому мають зрозумілий для людей вигляд. Таких псевдокодів зараз існує велика кількість, починаючи з графічних середовищ "Алгоритміка", "Роботландія", "Лого-світи", "Черепашка" тощо і закінчуючи текстовими "національними" реалізаціями алгоритмічних мов, подібних до Бейсіка, Паскаля. Ці псевдокоди мають програмну реалізацію і дуже широко застосовуються на етапі навчання основам програмування.

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

Базові структури алгоритму

Базові структури алгоритму — це структури, за допомогою яких створюється алгоритм для розв’язання певної задачі. Існують три основні (базові) алгоритмічні структури, або три основні типи алгоритмів: лінійний, розгалужений та циклічний.

1. Лінійний алгоритм (послідовне виконання, структура слідування) — це алгоритм, який забезпечує отримання результату шляхом одноразового виконання послідовності дій, незалежно від вхідних даних і проміжних результатів.

Дії в таких алгоритмах виконуються послідовно, одна за однією, тобто лінійно. Алгоритм РАНОК

1.Встати о 6.30 годині.

2.Виконати гімн. вправи.

3.Умитися.

4.Поснідати.

5.Вийти з дому о 7.30 годині.

2. Розгалужений алгоритм (умова, структура вибору) — у класичному варіанті ця структура розглядається як вибір дій у разі виконання або невиконання заданої умови. Галуження бувають повними і неповними. Повне галуження — це галуження, в якому певні дії визначені й у разі виконання, і в разі невиконання умови. Неповне галуження — це розгалуження, в якому дії визначені тільки у разі виконання (або у разі невиконання) умови. Якщо логічний вираз, то команда 1, інакше команда 2.

Серія команд – це декілька команд.

Алгоритм ВЕЧІР

1.Повернутися з коледжу додому після занять.

2.Пообідати.

3.Якщо погода хороша, то попрацювати в саду, інакше піти в бібліотеку, взяти книжку, повернутися додому.

4.Зробити домашнє завдання.

5.Повечеряти.

6.Якщо є цікава телепередача, то подивитися телевізор, інакше 7 почитати книжку.

7.Лягти спати.

3. Циклічний алгоритм (цикл, структура повторення) — це алгоритм, у якому передбачено повторення деякої серії команд. За допомогою цієї структури описуються однотипні дії, що повторюються декілька разів. Такі алгоритми забезпечують виконання довгої послідовності дій, записаних порівняно короткою послідовністю команд. Саме використання циклів дозволяє у повній мірі реалізувати швидкодію комп’ютерів. Циклом називають процес повторення дій. Циклічні алгоритми забезпечують повторне виконання деяких команд скінчену кількість разів. Доки логічний вираз, виконати команди

Алгоритм КОЛЕДЖ

1.Іти на першу пару.

2.Доки не закінчилися заняття іти на наступну пару.

3.Іти додому.

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

Способи запису алгоритму

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

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

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

Приклад 1. Створити блок-схему для обчислення функції X*SIN(X/2) по введеному значенню аргументу Х В цій задачі треба послідовно виконати ряд кроків, однакових для всіх вхідних даних, отже це буде лінійний алгоритм.

Приклад 2. Знайти корені квадратного рівняння ax 2 +bx+c=0, де a, b, c > 0. Блок схема представляє алгоритм з розгалуженням: