Алгоритми та виконавці
| 1. /ALGORITM.DOC | Алгоритми та виконавці |
Алгоритми та виконавці
1. Алгоритми та виконавці 3
Що таке алгоритм? 3
Стародавні завдання 5
Які бувають алгоритми? 5
Завдання про перевізника 7
Ханойські вежі (рекурсивні алгоритми) 8
2. Виконавець Робот 10
Середа Робота 10
Основні команди Робота 10
Проста програма (завдання z1-3.maz) 11
Які помилки можуть бути у Робота? 11
Робота в системі Виконавці 11
Що таке цикл (завдання z2-3.maz)? 14
Правила використання оператора циклу 14
Вкладені цикли (завдання z3-3.maz) 15
4. Алгоритми із зворотним зв'язком 16
Що таке зворотний зв'язок і навіщо він потрібний? 16
Як Робот використовує зворотний зв'язок? 16
Цикл з умовою 17
Правила використання циклу поки що 17
5. Умовний оператор 21
Що таке умовний оператор (завдання z5-3.maz)? 21
Правила використання умовного оператора 22
Скорочена форма 22
Що таке складні умови (завдання z6-3.maz)? 23
Правила використання складних умов 23
6. Змінні та арифметичні вирази 25
Навіщо потрібні змінні (завдання z7-3.maz)? 25
Що таке змінна? 26
Оголошення змінних 26
Правила роботи зі змінними 27
Арифметичні вирази 28
Цикл з параметром 29
7. Діалогові програми 31
Що таке діалогова програма? 31
Виведення на екран (завдання z8-3.maz) 31
Правила використання оператора виведення 32
Правила використання операторавведення 33
Обчислення з циклами 34
Навіщо потрібні процедури? 36
Як ввести нову команду (завдання z10-3.maz)? 37
Правила використання процедур 39
Процедури з параметрами (завдання z11-3.maz) 40
Правила використання процедур з параметрами 41
9. Методи складання програм 43
Метод “згори донизу” 43
Метод “знизу вгору” 43
Комбінований спосіб 44
Приклад складання програми 44
Виконавець Черепаха 50
Як працює Черепаха? 50
Які команди розуміє Черепаха? 50
Як керувати Черепахою? 50
Як розфарбувати малюнок? 50
Вкладені цикли 53
Процедури з параметрами 56
11. Виконавець Кресляр 66
Прямокутна система координат 66
Як керувати Креслярем? 66
Використання процедур 68
Процедури з параметрами 69
Цикли та змінні 70
Порівняння Кресляря та Черепахи 72
Змінні та використання пам'яті 72
Цикл з параметром 74
1.Алгоритми та виконавці
Що таке алгоритм?
"Перш ніж щось зробити, треба скласти план", - говорила Аліса з казки Льюїса Керролла. І в житті ми весь час складаємо плани наших дій, наприклад, уранці більшість із нас діє за таким планом:
вийти з дому до школи чи на роботу
У такому вигляді можна записати план для того, щоб заварити чай, зробити бутерброд з ковбасою, купити собі морозиво, вимити брудні руки, …
В інформатиці план дій називаютьалгоритмом. Алгоритм складається з окремих кроків - команд. Жодну з них не можна пропустити, найчастіше ніякі команди не можна змінитимісцями (що при цьому станеться?).
До кожного кроку цього алгоритму можна запропонувати докладніший план. Наприклад, для дії “поснідати”:
з'їсти бутерброд із чаєм
І тут кожен крок, у свою чергу, теж можна розшифрувати – скласти докладніший план. Де зупинитися? Відповідь проста – це залежить від виконавця, того, хто виконуватиме цей алгоритм. Треба зупинитись на такому плані, в якому виконавцю буде зрозуміло, як виконати кожен крок.
Що таке виконавець?
Виконавці часто зустрічаються у казках. В одній із них Іван-Царевич каже Хатці-На-Курих-Ніжках: “Хатинка, хатинко! Устань до лісу задом, до мене передом!”. При цьому команда повинна бути задана дуже точно, щоб виконавець її зрозумів. У казці “Алі-Баба та сорок розбійників” чарівні двері відчинялися за командою “Сезам, відчинися!”. Жадібний Касим, який таємно проник у печеру, забув цю фразу і не зміг вийти з печери.
І Хатинка-На-Курих-Ніжках, і чарівні двері мають багато спільного: вони вміють розуміти і виконувати деякі точно задані команди, тобтовиконавцями.
- Виконавець –це той, хто вміє розуміти та виконувати деякі команди.
- Середовище виконавця –це предмети, які оточують виконавця і з якими він працює.
- Список (абосистема) Команд Виконавця (СКІ) –набір команд, зрозумілих виконавцю. Виконавець може виконати лише команди, які входять до його СКІ.
- люди:учень, робітник, вчитель, бригада;
- тварини:дресирована собака (санітар, розшукова, мисливська), кішка;
- машини:верстати, роботи, комп'ютери;
Людина як виконавецьвідрізняється від решти виконавців декількома ознаками, наприклад:
- Розуміє команди в різних варіантах (наприклад “Сядь!”, “Сідай!”, “Присядь!”).
- Виконуючи команди, «додумує» їх з урахуванням свого досвіду.
- Може відмовитись виконувати команду, якщо вона йому не подобається (“Їж манну кашу!”, “Постріли у вікно з рогатки!”). Тобто людина має волю і відповідає за свої дії.
- Алгоритм –це точно певний план дій виконавця, спрямований на вирішення якогось завдання. У алгоритм можна включати лише команди, які є у СКІ виконавця.
Робота виконавця не завжди відбувається гладко – іноді трапляються помилки. Існує три види помилок виконавців.
| “НЕ РОЗУМІЮ” | Заданої команди немає у списку команд виконавця, і він її не зрозумів. Ймовірно, ми помилилися у записі тексту команди. |
| “НЕ МОЖУ” | Виконавець зрозумів команду, але не може її виконати. Наприклад, робота дана команда “вперед”, а попереду стоїть стінка, і він не може йти. Або собаці скомандували "Сидіти!", А вона вже сидить. |
| ЛОГІЧНІ ПОМИЛКИ | Виконавецьзрозумів команду та виконав її, але зробив не те, що ми від нього хотіли. Причина цього – наша помилка у складанні завдання (алгоритму). |
Введемо тепер нового виконавця, якого назвемо дядько Федір (як у Е. Успенського). Щоб запровадити нового виконавця треба:
- задатисередувиконавця - клас, столи, стільці;
- скластиСКІ:
- ВСТАНЬ
- СЯДЬ
- ПІДНИМИ РУКУ
- ОПУСТИ РУКУ
- ПРИГНИ
- МЯУКНІ
- визначити, як передаються команди виконавцю (голосом, жестом, письмово, по рації чи якось інакше);
- визначити, як виконавець виконує команди;
- визначити, у яких випадках виникає помилка “НЕ МОЖУ”.
Переправа. Селянину треба переправити через річку вовка, козу та капусту. Але крім людини човен вміщує лише вовка, або козу, або капусту. Залишити на березі без нагляду вовка з козою чи козу з капустою не можна (з'їдять!). Як селянинові переправити свій вантаж?
Переправа сім'ї. Батько, мати та двоє дітей хочуть переправитися через річку. Всі вміють веслувати, але човен витримує або одного дорослого або двох дітей. Як їм усім переправитися на інший берег?
Фальшиві монети. З 9 монет однакової гідності одна фальшива (легша). Як її знайти за два зважування за допомогою чашкових ваг без гирь?
Які бувають алгоритми?
У лінійному алгоритмі команди виконуються послідовно, одна одною. Прикладом лінійного алгоритму може бути алгоритм заварювання чаю:
сполоснути заварювальнийчайник гарячою водою
залити заварку окропом
закрити чайник чимось теплим
зачекати 5 хвилин
. тепер можна пити чай
У алгоритмі, що розгалужується, порядок прямування команд може бути різний в залежності від того, яка навколишня обстановка. Прикладом алгоритму, що розгалужується, може бути алгоритм переходу вулиці:
підійти до пішохідного переходу
якщо є світлофор, то
чекати зеленого світла
чекати, поки зліва не буде машин
перейти вулицю до середини
чекати, поки справа не буде машин
перейти другу половину вулиці
У циклічному алгоритмі деякі дії повторюються кілька разів (в інформатиці говорять, що виконується цикл ). Існують два види циклічних алгоритмів. В одному з них ми знаємо заздалегідь, скільки разів треба зробити ці дії, в іншому ми повинні зупинитися лише тоді, коли виконається певна умова.
Прикладомциклу першого типує наше життя в робочі дні (від понеділка до суботи) – ми виконуємо 6 разів майже одні й ті самі дії.
Прикладцикла другого типу– алгоритм розпилювання колоди: ми не можемо заздалегідь сказати, скільки разів нам треба провести пилкою від себе та на себе – це залежить від густини дерева, якості пили та наших зусиль. Однак ми достеменно знаємо, що треба закінчити роботу, коли чергове відпиляне поліно впаде на землю.
/* Кількість кроків відома */
повторити 6 разів
пограти у футбол
/* програма на неділю */
/* Число кроків невідоме,
але обмежена умовою */
покласти колоду на козли
намітити місце розпилу
поки поліно не відвалиться
покласти поліно в ліску
Людина здатнарозуміти сенс команди і часто може «додумати», що від нього хотіли навіть тоді, коли команда неточна. Для того, щоб алгоритм був зрозумілий роботу, комп'ютеру чи іншій машині, недостатньо тільки написати команди, треба ще й оформити алгоритм у такому вигляді, в якому його розуміє машина, тобто записати у формальному вигляді.
У формальному записі алгоритму можна використовувати лише команди, які входять у СКІ виконавця. Крім того, треба дотримуватися спеціальних правил оформлення, які дозволять виконавцю розпізнати команди та визначити послідовність їх виконання.
Ріпка/* це назва алгоритму */
/* ця дужка позначає початок алгоритму */
посадити ріпку /* команда закінчується знаком ;*/
намагатися витягнути ріпку;
покликати Бабку; намагатися витягнути ріпку;
покликати Внучку; намагатися витягнути ріпку;
покликати Жучку; намагатися витягнути ріпку;
покликати Кішку; намагатися витягнути ріпку;
покликати Мишку; витягнути ріпку;
>/* тут алгоритм закінчується */
Виконавцем цього алгоритму є дід — саме він має виконувати ці команди.
Правила запису алгоритмів для комп'ютерів
Давно відома старовинна задача про селянина, якому треба перевезти на інший берег річкивовка,козуікапустуна човні, в яку міститься сам селянин і наодне вільне місце він може взяти або вовка, або козу, або капусту. Складність у тому, що коза і вовк поводяться пристойно лише у присутності селянина, за його відсутності коза з'їсть капусту, а вовк з'їсть козу.
Коли селянин їде на інший берег вперше, він може взяти козу, бо тільки вовк та капустаможуть залишитися наодинці.
Потім він повертається і бере із собою вовка (або капусту – другий варіант рішення). Але він не може залишити вовка (або капусту) з козою на іншому березі і тому змушений взяти із собою козу назад.
Повернувшись і висадивши козу, він забирає вовка (чи капусту) і перевозить його. Тепер на іншому березі знову залишаться вовк із капустою і селянину залишиться лише забрати козу.
| Перевіз-1 |