|
Читайте также: |
Графічні схеми використовують для наочного зображення алгоритмів. Є два різновиди графічних схем: блок-схеми та структурні схеми.
Спочатку прийнято алгоритм формулювати словесно (письмово або в уяві), пізніше — рисувати графічну схему алгоритму, а згодом, на підставі схеми, записувати відповідну програму.
Блок-схема складається з блоків декількох видів: овальних блоків «початок» і «кінець», блоків «введення і виведення даних» у вигляді паралелограмів, прямокутних блоків «процес присвоєння» та ін. Призначення блоків випливає з їхніх назв. У блоці «процес» описують одну чи декілька команд присвоєння. Формули записують довільно (символ множення тут можна не зазначати). Блоки з'єднують лініями, які описують послідовність виконання команд. Ці лінії називають лініями потоків передавання інформації. Природні напрямки потоків: зверху— вниз і зліва—направо. Якщо напрямок потоку інший, то лінія повинна мати стрілку.
Блок-схеми алгоритмів
Наочною формою запису алгоритмів є блок-схеми, що складаються з геометричних фігур - блоків. Кожний блок відповідає певній дії. Наприклад, запис алгоритму починається і закінчується такими блоками:
 | |||
 | |||
Ці елементи називаються блоками початку і кінця алгоритму. Стрілки вказують напрямок виконання алгоритму. Блок Початок має одну вихідну стрілку, а блок Кінець - одну вхідну стрілку.
У алгоритмах часто використовуються команди введення і виведення значень. Цим командам відповідають блоки введення-виведення:
Тут лівий блок означає введення величини X, а правий блок - виведення У. За допомогою наведених вище блоків ви можете скласти найпростіший алгоритм введення величини X:
Відповідно до цього алгоритму в програму вводиться значення велцчини X Однак програма, що складається тільки з операції введення, навряд чи доцільна. Звичайно над введеною величиною виконуються певні дії, що позначаються прямокутниками (операторними) блоками, наприклад:
 |  |
У середині прямокутників записані вирази, що виконуються над величинами. Лівий блок означає присвоювання змінній X значення суми х +1. Правий блок відповідає за знаходження різниці Х-У і надання значення різниці змінній Z. Операторні блоки можуть мати кілька входів і лише один вихід.
Запишемо найпростіший алгоритм обчислення квадрата якогось числа:
Відповідно до цього алгоритму вводиться величина X, потім обчислюється квадрат цієї величини (добуток Х*Х) і виводиться отримане значення.
Усі наведені вище блоки дозволяють організувати послідовне виконання інструкцій алгоритму. Однак на практиці часто виникають ситуації, коли залежно від виконання будь-якої умови маємо змінити послідовний хід обчислень. Прикладом такої умов"и є нерівність Х> 0 в алгоритмі знаходження модуля чисті X. У схему алгоритму логічна умова вводиться за допомогою умовного блока. Цей блок прийнято зображати у вигляді ромба з одним входом і двома виходами:
 |
Якщо умова, зазначена на зображенні блока, виконується (умова має значення Істина), то відбувається перехід по стрілці Так, якщо не виконується (значення Хибність) - по стрілці Ні. Завдяки умовному блоку обчислювальний процес ніби розгалужується, тобто умовний блок використовується для організації розгалуження.
Приклад 11. Визначити, скільки метрів сітки потрібно, щоб загородити сад прямокутної форми зі сторонами 24 і 50 м, і скільки добрив треба придбати, якщо на 1 м
витрачають 2,5 кг.
Алгоритм Сад
Рис. Блок-схема алгоритму Сад
4. Властивості алгоритмів. Розглянемо такі властивості: визначеність, скінченність, результативність, правильність, формальність, масовість.
Визначеність алгоритму. Алгоритм визначений, якщо він складається з допустимих команд виконавця, які можна виконати для деяких вхідних даних.
Невизначеність, наприклад, виникне в алгоритмі 1, якщо в знаменнику буде таке: 92 - 92 (ділення на нуль недопустиме).
Невизначеність виникне, якщо деяка команда буде записана неправильно, бо така команда не належатиме до набору допустимих команд виконавця.
Скінченність або дискретність алгоритму. Виконання алгоритму розбивається на послідовність закінчених дій - кроків. Алгоритм повинен бути скінченним — послідовність команд, які потрібно виконати, має бути скінченною. Кожна команда починає виконуватися після закінчення виконання попередньої.
Результативність алгоритму. Алгоритм повинен призводити до вирішення завдання за кінцеве число кроків або висновку про неможливість вирішити задачу.
Приклад не результативного алгоритму — послідовність дій для виконання деяких обчислень, в якій пропущена команда виведення результатів на екран тощо.
Правильність алгоритму. Алгоритм правильний, якщо його виконання забезпечує досягнення мети.
Помінявши місцями валгоритмі Перехід будь-які дві команди, отримаємо неправильну послідовність дій.
Точність. Запис алгоритму повинен бути таким, щоб на кожному кроці його виконання було відомо, яку команду треба виконувати наступною.
Зрозумілість. Алгоритм повинен бути записаний на зрозумілій для виконавця мовою.
Формальність алгоритму. Алгоритм формальний, якщо його можуть виконати не один, а декілька виконавців з однаковими результатами. Ця властивість означає, що коли алгоритм застосовують до двох однакових наборів вхідних даних, то й результати мають бути однакові.
Масовість алгоритму. Алгоритм масовий, якщо він придатний для розв'язування не однієї задачі, а задач певного класу, які відрізняються лише вихідними даними.
Наприклад, алгоритм вирішення задачі про чайнику є:
- дискретним і точним (розбитий на послідовність певних кроків);
- зрозумілим і результативним (звичайно ж, програміст Білл вміє поводитися з чайником, водопровідним краном і газовою плитою!);
- масовим (так як може застосовуватися також для того, щоб закип'ятити в чайнику молоко або компот).
Приклади масових алгоритмів — загальні правила, якими користуються для множення, додавання, ділення двох багатозначних чисел, бо вони застосовні для будь-яких пар чисел. Масовими є алгоритми розв'язування математичних задач, описаних у загальному вигляді за допомогою формул. їх можна виконати для різних вхідних даних. Алгоритм, описаний у прикладі З, також масовий.
5. Базові структури алгоритму — це структури, за допомогою яких здійснюється керування процесом оброблення даних. Комбінації цих структур і створюють алгоритм для розв'язання певної задачі. Існують три базові алгоритмічні структури, або три основні типи алгоритмів: лінійний, розгалужений і циклічний.
На прикладах побутових ситуацій розглянемо три види алгоритмів: прості, розгалужені, циклічні.
5.1. Прості команди і прості алгоритми. Простими є такі команди: виконати, встати, іти, вийти тощо.
Якщо алгоритм складається лише з послідовності простих команд, то його називають простим, або лінійним.
Приклад 13. Розглянемо простий (лінійний) алгоритм Ранок.
Алгоритм Ранок
1. Встати о 7-й годині.
2. Виконати гімнастичні вправи.
3. Умитися.
4. Поснідати.
5. Вийти з дому о 8-й годині.
Лінійним (алгоритм послідовного виконання, структура слідування) називається алгоритм, що забезпечує одержання результату шляхом одноразового виконання послідовних дій, незалежно від вхідних даних і проміжних результатів. Усі команди в таких алгоритмах виконуються одна за одною, послідовно, тобто лінійно.
5.2. Алгоритми із розгалуженнями. Якщо в алгоритмі, крім простих команд, є команда, яка містить якусь умову, то такий алгоритм називається розгалуженим, або алгоритмом з розгалуженням (галуженням).
Умову в інформатиці називають логічним виразом. Команду розгалуження утворюють за допомогою логічного виразу і трьох службових слів: якщо, то, інакше. Вона має вигляд
якщо логічний вираз, то команда 1, інакше команда 2.
Дія команди. Команда розгалуження — це вказівка виконати одну з двох команд: команду 1, якщо логічний вираз істинний (справджується), або команду 2, якщо логічний вираз хибний (не справджується).
Замість команди 1 чи 2 може бути декілька команд, які називатимемо серією команд.
Приклад 14. Розглянемо алгоритм Вечір.
Алгоритм Вечір
1. Повернутися зі школи додому після уроків.
2. Пообідати.
3. Якщо погода гарна, то попрацювати в саду,
інакше піти в бібліотеку, взяти книжки,
повернутися додому.
4. Зробити уроки.
5. Повечеряти.
6. Якщо є цікава телепередача, то подивитися телевізор,
інакше почитати книжку.
7. Лягти спати.
Алгоритм Вечір складається із семи команд. Команди 3 і 6 — це команди розгалуження. Команда 3 містить серію команд. Простежимо за виконавцем алгоритму. Якщо погода гарна і є цікава телепередача, то він після уроків працюватиме в саду, зробить уроки й подивиться телевізор. Розгляньте інші ситуації самостійно.
Розгалуженим (умова, структура вибору) називається алгоритм, у якому різні дії виконуються у випадку виконання або невиконання заданої умови. Галуження буває повним і неповним. Повне галуження — це галуження, у якому різні дії визначені, як у випадку виконання, так і у випадку невиконання деякої умови. Неповне галуження — це галуження, у якому дії визначені тільки у випадку виконання (або у випадку невиконання) умови.
5.3. Циклічні алгоритми. Циклом називається процес повторення дій. Циклічні алгоритми забезпечують повторне виконання деяких команд скінченну кількість разів. Для організації циклів застосовують команду циклу, яка має такий вигляд:
доки логічний вираз, виконати команди.
Зазначені команди (чи одна команда) виконуються, доки наведений логічний вираз справджується. Тут доки - службове слово.
Приклад 15. Розглянемо циклічний алгоритм Школа.
Алгоритм Школа
1. Іти на перший урок.
2. Доки не закінчилися уроки, іти на наступний урок.
3. Іти додому.
Циклічним (цикл, структура повторення) називається алгоритм, у якому передбачене повторення деякої групи (серії) команд. За допомогою цієї структури описуються однотипні дії, що багаторазово повторюються. Такі алгоритми забезпечують виконання довгої послідовності дій, записаних порівняно короткою послідовністю команд. Саме використання циклів дозволяє повною мірою реалізувати швидкодію комп'ютерів. Існує три основні види циклів: цикл із передумовою, цикл із постумовою, цикл із покроковою зміною аргумента.
Розглянемо інші приклади команд циклу.
Приклад 16. Доки немає виходу, зробити крок уперед.
Приклад 17. Доки немає фінішу, гребти.
Приклад 18. Доки падає дощ, читати наступну сторінку.
Задача *. Скласти алгоритм наповнення водою 10-літрового відра, користуючись З-літровою байкою. Розв'язок такий:
Алгоритм Наповнення банки водою.
1. Наповнити банку водою.
2. Доки відро неповне, перелити воду з банки у відро,
наповнити банку водою.
Простежимо за виконавцем алгоритму. Прості команди (перелити та наповнити) він виконає в циклі чотири рази. Віро наповнить, у цьому випадку 2 л води проллє на землю.
Контрольні запитання:
1.Яке походження терміна «алгоритм»?
2.Що ми розуміємо під поняттям «алгоритм»?
3.Що таке допустимі команди виконавця?
4.Які є способи опису алгоритмів?
5.Які властивості повинен мати алгоритм?
6.Що означає скінченність (дискретність) алгоритму?
7.Що таке формальність алгоритму?
8.Що означає масовість алгоритму?
Практичні завдання з теми:
1.Наведіть приклади допустимих і недопустимих команд для виконавців:
а) людина;
б) робот на деякому виробництві;
в) пристрій дистанційного керування телевізором.
2.Наведіть приклади недопустимих вхідних даних для команд:
а) ділення двох чисел;
б) обчислення квадратного кореня числа.
3.Складіть алгоритм переходу вулиці на регульованому світлофором перехресті.
4.Запишіть алгоритм обчислення шляху, який долає автомобіль зі швидкістю V за час t.
5.Запишіть алгоритм обчислення площі та периметра прямокутника за двома відомими сторонами а і b.
6.Складіть алгоритм приготування улюбленої страви (наведіть кулінарний рецепт) і проаналізуйте його властивості.
7. На інший берег річки треба перевезти човном вовка, козу та капусту. Складіть алгоритм розв'язування задачі, якщо не можна залишати разом у човні чи на березі вовка і козу або козу і капусту (за один раз можна перевозити не більше одного об'єкта).
Дата добавления: 2015-02-16; просмотров: 195 | Поможем написать вашу работу | Нарушение авторских прав |