 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Алгоритми з розгалуженням
|
|
Алгоритми, в яких робиться вибір одного з декількох варіантів дій залежно від виконання деякої умови, називаються алгоритмами з розгалуженням, або умовними алгоритмами.
Умова та послідовність дій згідно цієї умови називається гілкою алгоритму.
Де починається і де закінчується кожна гілка? При виконанні умови Якщо послідовність дій в алгоритмі триває так, як вона записана, — адже ніяких підстав для її порушення немає. Де вона закінчується? Там, де закінчуються дії, передбачені умовою Якщо, тобто перед іншою умовою — Інакше.
А якщо умова Якщо не виконана? Тоді з'являються підстави для порушення послідовності дій. Потім перевірки виконання (точніше, невиконання) умови Якщо починається виконання дій, що стоять в алгоритмі після Інакше, тобто дій другої гілки.
Для зняття невизначеності в алгоритм вводять спеціальний покажчик, що відділяє гілки від продовження алгоритму. Зазвичай таким покажчиком є фраза Кінець розгалуження. Тому завершення дій будь-якої гілки потрібно відшукати фразу Кінець розгалуження і продовжити виконання алгоритму з дії, яка слідує після цієї фрази.
Розглянемо ще один алгоритм з розгалуженням. Припустимо, що потрібно зробити сортування циліндричних виробів по діаметру і розподілити їх у два магазини (ящики, коробки). Вироби поступають з конвеєра в пристрій, який вимірює їх діаметр, і залежно від результатів виміру інший пристрій поміщає виріб в той або інший магазин.
Алгоритм сортування може бути наступним:
1 Встановити виріб у вимірювальний пристрій.
2 Виміряти діаметр виробу.
3 Якщо діаметр більший за заданий, то помістити виріб в магазин № 1.
4 Інакше помістити виріб в магазин № 2.
5 Кінець галуження.
Виконавцем цього алгоритму може бути як людина, так і машина (наприклад, робот). Якщо виконання подібного алгоритму передбачається доручити машині, то треба бути упевненим, що вона не лише зрозуміє кожну команду, але і зуміє зробити вибір, тобто машина повинна мати технічні засоби, здатні визначити, чи виконана умова Якщо. У нашому випадку машина повинна не лише виміряти діаметр виробу, але і порівняти його із заданим діаметром і за результатами порівняння прийняти рішення про приміщення виробу в потрібний магазин.
У автоматичних системах, працюючих без участі людини, при виникненні різних ситуацій машині доводиться самій приймати рішення про вибір варіанту дій, тому в таких системах часто використовуються алгоритми з розгалуженням. Будь-яку ситуацію, в якій треба вибирати один з двох або декількох варіантів дій, завжди можна звести до одного або декількох розгалужень алгоритму.
2.2.3 Циклічні алгоритми
Часто ми спостерігаємо або беремо участь в процесах, в яких багато разів підряд виконуються одні і ті ж дії.
Повернемося до розгляду алгоритму сортування виробів. У цьому алгоритмі описані одноразові дії, які виконуються над одним виробом. Він відправлявся в магазин № 1 або № 2, і на цьому алгоритм закінчувався. Але реальні вироби поступають на сортування, швидше за все, у великій кількості. Значить, описані в алгоритмі дії повинні повторюватися знову і знову. Як довго? Очевидно, поки вироби є на конвеєрі.
Як змінити алгоритм, щоб процес сортування повторювався багаторазово? Які саме дії повторювати і до яких пір? Існує два варіанти:
- задати умову, при виконанні якої дії треба повторювати, а як тільки умова буде порушена - припинити повторення і перейти до продовження алгоритму (наприклад, фарбувати дошки огорожі, поки він не закінчиться, а потім приступити до обіду);
- задати необхідну кількість повторень одних і тих же дій (наприклад, налити у бочку 10 відер води).
Перший варіант більше універсальний — він підходить для забору з будь-якою кількістю дощок, у тому числі і заздалегідь невідомим. Але виконавець цього варіанту алгоритму повинен уміти проміряти виконання заданої умови (чи закінчилася огорожа?), що не важко для людини, але може виявитися важким для машини.
А ось другий варіант для машини не проблема — механічні, електричні, електронні і інші лічильники існують давно і в самих різних видах. Але цей варіант позбавлений гнучкості, і при зміні умов виконання алгоритму (наприклад, при заміні бочки на меншу) треба змінювати команди в самому алгоритмі (встановлювати іншу кількість наливаних відер).
Група дій, що повторюється в алгоритмі, утворює цикл.
Алгоритми, в яких повторюються одні і ті ж дії, називаються циклічними алгоритмами.
Коли цикл виконаний потрібна кількість разів, виконавець алгоритму переходить до подальших дій, що знаходяться вже за межами циклу.
Оскільки в алгоритмі сортування виробів кількість виробів заздалегідь невідома, скористаємося першим варіантом — спробуємо знайти умову, виконання якої потрібне для повторення процесу сортування. Такою умовою є нали-чие чергового виробу на конвеєрі. Якщо сортування виконує людина, то він легко виявить цей виріб. Якщо ж виконавець алгоритму сортування — машина, то вона повинна уміти перевіряти наявність виробу на конвеєрі. Як машина зможе це зробити, розглянемо далі. А зараз доповнимо алгоритм сортування умовою повторення циклу:
1 Поки на конвеєрі є виріб, виконувати дії:
2 Встановити виріб у вимірювальний пристрій.
3 Виміряти діаметр виробу.
4 Якщо діаметр більший за заданий, то помістити виріб в магазин № 1.
5 Інакше помістити виріб в магазин № 2.
6 Кінець галуження.
7 Кінець циклу.
Тут напівжирним шрифтом виділені рядки, от-ношение, що мають, до повторення дій, т. е. до циклу. У алгоритмі є і галуження, але воно записане світлим шрифтом.
Для того, щоб виконавцеві було зрозуміле, які саме дії треба повторювати, ці дії (цикл) мають бути якось виділені, тобто мають бути вказані межі циклу. Оскільки повторення циклу залежить від виконання заданої умови 1. Поки на конвеєрі..., рядок з цією умовою може бути одним з границь циклу. Іншу межу встановлюють рядком Кінець циклу. Якщо умова 1 дотримано, то виконуються дії 2... 6, розташовані між вказаними межами. При порушенні умови 1 виконавцю треба буде перейти до дії, що йде за рядком 7. Кінець циклу (якщо є продовження алгоритму).
У розглянутому алгоритмі перевірка умови, що визначає необхідність повторення циклу, робилася до початку виконання самих дій циклу. Але буває і так, що оцінити необхідність повторення циклу можна тільки по результату, отриманому після його виконання. Вибір того або іншого варіанта залежить від сенсу виконуваних дій.
Наприклад, при вантаженні контейнерів в залізничний вагон тільки після завантаження чергового контейнера можна визначити, чи є ще вільне місце у вагоні і чи варто продовжувати завантаження. В цьому випадку рядок з умовою повторення циклу є його нижньою межею, а верхню межу встановлюють строкою Початок циклу.
Складемо циклічний алгоритм вантаження контейнерів у вагон:
Дата публикования: 2014-12-11; Прочитано: 768 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
