Основні алгоритмічні конструкції
Способи запису алгоритму
На практиці найбільш поширеними є такі форми запису алгоритмів:
1) графічний запис (блок-схеми);
2) словесна запис (псевдокоди);
3) мова програмування.
Словесна форма запису алгоритму є опис природною мовою послідовних етапів обробки даних. Словесний спосіб немає широкого поширення, оскільки такі описи строго не формализуемы, допускають неоднозначність тлумачення окремих приписів. Алгоритм, записаний за допомогою псевдокода, є напівформалізованим описом умовною алгоритмічною мовою, що включає як основні елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення та інші.
Графічна форма запису, звана також схемою алгоритму, є зображення алгоритму як послідовності пов'язаних між собою функціональних блоків, кожен із яких відповідає виконанню однієї чи кількох дій. Графічний запис є більш компактним і наочним порівняно зі словесним. У схемі алгоритму кожному типу дій відповідає геометрична фігура. Фігури з'єднуються лініями переходів, що визначають черговість виконання дій. Графічна форма запису, звана також структурною схемою чи блок-схемою алгоритму, є зображення алгоритму як послідовності пов'язаних між собою функціональних блоків, кожен із яких відповідає виконанню однієї чи кількох дій. Надалі ми будемо використовувати блок-схеми алгоритмо в. Вони дозволяють уявити алгоритми у більш наочному вигляді, це дає можливість аналізувати їхню роботу, шукати помилки у реалізації і т.д. У блок-схемах завжди єпочатокікінець, що позначаються еліпсами, між ними - послідовністькроківалгоритму, з'єднанихстрілками.
Кроки буваютьбезумовними(зображуються прямокутниками, паралелограмами) таумовними(зображуються ромбами). З ромба завжди виходять дві стрілки - одна означає подальший шлях у разі виконання умови (позначається зазвичай словом "так" або "+"), інша - невиконання (словом "ні" або "-"). Введення з клавіатури або виведення на екран значення виразу зображується паралелограмом. Команда, що виконує обробку дій (команда присвоєння), зображується у прямокутнику.
Якщо розв'язання задачі складне і досить довге, алгоритм може вийти дуже великим. Уникнути цього можна, замінивши деяку закінчену послідовність кроків алгоритму блоками, які будуть допоміжними алгоритмами. Блок зазвичай не елементарний, його розміри вибираються в залежності від необхідності, проте якщо він правильно складений, то має всі необхідні ознакиалгоритмического кроку: має точку входу (чітко виділений початок) і може бути умовним або безумовним. Різні блоки алгоритму пов'язані один з одним тільки через точки входу та виходу, тому якщо блок правильно вирішує своє завдання, то його внутрішня структура несуттєва для решти алгоритму. Таке блочне уявлення особливо зручне перших етапах вирішення складних завдань, коли деталізація блоків виробляється пізніше і, можливо, іншими розробниками.
Мова програмування - мова, яка використовується для формального запису алгоритмів. Більшість мов програмування належать до алгоритмічних мов. Запис алгоритму алгоритмічною мовою називають програмою.Мова, що використовується для формального запису алгоритмів, називаєтьсяалгоритмічною мовою. При описі будь-якої мови (у тому числі природної, наприклад, української, англійської тощо) використовуються такі поняття:алфавіт, синтаксистасемантика.
Алфавітмови - це безліч найпростіших символів, які можуть бути використані в текстах цієї мови. Послідовність символів алфавіту називаютьсловом. Правила, за якими утворюються слова з алфавіту, називаються граматикою. Сама жмова- це безліч всіх слів, що записуються в даному алфавіті згідно з цією граматикою.
Синтаксис- це набір правил, що визначають можливі поєднання (конструкції) з літер алфавіту. Для опису синтаксису мови, як правило, використовують іншу мову (метамову) або синтаксичні діаграми.
Семантика- це набір правил, визначальних значення (сенс) окремих конструкцій мови.
Основні алгоритмічні конструкції
Найбільш зрозуміло структуру алгоритму можна уявити за допомогою блок-схеми, в якій використовуються геометричні фігури (блоки), з'єднані між собою стрілками, що вказують на послідовність виконання дій. Прийнято певні стандарти графічних зображень блоків. Наприклад, команду обробки інформації поміщають у блок, що має вигляд прямокутника, перевірку умов - у ромб, команди введення або виведення - у паралелограм, а овалом позначають початок та кінець алгоритму. Структурною елементарною одиницею алгоритму є проста команда, що означає один елементарний крок переробки чи відображення інформації. Проста команда мовою схем зображується у вигляді функціонального блоку.
 | Цей блок маєодин вхідіодинвихід. З простих команд та перевірки умов утворюються складові команди, що мають більш складну структуру і теж один вхід і один вихід. Структурний підхід до розробки алгоритмів визначає використання лише базових алгоритмічних структур (конструкцій): слідування, розгалуження, повторення, які мають бути оформлені стандартним чином. |
 | Розглянемо основні структури алгоритму. Команданаслідуванняскладається тільки з простих команд. На малюнку прості команди мають умовне позначенняS1таS2. З команд прямування утворюються лінійні алгоритми. Приклад лінійного алгоритму буде знаходження суми двох чисел, введених з клавіатури. |
 | Командарозгалуження- це складова команда алгоритму, в якій в залежності від умови Р виконується або однаS1, або іншаS2дію. З команд прямування і команд розгалуження складаються алгоритми, що розгалужуються (алгоритми розгалуження). Прикладом алгоритму, що розгалужується, буде знаходження більшого з двох чисел, введених з клавіатури. |
 | Команда розгалуження може бути повною та неповною форми. Неповна форма команди розгалуження використовується тоді, коли необхідно виконувати діюSтільки у разі дотримання умовиP. Якщо умоваPне дотримується, команда розгалуження завершує свою роботу без виконання дії. Прикладом команди розгалуження неповної форми буде зменшення удвічі лише парного числа. |
 | Командаповторення- це складова команда алгоритму, у якій залежно від умовиРможливе багаторазове виконання діїS. З команд прямування та команд повторення складаються циклічні алгоритми(Алгоритми повторення). На малюнку представлено команду повторення з передумовою. Називається вона тому, що спочатку перевіряється умова, а потім виконується дію. Причому дію виконується, доки умова дотримується. Приклад циклічного алгоритму може бути наступним. Поки з клавіатури вводяться позитивні числа, алгоритм виконує їх суми. Команда повторення з передумовою не є єдиною можливою. Різновидом команди повторення із передумовою є команда повторення із параметром. Вона використовується тоді, коли відома кількість повторень дії. У блок-схемі команди повторення з параметром умова записується над ромбі, а шестикутнику. Прикладом циклічного алгоритму із параметром буде знаходження суми перших 20 натуральних чисел. |
 | У команді повторення з умовою спочатку виконується діяSі лише потім, перевіряється умоваP. Причому дія повторюється доти, доки умова не дотримується. Прикладом команди повторення з постумовою буде зменшення позитивного числа до тих пір, поки воно невід'ємне. Як тільки число стає негативним, команда повторення закінчує свою роботу. За допомогою з'єднання лише цих елементарних конструкцій (послідовно або вкладенням) можна "збирати" алгоритм будь-якого ступеня складності. |
Кожна вказана конструкція може бути без змін у структурі реалізована будь-якою мовою програмування, наприклад, на Паскалі та Бейсику. Тому необхідно грамотно скласти алгоритм за допомогою блок-схеми, а вже потім, знаючи, як записуються команди конкретною мовою програмування, набрати програму на комп'ютері та отримати результат, запустивши її на виконання.
Лінійний алгоритм
Наведемо приклад запису алгоритму як блок-схеми, псевдокодів і мовою Паскаль. Ручне тестування та підбір системи тестів виконуються аналогічно до попереднього завдання.
Розгалужується алгоритм
Наведемо приклад запису алгоритму, що розгалужується, для знаходження найбільшого з двох чисел.
Циклічний алгоритм
Розглянемо алгоритм знаходження суми перших натуральних непарних чисел доn. Представимо запис алгоритму трьома способами: як блок-схеми, шкільного алгоритмічного мови та мовою програмування Pascal.
Блок-схема складається з наступних базових структур: дві складові команди (команда прямування та команда повторення з передумовою), далі проста команда. Усі команди з'єднані послідовно. Конструкції оформлені стандартним чином, тому їх легко розпізнати та перекласти мовою програмування. Кожна конструкція має один вхід та один вихід.
Пунктирні стрілки у таблиці відображають послідовність виконання технологічного ланцюжка. Після запису алгоритму у вигляді блок-схеми кожна команда перекладається шкільною алгоритмічною мовою, а вже потім мовою програмування.
Запишемо алгоритм обчислення суми перших n натуральних чисел. Для цього скористаємося циклом з параметром, оскільки заздалегідь відомо, скільки разів буде виконуватися команда знаходження суми. У всіх ланках ланцюжка поміняємо цикл "поки" на цикл "для" і наведемо приклад перекладу алгоритму з мови блок-схем на шкільну алгоритмічну мову та на мову програмування Pascal.
Розглянемо знаходження кількості натуральних чисел, сума яких не більша за задану. Для цього скористаємося командою повторення зпостумовою.