З відповідями ← До сторінки

Алгоритми: властивості, блок-схеми та базові структури

Алгоритм

Означення

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

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

  • дискретність — поділ на окремі кроки;

  • визначеність — кожен крок однозначний;

  • скінченність — завершення за скінченну кількість кроків;

  • результативність — отримання результату;

  • масовість — застосовність до класу задач.

Способи подання

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

Блок

Призначення

Овал

початок і кінець

Паралелограм

введення й виведення

Прямокутник

обчислення

Ромб

умова з двома виходами (так/ні)

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

  1. Слідування — команди виконуються одна за одною.

  2. Розгалуження — вибір виконання залежно від умови: «якщо …, то …, інакше …».

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

Приклад: найбільший спільний дільник

Алгоритм Евкліда: поки b=0, замінюємо пару (a;b) на (b;amodb). Коли b=0, відповідь — a.

Приклад

Знайдіть НСД(48; 18) за алгоритмом Евкліда, записуючи кожен крок.

Складність

Той самий результат можна отримати різними алгоритмами. Їх порівнюють за часом роботи й обсягом пам’яті. Наприклад, пошук числа в невпорядкованому списку з n елементів у гіршому разі потребує n порівнянь, а двійковий пошук у впорядкованому — близько log2​n.

BitMath · https://bitmath.com.ua/informatyka/alhorytmy/alhorytmy-ta-blok-skhemy