Розділ 9. Основні поняття алгоритмізації

Алгоритми та їх виконавці; властивості алгоритмів; способи опису алгоритмів; базові алгоритмічні структури.

9.1. Поняття алгоритму

Людина постійно користується алгоритмами, часто не підозрюючи цього. Наприклад, є алгоритми розв’язування систем лінійних рівнянь, складання шкільного розкладу занять, поділу відрізка навпіл за допомогою циркуля та лінійки, запису заданих чисел з^г порядкз⁷ спадання, додавання двох чисел у десятковій системі числення. Прикладами алгоритмів с також правила переходу перехрестя в з'лиць, порядок вимикання комп’ютера, послідовність дій впроцесі приготу'вання страви та багато інших.

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

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

Слово "алгоритм" походить від імені видатного арабського математика IX століття аль-Хорезмі, який розробив правила виконання чотирьох арифметичних дій над десятковими числами.

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

Приклад. Опишемо алгоритм поділу відрізка АВ навпіл за допомогою циркуля та лінійки.

1. Встановити ніжку циркуля в точці *А

2. Дрзтз' ніжку циркуля встановити у точці В.

3. Окреслити коло.

4. Встановити ніжку циркуля в точці В, не змінюючи його розхил.

5. Окреслити коло.

6. Через точки перетинз⁷ кіл за допомогою лінійки провести пряму.

7. Позначити точк}' перетину проведеної прямої з цим відрізком літерою О.

Точка О і е серединою відрізка АВ.

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

У багатьох алгоритмах об’єктом перетворення є літерна або літерно-цифрова інформація. Прикладами таких алгоритмів є алгоритм запису прізвищ в алфавітному порядку, алгоритм вибору із заданого списку осіб, які мають інженерну освіту з радіоелектроніки та стаж роботи понад 10 років, алгоритм підрахунку в тексті кількості речень, що починаються зі слова МОРЕ та ін.

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

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

Перевіряємо себе

1. Що називають алгоритмом?

2. Як і коли виникло поняття алгоритму?

3. Що є об’єктом перетворення в чисельних алгоритмах?

4. Сформулюйте поняття виконавця.

5. Що таке система команд виконавця?

6. Наведіть приклади виконавців алгоритмів.

Виконуємо

1. Складіть алгоритм побудови бісектриси кута за допомогою циркуля та лінійки.

Складіть алгоритм обчислення середнього арифметичного

двох чисел.

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

До основних властивостей алгоритмів належать такі:

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

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

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

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

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

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

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

Приклад 1. Опишемо алгоритм розв’язування квадратного рівняння.

1. Надати змінним а, Ы с певні числові значення.

2. Обчислити значення дискримінанта сі за формулою

3. Якщо сі < 0, перейти до пункт}' в, інакше виконати пункт 4.

4. Визначити хі і хч за формулами:

5. Перейти до пункт}' 7.

6. Дискримінант від'ємний. Рівняння розв’язків не має.

7. Кінець.

Приклад 2. Алгоритм обчислення найбільшого спільного дільника двох натуральних чисел А і В (алгоритм Евкліда).

1. Якщо А = В, то перейти до пункту 7, інакше виконати пункт 2.

2. Якщо А >В, то перейти до пункту 5, інакше виконати пункт 3.

3. Значення В зменшити на величину А.

4. Перейти до пункту 1.

5. Значення А зменшити на величину В.

6. Перейти до пункту 1.

7. Найбільший загальний дільник, який має значення А, присвоїти змінній О.

8. Кінець.

Неважко впевнитися, що алгоритм Евкліда дає правильний результат при різних значеннях натуральних чисел А і В. Наприклад, якщо А = 23 і В = 65, то П = 1, якщо А = 119 і В = 51, то Л - 17.

Для розв'язання двох останніх завдань ми використовували різноманітні дані. Одні з них були початковими (а, в, с — у прикладі 1 та А, В — у прикладі 2), остаточні результати (хі, хч — у прикладі 1 та Л — у прикладі 2) отримали після опрацювання початкових даних. При цьому використовували допоміжні дані (наприклад, (1-у прикладі 1).

Початкові (вхідні) дані наливають аргументами, остаточні (вихідні) дані - результатами, допоміжні дані - проміжними.

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

Перевіряємо себе

1. Які основні властивості мас алгоритм?

2. У якій послідовності виконуються вказівки алгоритму?

3. Чи різні виконавці можуть отримати різні результати роботи одного алгоритму?

4. Від чого залежить міра деталізації алгоритму?

5. Назвіть основні властивості алгоритмів.

6. Наведіть характеристики властивостей алгоритмів.

7. Що таке аргументи, результати та проміжні дані алгоритму?

Виконуємо

1. Опишіть алгоритм підрахунку кількості літер "а" у слові довжиною 10 символів.

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

9.3. Способи описання алгоритмів

Існують різноманітні способи описання алгоритмів, наприклад, словесно-формульний, зображення у вигляді блок-схеми, запис мовою програмування. Розглянемо два найбільш поширених простих способи.

Словесно-формульний спосіб. Цей спосіб описаїшя алгоритмів люди широко використовують у ПОВСЯКДСННОМ}' житті як інструкції з експлуатації пристроїв, рецепти виготовлення ліків тощо. Перевага цього способ}' полягає в його простоті. Але такі описи алгоритмів часто е громіздкими, а їх вказівки різні виконавці можуть сприймати неоднозначно.

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

<змінна>:=< вираз>

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

отримане значення присвоюється змінній, записаній ліворуч.

Приклад. За допомогою оператора присвоювання алгоритм розв'язування квадратного рівняння (див. підрозділ 9.2) можна записати так:

1. Увести значення змитих а, Ь, с.

2.

3. Якщо сі < 0, виконати пункт 6. інакше - пупкт 4.

4.

5. Перейти до пункту 7.

6. Дискримінант від'ємний. Рівняння розв’язків не має.

7. Кінець.

Зображення алгоритмів у вигляді блок-схеми. Переваги зображення алгоритму блок-схеми, порівняно зі словесио-формульним

способом описання, полягають у наочності та простоті. Основні графічні позначення, за допомогою яких конструюються блок-схеми алгоритму, показані на рис. 9.1.

1. Термінатор (рис. 9.1, а). Визначає початок або кінець алгоритму. У заокруглений прямокутник може записуватися слово "Початок" або "Кінець". Крім цього, разом зі словом "Початок" може бути вказане ім’я алгоритму або дія, яку він виконує.

2. Дані (рис. 9.1, б). Конструкція відображає дані, що можуть бути записані на різноманітних носіях. Може використовуватися для позначення операцій введення і виведення. У цьому випадку всередині паралелограма слід записувати слово "Введення" ("Виведення") і значення або імена змінних, що вводяться (виводяться).

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

4. Розгалуження (рис. 9.1, г). Конструкція розгалуження

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

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

Якщо кілька стрілок спрямовано в один блок, їх можна поєднати в одній точці.

Приклад. Сконструюємо блок-схему алгоритму обчислення значення виразу

Значення виразу залежить від чотирьох параметрів: а, Ь, с, х. Тому після термінатора, що позначає початок алгоритму, зобразимо блок даних, у якому надаватимуться значення цих параметрів. Вираз є умовним, адже те, за якою формулою обчислюватиметься значення у,

залежить від виконання умови х > 0. Тому після блоку даних зобразимо розгалуження, на кожній із гілок якого розташуємо блоки процесу, де запишемо відповідні формули. За якою формулою не обчислювалося б значення у, його потрібно вивести. Отже, обидва блоки процесів з’єднуємо з блоком даних, яким позначимо виведення у. Завершуємо блок-схему термінатором "Кінець" (рис. 9.2).

Рис. 9.2. Блок-схема алгоритму обчислення значення умовного виразу

і Складіть блок-схему алгоритму обчислення значення виразу

9.4. Базові алгоритмічні структури

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

Алгоритми з лінійною структурою. У таких алгоритмах вказівки виконуються послідовно в порядку їх запису. На рис. 9.3 подано

приклад блок-схеми лінійного алгоритму обчислення значення виразу у = ах - віл^ш:.

Спочатку здійснюється введення значень а та х, які потім перемножуються, і одержаний результат присвоюється змінній £. Далі, від значення і віднімається значення віпЧ, і одержаний результат присвоюється змігшій у. Завернеться виконання алгоритму' виведенням результату.

Рис. 9.3. Блок-схема лінійного алгоритму

Алгоритми з розгалуженою структурою. У цих

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

інструкція 5, інакше вона не виконується (рис. 9.4, о).

Двохальтернативне розгалуження зад ас таку послідовність дій: якщо умова В істинна, виконується інструкція 52, інакше - 52 (рис. 9.4, б).

Блок-схема алгоритму зображена на рис. 9.5. Цей алгоритм є прикладом алгоритму з перевіркою складної умови: якщо х >0, здійснюється перевірка умови а < 0. Якщо умова х > 0 не виконується, змігшій у присвоюється значення 0.

Алгоритми з повтореннями (з циклічною структурою). У таких алгоритмах одні й ті самі вказівки (команди) виконуються багаторазово для різних значень одних і тих самих змінних.

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

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

Як бачимо з рис. 9.6, обчислення значення заданої функції здійснюється за такою схемою: уі = уі-1 -х, де і = 1, 2, 3,... , п; уО = 1, тобто на першому кроці у = 1*х, на другому — у = х * х, на третьому — у = х 2* х і т.д. На рис. 9.6 праворуч проілюстровано процес виконання алгоритму для п=4.

У розглянутому прикладі підготовчу частину зображає блок 3, в якому змінним х та у присвоюються одиниці. Робочу частину (яку ще називають тілом циклу) утворюють вказівки, що визначають основні обчислення. В алгоритмі, блок-схема якого зображена на рис. 9.6, тілом циклу є блок 4, а блоки 5 і 6 здійснюють керування циклом. У керівній частині перевіряється умова завершення циклу. Якщо ця умова істинна, виконання циклу припиняється, інакше - триває далі. В алгоритмі (рис.

Лічильник — це змінна, значення якої вказує на те, скільки разів виконано тіло циклу.

9.6) умовою завершення циклу є вираз і < п. У цій умові перевіряється значення лічильника, яким у даному випадку є змінна і.

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

Наприклад, при створенні алгоритму знаходження суми 8Іп(.т) + + сой(.г') допоміжним алгоритмом може слугувати алгоритм обчислення окремо 8Іп(х) .9 і окремо соб(.г); у процесі створення алгоритму⁷ поділу' кута на чотири рівні частини допоміжним алгоритмом слугуватиме алгоритм поділу кута навпіл.

При створенні складних алгоритмів широко використовується метод покрокової деталізації, сутність якого полягає в тому, що складну

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

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

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

Перевіряємо себе

1. Із яких алгоритмічних структур складаються алгоритми?

2. Які с різновиди алгоритмів із розгалуженою структурою?

3. Із яких частин складаються циклічні алгоритми*

4. Для чого використовується лічильник циклу?

5. Чому послідовність, розгалуження і повторення називають базовими алгоритмічними конструкціями?

6. Що таке аргументи, результати і проміжні дані алгоритму?

7. Які алгоритми називають допоміжними?

8. Які переваги надає застосування допоміжних алгоритмів?

Виконуємо

1. Складіть блок-схему алгоритму обчислення значення функції у = а² + кх.

2. Складіть блок-схему алгоритм}' обчислення значення виразу

Задано послідовність натуральних чисел: 1, 2, 3,..., п. Складіть блок-схем}' алгоритм}', за яким обчислюється сума парних членів цієї послідовності.

Задано послідовність натуральних чисел. Складіть блок-схем}' алгоритму обчислення добутку п перших членів цієї послідовності.

і Складіть блок-схему алгоритму обчислення суми

Завдання

1. Розробити алгоритм переходу регульованого перехрестя вулиць 5' словесній формі.

2. Накреслити основні позначення на блок-схемах алгоритмів.

3. Накреслити блок-схему алгоритму обчислення суми членів арифметичної прогресії.

4. Накреслити й описати блок-схему алгоритму обчислення виразу у = а³ + (ах + 3), якщо х > 2, інакше у = а/2 + 4.

Словничок

Це матеріал з підручника Інформатика 8 клас (поглиблений рівень) Гуржій