Алгоритми: властивості, блок-схеми та базові структури
Алгоритм
Властивості алгоритму:
дискретність — поділ на окремі кроки;
визначеність — кожен крок однозначний;
скінченність — завершення за скінченну кількість кроків;
результативність — отримання результату;
масовість — застосовність до класу задач.
Способи подання
Алгоритм подають словесно, у вигляді блок-схеми або програмою мовою програмування.
Блок | Призначення |
|---|---|
Овал | початок і кінець |
Паралелограм | введення й виведення |
Прямокутник | обчислення |
Ромб | умова з двома виходами (так/ні) |
Базові алгоритмічні структури
Слідування — команди виконуються одна за одною.
Розгалуження — вибір виконання залежно від умови: «якщо …, то …, інакше …».
Повторення (цикл) — багаторазове виконання групи команд: з лічильником (скільки разів відомо), з передумовою або післяумовою.
Приклад: найбільший спільний дільник
Алгоритм Евкліда: поки , замінюємо пару на . Коли , відповідь — .
Складність
Той самий результат можна отримати різними алгоритмами. Їх порівнюють за часом роботи й обсягом пам’яті. Наприклад, пошук числа в невпорядкованому списку з елементів у гіршому разі потребує порівнянь, а двійковий пошук у впорядкованому — близько .
BitMath · https://www.bitmath.com.ua/informatyka/alhorytmy/alhorytmy-ta-blok-skhemy