Приклади

Лабораторна робота № 2

Тема: Базові поняття теорії алгоритмів

Мета роботи: Отримати практичні навички складання простих алгоритмів рішення задач з обчислення числових функцій.

Форма звіту: виконання аудиторного і домашнього завдань.

Теоретична частина.

Слово "Алгоритм" походить від імені середньовічного вченого Мухаммеда ібн Муси аль-Хорезмі (787-850 гг), що жив в Середній Азії. У XVIII столітті, коли праці аль-Хорезмі були перекладені з арабської мови на латинь, його ім'я записали так: "Algorithmus", але люди винаходили алгоритми задовго до аль-Хорезмі.

Алгоритм -це зрозумілий і точний опис виконавцеві зробити певну послідовність дій, спрямованих на досягнення вказаної мети або рішення поставленої задачі, за кінцеве число кроків.

Для запису алгоритмів використовуються:

Блок-схема -поширений тип схем, що описує алгоритми або процеси, зображуючи кроки у вигляді блоків різної форми, сполучених між собою стрілками.

Складання алгоритмів графічним способом підкоряється двом ГОСТам:

1) ГОСТ 19.002-80, відповідає міжнародному стандарту ИСО 2636-73. Регламентує правила складання блок-схем.

2) ГОСТ 19.003-80, відповідає міжнародному стандарту ИСО 1028-73.

Форми представлення алгоритму

Алгоритм фіксується різними способами: на природній мові, за допомогою спеціальних схем, графічно, на алгоритмічній мові.

Приклади

Алгоритми на природній мові

1. Є два глеки місткістю 3 і 8 л. Напишіть алгоритм або просто відповідь, як можна набрати з річки 7 л води.

Рішення. Алгоритм: Наповнюєш восьмилітровий глек за допомогою трилітрового: 3+3+2. Після цього в глеку трилітровому залишається 1 літр.Виливаєш усе з восьмилітрового, переливаєш 1 літр з трилітрового, потім 3+3, у результаті - сім літрів.

2. Селянин стоїть на лівому березі річки з вовком, козою і капустою. Йому треба перевезти усе це на правий берег. Але його човен занадто малий: він може узяти тільки одного пасажира - або вовка, або капусту, або козу. Як тут поступити?

Рішення. Алгоритм:

a. Перевези козу

b. Повернутися

c. Перевези вовка, забрати козу

d. Повернутися

e. Висадити козу, перевези капусту

f. Повернутися

g. Перевези козу.

ГОСТ на опис блок-схем

Для графічного представлення алгоритму використовують певні геометричні фігури. Таке представлення називається блок-схемою. Розміри і співвідношення розмірів фігур приводяться в ГОСТ 19-002-80 і ГОСТ 19-003-80. Згідно з ними усі розміри пов'язані з двома величинами: а і в, де а - величина, кратна 5, а в обчислюється за формулою в = 1,5а, допускається в = 2а.

У січні 1992 року введений новий ГОСТ 19-701-90. Він описує, як і де слід використовувати фігури. Згідно з ним допускаються наступні символи для зображення схем.

1. Для зображення даних

1.1.

дані, що вводяться, носій даних не визначений

1.2.

/дані, що зберігаються, носій не визначений

1.3.

/дані, що зберігаються в оперативній пам'яті

1.4.

/дані, що зберігаються в пристроях, що запам'ятовують, з послідовним доступом

1.5.

/дані, що зберігаються в пристроях, що запам'ятовують, з прямим доступом

2. Для зображення документів

2.1.

/дані на носієві (машинограммы, документи для оптичного прочитування, мікрофільми, бланки введення)

2.2.

/дані, що відображуються, вводяться вручну (клавіатура, перемикачі, кнопки, світлове перо і так далі)

2.3.

/дані на паперовій стрічці

2.4.

/дані в зчитаній формі на носієві у вигляді пристрою (дисплей і так далі), що відображує

3. Для відображення дій

3.1.

/виконання операцій, групи операцій, що призводять до зміни значення, форми, їх розміщення і так далі. Блок "процес"

3.2.

/зумовлений (тобто визначений заздалегідь) процес (процедури, функції, підпрограми)

3.3.

/ручна операція - процес, що виконується людиною.

3.4.

/підготовка команди або група команд з метою дії на наступну функцію (ініціалізація)

3.5

/рішення, блок "умова"

3.6.

/виконання паралельних дій

3.7.

позначення циклу здійснюється двома блоками, усередині першого або другого позначається умова ініціалізації або умова циклу. Між ними розміщуються інші блоки

3.8.

/передача управління безпосередньо з вказівкою типу (запит, виклик, подія і так далі)

3.9. З'єднувач (міжсторінковий, міжлистовий)

до сторінки

від сторінки

Усередині використовують унікальні одні і ті ж буквені позначення

3.10.

вихід і вхід в зовнішнє середовище, блок "введення/виведення"

3.11.

/коментар

3.12.

/канал зв'язку

Поиск по сайту: