типи алгоритмів

В алгоритмах команди записуються один за одним в певному порядку. Виконуються вони не обов'язково в записаної послідовності: в залежності від порядку виконання команд можна виділити три типи алгоритмів:

• лінійні алгоритми;
• алгоритми з ветвлениями;
• алгоритми з повтореннями.

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

Наприклад, лінійним є наступний алгоритм посадки дерева:

1) викопати в землі ямку;
2) опустити в ямку саджанець;
3) засипати ямку з саджанцем землею;
4) полити саджанець водою.

За допомогою блок-схеми даний алгоритм можна зобразити так:

Алгоритми про ветвлениями

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

Логіку прийняття рішення можна описати так:

ЯКЩО <условие> ТО <действия 1> ІНАКШЕ <действия 2>

• ЯКЩО хочеш битьздоров. ТО закаляйся, ІНАКШЕ болю весь день на дивані;
• ЯКЩО низько ластівки літають, ТО буде дощ, ІНАКШЕ дощу не буде;
• ЯКЩО уроки вивчені, ТО йди гуляти, ІНАКШЕ вчи уроки.

В деяких випадках <действия 2> можуть бути відсутні;

ЯКЩО <условие> ТО <действия 1>

• ЯКЩО назвався грибом, ТО лізь у кошик.

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

Зобразимо у вигляді блок-схеми послідовність дій учня 6 класу Мухіна Васі, яку він уявляє собі так: "Якщо Павлик будинку, будемо вирішувати завдання з математики. В іншому випадку слід зателефонувати Марині і разом готувати доповідь з біології. Якщо ж Марини немає вдома, то треба сісти за твір. "

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

З трьох монет однакової гідності одна фальшива (легша). Як її знайти за допомогою одного зважування на чашкових вагах без гир?

Алгоритми з повтореннями

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

Форма організації дій, при якій виконання однієї і тієї ж послідовності команд повторюється, поки виконується деяка заздалегідь встановлений умова, називається циклом (повторенням).

Алгоритм, що містить цикли. називається циклічним алгоритмом або алгоритмом з повтореннями.

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

Розглянемо приклад з математики.

Натуральне число називають простим, якщо воно має тільки два дільника: одиницю й саме це число1.

2, 3, 5, 7 - прості числа; 4, 6, 8 - немає. У III столітті до нашої ери грецький математик Ератосфен запропонував наступний алгоритм для знаходження всіх простих чисел, менших заданого числа n:

1) виписати всі натуральні числа від 1 до n;
2) викреслити 1;
3) підкреслити найменше з невідмічених чисел;
4) викреслити все числа, кратні підкресленому на попередньому кроці;
5) якщо в списку є невідмічені числа, то перейти до кроку 3, інакше все підкреслені числа - прості.

Це циклічний алгоритм. При його виконанні повторення кроків 3-5 відбувається, поки у вихідному списку залишаються невідмічені числа.

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

Нагадаємо, що число 1 не відносять ні до складових (які мають більше двох дільників), ні до простих чисел.

Залежно від порядку виконання команд можна виділити три типи алгоритмів:

> Лінійні алгоритми;
> Алгоритми з ветвлениями;
> Алгоритми з повтореннями.

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

Запитання і завдання

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

Перефразіруйтеінформаціюо професіях за допомогою слів «ЯКЩО. ТО »/

8. Згадайте, герої яких українських народних казок роблять вибір, який визначає їх долю.
9. З 9 монет однакової гідності одна фальшива (легша). За скільки зважувань на чашкових вагах без гир ви можете її визначити?
10. Яка форма організації дій називається повторенням?
11. Наведіть приклад алгоритму, що містить повторення.
12. У яких відомих вам літературних творах має місце циклічна форма організації дій?
13. Де виявиться виконавець, який виконав 16 раз поспіль наступну групу команд?

пройти 10 метрів вперед

повернути на 90 ° за годинниковою стрілкою

14. Яку групу дій і скільки разів слід повторити при вирішенні наступного завдання?

Сорок солдат підійшли до річки, по якій на човні катаються двоє хлопчиків. Як солдатам переправитися на інший берег, якщо човен вміщує тільки одного солдата або двох хлопчиків, а солдата і хлопчика вже не вміщає?

15. Згадайте завдання про обчислювачів, котрий уміє тільки множити на 2 і додавати 1. Розробляти для нього раціональні алгоритми буде значно простіше, якщо скористатися наступною блок-схемою:

Використовуючи цю блок-схему, розробіть раціональні алгоритми отримання з числа 0 чисел 1024 і 500.

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

Якщо ви хочете побачити інші коригування та побажання до уроків, дивіться тут - Освітній форум.