до виконання лабораторної роботи №1
для студентів очної форми навчання спеціальності 010500 «Математичне забезпечення й адміністрування інформаційних систем»
Рекомендовано кафедрою «Інформатика та програмне забезпечення» БГТУ (протокол №4 від 15.02.10)
У цій ЛР студенти знайомляться з поняттям алгоритму, його властивості та способами запису. Формуються навички запису алгоритмів у вигляді блок-схем і діаграм Насс - Шнейдермана.
Мета роботи - вивчити основні способи запису алгоритмів. Для цього студент повинен:
· Вивчити поняття алгоритму і виконавця;
· Вивчити умовні позначення в блок-схемах;
· Вивчити умовні позначення в структурограммах;
Тривалість роботи - 2 години.
Алгоритм - послідовність чітко визначених дій, виконання яких веде до вирішення завдання. Алгоритм, записаний на мові машини, є програма рішення задачі.
Алгоритм - це сукупність дій, що призводять до досягнення результату за кінцеве число кроків.
1. Дискретність - це розбиття алгоритму на ряд окремих закінчених дій (кроків).
2. детермінованість (від лат. Determinate - визначеність, точність) - будь-яка дія алгоритму має бути строго і недвозначно визначено у кожному випадку.
3. Кінцівка - кожна дія окремо і алгоритм в цілому повинні мати можливість завершення.
4. Масовість - алгоритм повинен бути застосований до різних наборів вихідних даних.
5. Результативність - алгоритм повинен призводити до достовірного вирішення.
Прикладами алгоритмів можуть бути:
· Інструкція до приладу;
· Опис маршруту та ін.
Розрізняють три основних види алгоритмів:
Лінійний алгоритм - це алгоритм, в якому дії виконуються одноразово і строго послідовно.
Прикладом лінійного алгоритму може бути послідовність дій при приготуванні бутерброда. Алгоритм в цьому випадку буде виглядати наступним чином:
2. відрізати хліб;
3. намазати хліб маслом;
4. відрізати ковбасу;
5. покласти ковбасу на хліб;
Всі дії виконуються послідовно один за одним в певному порядку і призводять до кінцевого результату.
Розгалужується алгоритм - це алгоритм, в якому в залежності від умови виконується або одна, або інша послідовність дій.
Найпростіший приклад реалізації разветвляющегося алгоритму - якщо на вулиці йде дощ, то необхідно взяти парасольку, інакше не брати парасольку з собою.
Циклічний алгоритм - це алгоритм, команди якого повторюються певну кількість разів поспіль.
Найпростіший приклад реалізації циклічного алгоритму - при читанні книги будуть повторюватися одні й ті ж дії: прочитати сторінку, перегорнути і т.д.
Циклічні алгоритми трьох видів:
· Цикл з лічильником - дії всередині циклу виконуються певну кількість разів;
· Цикл з передумовою - перед кожним новим проходом циклу перевіряється певну умову, якщо воно істинне, дії всередині циклу виконуються, в іншому випадку відбувається вихід з циклу;
· Цикл з умовою поста - на початку відбувається виконання дій усередині циклу, а тільки потім перевірка умови.
Форми запису алгоритму:
· Словесна або вербальна (мовна, формульно-словесна);
· Псевдокод (формальні алгоритмічні мови);
o структурограмми (схеми Насс-Шнайдерман);
o графічна (блок-схеми).
Зазвичай спочатку (на рівні ідеї) алгоритм описується словами, але в міру наближення до реалізації в неї з'являються все більш формальні обриси і формулювання мовою, зрозумілою виконавцю (наприклад, машинний код).
Приклад словестного записи алгоритму наведено раніше при розгляді лінійного алгоритму. Прикладом записи алгоритму за допомогою псевдокоду є код будь-якої програми на будь-якій мові програмування (С ++, Pascal, Basic і ін.).
Способи схематичною запису алгоритмів детально розглядаються далі.
Правила виконання схем визначаються наступними документами:
· ГОСТ 19.701-90. Схеми алгоритмів, програм, даних і систем. Умовні позначення і правила виконання.
Дані документи зокрема регулюють способи побудови схем і зовнішній вигляд їх елементів.
Основні елементи схем алгоритму
Елемент відображає вхід із зовнішнього середовища або вихід з неї (найбільш часте застосування - початок і кінець програми). Усередині фігури записується відповідна дія.
Блок обчислень (обчислювальний блок)
Виконання однієї або кількох операцій, обробка даних будь-якого виду (зміна значення даних, форми подання, розташування). Усередині фігури записують безпосередньо самі операції, наприклад, операцію присвоювання: a = 10 * b + c.
Логічний блок (блок умови)
Символ відображає виконання процесу, що складається з однієї або декількох операцій, який визначений в іншому місці програми (в підпрограмі, модулі). Усередині символу записується назва процесу і передані в нього дані. Наприклад, в програмуванні - виклик процедури або функції.
Перетворення даних у форму, придатну для обробки (введення) або відображення результатів обробки (висновок). Даний символ не визначає носія даних (для вказівки типу носія даних використовуються специфічні символи).
Символ складається з двох частин - відповідно, початок і кінець циклу - операції, що виконуються всередині циклу, розміщуються між ними. Умови циклу і збільшення записуються всередині символу початку або кінця циклу - в залежності від типу організації циклу. Часто для зображення на блок-схемі циклу замість цього символу використовують символ умови, вказуючи в ньому рішення, а одну з ліній виходу замикають вище в блок-схемі (перед операціями циклу).
Опис інших елементів схем можна знайти у відповідних ГОСТ (вказані вище).
Розглянемо приклад побудови блок-схеми алгоритму рішення повного квадратного рівняння. Для початку запишемо алгоритм у вербальній формі:
5. Висновок рівняння на екран;
6. Обчислення дискримінанту за формулою;
7. Якщо вивести повідомлення про відсутність коренів і перейти до кроку 10, інакше перейти до кроку 8;
8. Якщо. єдиний корінь рівняння обчислити за формулою. вивести його на екран і перейти до кроку 10. В іншому випадку перейти до кроку 9.
9. Обчислити корені рівняння за формулами
вивести результати на екран, перейти до кроку 10.
При побудові блок-схеми будуть використовуватися наступні елементи:
1. Початок і кінець -
2. Введення і виведення даних -
Послідовність дій задається керуючими стрілками, що зв'язують блоки, всередині графічних елементів записується відповідна команда.
Блок схема алгоритму наведена на Рис. 1.
Рис.1. Блок-схема алгоритму обчислення коренів квадратного рівняння
Далі розглядається інший спосіб графічного запису алгоритму - за допомогою діаграми Насс-Шнейдермана.
Діаграма Насс-Шнейдермана (структурограмми)
Діаграма Насс-Шнейдермана - це графічний спосіб представлення структурованих алгоритмів і програм, розроблений в 1972 році американськими аспірантами Беном Шнейдерманом і Айзеком Насс.
Діаграми Насс-Шнейдермана мають ряд переваг перед блок-схемами при розробці структурованих алгоритмів і програм:
· Запис є більш компактною (в першу чергу за рахунок відсутності стрілок між елементами).
· Гарантоване дотримання принципів структурного програмування дотримані (при використанні блок-схем можна випадково отримати неструктурований алгоритм, якщо бути неуважним).
· Діаграми Насс - Шнейдермана зручніше використовувати для покрокової деталізації завдання, так як вони теж будуються за принципом покрокової деталізації - спочатку діаграма являє собою один прямокутник (вихідна задача), потім в ньому малюється деяка структура управління, в якій є кілька прямокутників (подзадач вихідної завдання ), і далі з кожним прямокутником (підзадачею) може бути виконана та ж операція.