У цій статті будуть розглянуті приклади блок-схем, які можуть зустрітися вам в підручниках з інформатики та іншій літературі. Блок-схема являє собою алгоритм, щодо якого вирішується яка-небудь завдання, поставлене перед розробником. Спочатку потрібно відповісти на питання, що таке алгоритм, як він представляється графічно, а найголовніше – як його вирішити, знаючи певні параметри. Потрібно відразу зазначити, що алгоритми бувають декількох видів.
Що таке алгоритм?
Це слово ввів в ужиток математик Мухаммед аль-Хорезмі, який жив у період 763-850 року. Саме він є людиною, який створив правила виконання арифметичних дій (а їх всього чотири). А ось ГОСТ від 1974 року, який свідчить, що:
Алгоритм – це точний припис, що визначає обчислювальний процес. Причому є кілька змінних із заданими значеннями, які призводять розрахунки до шуканого результату.
Алгоритм дозволяє чітко вказати виконавцю виконувати строгу послідовність дій, щоб вирішити поставлену задачу і отримати результат. Розробка алгоритму – це розбивання однієї великої задачі на якусь послідовність кроків. Причому розробник алгоритму зобов’язаний знати всі особливості і правила його складання.
Особливості алгоритму
Всього можна виділити вісім особливостей алгоритму (незалежно від його виду):
- Присутня функція введення початкових даних.
- Є висновок якогось результату після завершення алгоритму. Потрібно пам’ятати, що алгоритм потрібен для того, щоб досягти певної мети, а саме – отримати результат, який має пряме відношення до вихідним даним.
- У алгоритму повинна бути структура дискретного типу. Він повинен представлятися послідовними кроками. Причому кожен наступний крок може початися тільки після завершення попереднього.
- Алгоритм повинен бути однозначним. Кожен крок чітко визначається і не допускає довільного трактування.
- Алгоритм повинен бути кінцевим – необхідно, щоб він виконувався за строго певну кількість кроків.
- Алгоритм повинен бути коректним – задавати виключно вірне рішення поставленої задачі.
- Спільність (або масовість) – він повинен працювати з різними вихідними даними.
- Час, який дається на рішення алгоритму, має бути мінімальним. Це визначає ефективність вирішення поставленого завдання.
А тепер, знаючи, які існують блок-схеми алгоритмів, можна приступити до розгляду способів їх запису. А їх не дуже багато.
Словесна запис
Така форма, як правило, застосовується при описі порядку дій для людини: «Піди туди, не знаю куди. Принеси те, не знаю що».
Звичайно, це жартівлива форма, але суть зрозуміла. В якості прикладу можна навести ще, наприклад, звичну запис на стеклах автобусів:«При аварії висмикнути шнур, видавити скло».
Тут чітко ставиться умова, при якому потрібно виконати дві дії в строгій послідовності. Але це найпростіші алгоритми, існують і більш складні. Іноді використовуються формули, спецобозначения, але за обов’язкової умови – виконавець повинен розуміти.
Допускається змінювати порядок дій, якщо необхідно повернутися, наприклад, до попередньої операції або обійти якусь команду при певному умови. При цьому команди бажано нумерувати і обов’язково вказується команда, до якої відбувається перехід: «Закінчивши всі маніпуляції, повторюєте пункти 3-5».
Запис у графічній формі
У цьому записі беруть участь елементи блок-схем. Всі елементи стандартизовані, у кожної команди є певна графічна запис. А конкретна команда повинна записуватися всередині кожного з блоків звичайною мовою або математичними формулами. Всі блоки повинні з’єднуватися лініями – вони показують, який саме порядок у виконуваних команд. Власне, цей тип алгоритму більш підходить для використання в програмному коді, ніж словесний.
Запис на мовах програмування
У тому випадку, якщо алгоритм необхідний для того, щоб завдання вирішувала програма, встановлена на комп’ютері, його потрібно записувати спеціальним кодом. Для цього існує безліч мов програмування. І алгоритм у цьому випадку називається програмою.
Блок-схеми
Блок-схема – це подання алгоритму в графічній формі. Всі команди і дії представлені геометричними фігурами (блоками). Всередині кожної фігури вписується вся інформація про ті дії, які потрібно виконати. Зв’язку зображені у вигляді звичайних ліній зі стрілками (при необхідності).
Для оформлення блок-схем алгоритмів є ГОСТ 19.701-90. Він описує порядок та правила створення їх в графічній формі, а також основні методи рішення. У цій статті приведені основні елементи блок-схем, які використовуються при вирішенні завдань, наприклад, з інформатики. А тепер давайте розглянемо правила побудови.
Основні правила складання блок-схеми
Можна виділити такі особливості, які повинні бути у будь-який блок-схеми:
- Обов’язково має бути два блоки – «Початок» і «Кінець». Причому в одиничному екземплярі.
- Від початкового блоку до кінцевого повинні бути проведені лінії зв’язку.
- З усіх блоків, крім кінцевого, повинні виходити лінії потоку.
- Обов’язково повинна бути нумерація всіх блоків: зверху вниз, зліва направо. Порядковий номер потрібно проставляти у лівому верхньому куті, роблячи розрив накреслення.
- Всі блоки повинні бути пов’язані один з одним лініями. Саме вони повинні визначати послідовність, з якою виконуються дії. Якщо потік рухається знизу вгору, справа наліво (іншими словами, в зворотному порядку), то обов’язково малюються стрілки.
- Лінії поділяють на вихідні і вхідні. При цьому потрібно відзначити, що одна лінія є для одного блоку виходить, а для іншого входить.
- Від початкового блоку в схемі лінія потоку тільки виходить, так як він є найпершим.
- А ось у кінцевого блоку є тільки вхід. Це наочно показано на прикладах блок-схем, які є в статті.
- Щоб простіше було читати блок-схеми, вхідні лінії зображуються зверху, а вихідні знизу.
- Допускається наявність розривів на лініях потоку. Обов’язково вони позначаються спеціальними з’єднувачами.
- Для полегшення блок-схеми дозволяється всю інформацію прописувати в коментарях.
Графічні елементи блок-схем алгоритмів для вирішення представлені у таблиці:
Лінійний тип алгоритмів
Це найпростіший вид, який складається з певної послідовності дій, вони не залежать від того, які дані вписані спочатку. Є кілька команд, які виконуються одноразово і тільки після того, як буде зроблена попередня. Лінійна блок-схема виглядає таким чином:
Причому зв’язки можуть йти як зверху вниз, так і зліва направо. Використовується така блок-схема для запису алгоритмів обчислень за простими формулами, у яких немає обмежень на значення змінних, що входять у формули для розрахунку. Лінійний алгоритм – це складова частина складних процесів обчислення.
Розгалужуються алгоритми
Блок-схеми, побудовані за таким алгоритмом, є більш складними, ніж лінійні. Але суть не змінюється. Розгалужений алгоритм – це процес, в якому подальша дія залежить від того, як виконується умова і яке виходить рішення. Кожне напрям дії – це гілка.
На схемах зображують блоки, які називаються «Рішення». У нього є два виходи, а всередині прописується логічна умова. Саме від того, як воно буде виконане, залежить подальший рух за схемою алгоритму. Можна розділити розгалужуються алгоритми на три групи:
- «Обхід» – при цьому одна з гілок не має операторів. Іншими словами, відбувається обхід кількох дій іншої гілки.
- «Розгалуження» – кожна гілка має певний набір виконуваних дій.
- «Множинний вибір» – це розгалуження, в якому є кілька гілок і кожна містить у собі певний набір виконуваних дій. Причому є одна особливість – вибір напрямку безпосередньо залежить від того, які задані значення виразів, що входять в алгоритм.
Це прості алгоритми, які вирішуються дуже просто. Тепер давайте перейдемо до більш складним.
Циклічний алгоритм
Тут все гранично зрозуміло – циклічна блок-схема представляє алгоритм, в якому багаторазово повторюються однотипні обчислення. За визначенням, цикл – це певна послідовність дій, що виконується багато разів (більше ніж один раз). І можна виділити кілька типів циклів:
- У яких відоме число повторень дій (їх ще називають циклами з лічильником).
- У яких число повторень невідомо – з постумовою і передумовою.
Незалежно від того, який тип циклу використовується для вирішення алгоритму, у нього обов’язково повинна бути присутня змінна, за допомогою якої відбувається вихід. Саме вона визначає кількість повторень циклу. Робоча частина (тіло) циклу – це певна послідовність дій, яка виконується на кожному кроці. А тепер більш детально розглянемо всі типи циклів, які можуть зустрітися при складанні алгоритмів і вирішенні завдань з інформатики.
Цикли з лічильниками
На малюнку зображена проста блок-схема, в якій є цикл з лічильником. Такий тип алгоритмів показує, що заздалегідь відома кількість повторень даного циклу. І це число фіксовано. При цьому змінна, яка вважає число кроків (повторень), так і називається – лічильник. Іноді в підручниках можна зустріти інші визначення – параметр циклу, керуюча змінна.
Блок-схема наочно ілюструє, як працює цикл з лічильником. Перш ніж приступити до виконання першого кроку, потрібно присвоїти початкове значення лічильника – це може бути будь-яке число, воно залежить від конкретного алгоритму. У тому випадку, коли кінцеве значення менше величини лічильника, почне виконуватися певна група команд, які складають тіло циклу.
Після того, як тіло буде виконано, лічильник змінюється на величину кроку лічильника, позначену буквою h. У тому випадку, якщо значення, яке вийде, буде менше кінцевого, цикл триватиме. І закінчиться лише тоді, коли кінцеве значення буде меншим, ніж лічильник циклу. Тільки в цьому випадку відбудеться виконання того дії, яке слід за циклом.
Зазвичай в позначеннях блок-схем використовується блок, який називається «Підготовка». У ньому прописується лічильник, а потім вказуються такі дані: початкове і кінцеве значення, крок зміни. На блок-схемі це параметри I н, Ik і h відповідно. У тому випадку, коли h=1, величину кроку не записують. В інших випадках робити це обов’язково. Необхідно дотримуватися простого правила – лінія потоку повинна входити зверху. А лінія потоку, яка виходить знизу (або праворуч, залежно від конкретного алгоритму), повинна показувати перехід до наступного оператору.
Тепер ви повністю вивчили опис блок-схеми, зображеної на малюнку. Можна перейти до подальшого вивчення. Коли використовується цикл з лічильником, потрібно дотримувати певні умови:
- У тілі не дозволяється змінювати (примусово) значення лічильника.
- Заборонено передавати управління ззовні оператору тіла. Іншими словами, ввійти в цикл можна тільки з його початку.
Цикли з передумовою
Цей тип циклів застосовується в тих випадках, коли кількість повторень заздалегідь невідомо. Цикл з передумовою – це тип алгоритму, в якому безпосередньо перед початком виконання тіла здійснюється перевірка умови, при якому допускається перехід до наступного кроку. Зверніть увагу на те, як зображуються елементи блок-схеми.
У тому випадку, коли умова виконується (твердження істинно), відбувається перехід на початок тіла циклу. Безпосередньо в ньому змінюється значення хоча б однієї змінної, яка впливає на значення поставленого умови. Якщо не дотримуватися цього правила, отримаємо «зациклення». У тому випадку, якщо після наступної перевірки умови виконання тіла циклу виявляється, що воно хибне, то відбувається вихід.
У блок-схемах алгоритмів допускається здійснювати перевірку не істинність, а хибності початкової умови. При цьому з циклу відбудеться вихід тільки в тому випадку, якщо значення умови виявиться істинним. Обидва варіанти правильні, їх використання залежить від того, якою конкретно зручніше використовувати для вирішення тієї чи іншої задачі. Такий тип циклу має одну особливість – тіло може не виконатися в випадку, коли умова помилкова або істинним (в залежності від варіанту, який застосовується для розв’язання алгоритму).
Нижче наведено блок-схему, яка описує всі ці дії:
Що таке цикл з післяумовою?
Якщо уважно придивитися, то цей вид циклів чимось схожий на попередній. Самостійно побудувати блок-схему, що описує цей цикл, ми зараз і спробуємо. Особливість полягає в тому, що невідомо заздалегідь число повторень. А умова задається вже після того, як стався вихід з тіла. Звідси видно, що тіло, незалежно від рішення, буде виконуватися як мінімум один раз. Для наочності погляньте на блок-схему, що описує виконання умови та операторів:
Нічого складного в побудові алгоритмів з циклами немає, достатньо у них тільки один раз розібратися. А тепер перейдемо до більш складних конструкцій.
Складні цикли
Складні – це такі конструкції, всередині яких є один або більше простих циклів. Іноді їх називають вкладеними. При цьому ті конструкції, які охоплюють інші цикли, називають «зовнішніми». А ті, які входять в конструкцію зовнішніх – внутрішніми. За виконання кожного кроку зовнішнього циклу відбувається повна прокрутка внутрішнього, як представлено на рисунку:
Ось і все, ви розглянули основні особливості побудови блок-схем алгоритмів для вирішення, знаєте принципи і правила. Тепер можна розглянути конкретні приклади блок-схем з життя. Наприклад, у психології такі конструкції використовуються для того, щоб чоловік вирішив якесь питання:
Або приклад з біології для вирішення поставленого завдання:
Рішення задач з блок-схемами
А тепер розглянемо приклади завдань з блок-схемами, які можуть попастися в підручниках інформатики. Наприклад, задана блок-схема, за якою вирішується якийсь алгоритм:
При цьому користувач самостійно вводить значення змінних. Припустимо, х=16, а у=2. Процес виконання такої:
- Проводиться введення значень х і у.
- Виконується операція перетворення: х=√16=4.
- Виконується умова: у=у2=4.
- Виробляється обчислення: х=(х+1)=(4+1)=5.
- Далі обчислюється наступна змінна:=(у+х)=(5+4)=9.
- Виводиться рішення: у=9.
На цьому прикладі блок-схеми з інформатики добре видно, як відбувається алгоритму рішення. Потрібно звернути увагу на те, що значення х та у задається на початковому етапі вони можуть бути будь-якими.
