Алгоритми. Блок-схеми

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

Термін «алгоритм» походить від імені узбецького математика ал-Хорезмі латинською мовою algorithmi), який сформулював правила виконання чотирьох арифметич­них дій.

Алгоритм - це послідовність дій, які спрямовані на досягнення вказа­ної мети або на розв'язання поставленої задачі.

Крім того, ця послідовність дій повинна задовольняти такі вимоги:

1. Скінченність. Виконання кожного алгоритму повинно завершуватись за скінченне число кроків.

2. Результативність. Виконання алгоритму призводить завжди до певного результату (зокрема, негативного) для кожних початкових даних, припустимих для цього алго­ритму.

3. Формальність. Виконавець відповідно до алгоритму одержить результат, не вникаючи в його суть.

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

5. Масовість. Алгоритм є правилом розв'язування ціло­го класу задач.

6. Зрозумілість. В алгоритмі зустрічаються лише опера­ції з набору операцій виконавця.

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

Часто за допомогою алгоритмів визначають нові опера­ції через уже відомі.    

Приклад 1. Скласти алгоритм обчислення виразу S=f(1)+f(2)+…+f(m)

де т — ціле число; f(k) — вираз, який залежить від k.

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

Останній запис між двома знаками «+», що відповіда­ють операції додавання, містить багато крапок, які для ви­конавця не визначають відомої операції. Можливі випад­ки m£1, при яких зміст цього запису стає ще менш зрозу­мілим.

Для обчислення суми запишемо такий алгоритм:

Крок 1. Визначити т.

Крок 2. Прийняти k=1 та S=0 і перейти на крок 3.

Крок 3. Якщо k>т, то шуканим значенням S буде зна­йдене значення. Процес обчислення завершити. У проти­лежному випадку перейти на крок 4.

Крок 4. Замінити S значенням виразу S+f(k) та k зна­ченням k+1. Перейти на крок 3.

Наведений алгоритм дає змогу обчислити суму при будь-якому цілому т. Відповідно до цього алгоритму мож­на написати програму мовою програмування для її реаліза­ції з використанням ЕОМ.

Приклад 2. Скласти алгоритм знаходження коренів квадратного рівняння

                                   a*x^2 + b*x + c = 0
 при а¹0.

Крок 1. Визначити а, b, с.

Крок 2. Обчислити D=b²—4ас.

Крок 3. Якщо D<0, то перейти на крок 7, у протилеж­ному випадку—на крок 4.

Крок 4. Обчислити корені півняння.

Крок 5. Надрукувати значення коренів.

Крок 6. Перейти на крок 8.

Крок 7. Надрукувати повідомлення, що рівняння коренів не має.

Крок 8. Процес обчислення завершити.

Уміння складати алгоритми — перший етап в оволодінні навиками програмування.

Розглянемо більш зручні способи запису алгоритмів з використанням блок-схем та алгоритмічної мови.

Приклад 3. Скласти алгоритм обчислення виразу S= 1+2+3+...+n , де n — ціле число.

Блок-схемний спосіб - запису алгоритмів

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

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

Позначення блоків

Блоки	Назва та призначення
Овал	Початок або кінець процесу обробки
Паралелограм	Блок введення
Надірваний папір	Блок виведення
Прямокутник	Арифметичний блок використовується при обчисленні виразів
Ромб	Логічний блок використову­ється для перевірки умов

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

У кожен блок може входити не менше однієї лінії, з кожного блоку може виходити тільки одна лінія. З логіч­ного блоку завжди виходять дві лінії потоку: одна у випад­ку виконання умови, друга — при її невиконанні.

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

Лінійні алгоритми (домашнє завдання)

Задача. Обчислити L=(Ax+B)y+z.

Алгоритми з розгалуженням (домашнє завдання)

Задача 1. Обчислити y=(x+5)/2 якщо x>=5, обчислити y=1- x^2 при x<5.

Задача 2. Якщо x+y>=0, тоді обчислити z=x^2 + y^2 і  k=x^3.

Задача 3. Якщо x>0, тоді обчислити y=x^2 + x+5, якщо x<0, тоді обчислити y=x^3 +10, якщо x=0, тоді задати y=15.

Задача 4. Скласти алгоритм знаходження більшого з трьох чисел А, В, С і результат присвоїти змінній y.

Складання блок-схем з циклами (домашнє завдання)

Циклічна блок-схема містить блоки, які можуть під час виконання алгоритму проходитись повторно. Є два типи циклів:

1.      Цикл з післяумовою

2.      Цикл з передумовою

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

Задача 1. Обчислити  суму парних чисел на проміжку [2,20]  (двома способами).

Задача 2. Протабулювати функцію y=sin(x+0,4) на проміжку [a,b] з кроком h (двома способами).

Задача 3. Ввести 15 чисел, знайти суму і кількість всіх додатніх.

Задача 4. Ввести n чисел, вивести всі від’ємні числа, піднесені до кубу.

Задача 5. Ввести 20 чисел, знайти максимальне.