Характерною особливістю базових структур є наявність у них одного входу і одного виходу.
1. Базова структура "слідування". утворюється послідовністю
дій, наступних одне за іншим:
У лінійному алгоритмі команди виконуються послідовно, одна за одною. Прикладом лінійного алгоритму може служити алгоритм заварки чаю:
закип'ятити воду
сполоснути заварювальний чайник гарячою водою
насипати заварку
залити заварку окропом
закрити чайник чим-небудь теплим
почекати 5 хвилин
... тепер можна пити чай
Лінійний алгоритм переходу через дорогу:
1. Підійти до пішохідного переходу
2. Переконатися що не має машин праворуч
3. Перейти половину дороги
4. Переконатися що немає машин зліва
5. Перейти половину дороги
Що буде якщо на дорозі є світлофор?
2. Базова структура "розгалуження". Забезпечує в залежності від результату
перевірки умови (так чи ні) вибір одного з альтернативних шляхів роботи алгоритму.
Кожен з шляхів веде до загального виходу, так що робота алгоритму триватиме незалежно від того, який шлях буде обраний. Структура розгалуження існує в двох основних варіантах:
• якщо-то;
• якщо-то-інакше;
У розгалуженому алгоритмі порядок проходження команд може бути різний залежно від того, яке навколишнє оточення. Прикладом розгалуженя алгоритму може служити алгоритм переходу вулиці:
1. підійти до пішохідного переходу
якщо є світлофор, то
{
2. чекати зеленого світла
3. перейти вулицю
}
інакше
{
4. Переконатися що немає машин праворуч
5. Перейти половину дороги
6. Переконатися що немає машин ліворуч
7. Перейти половину дороги
}
Розпишемо 4 і 6 кроки детальніше.
1. підійти до пішохідного переходу
якщо є світлофор, то
{
2. чекати зеленого світла
3. перейти вулицю
}
інакше
{
4. подивитися праворуч.
Якщо машин немає, то
{
5. перейти половину дороги,
}
інакше,
{
6. чекати, поки вони проїдуть,
7. перейти половину дороги.
}
8. подивитися ліворуч,
Якщо машин немає, то
{
9. перейти дорогу до кінця,
}
інакше,
{
10. чекати, поки вони проїдуть,
11. перейти дорогу до кінця.
} }
Завдання по темі:
Розділ Boolean: 1, 2, 6, 9,16, 18, 20
3. Базова структура "цикл".
Забезпечує багаторазове виконання деякої сукупності дій, що називається тілом циклу. Основні різновиди циклів, це цикл з передумовою, цикл з пост умовою і цикл з параметром. Два останніх типи циклів ми розглянемо пізніше, а поки більш детально познайомимося з основною циклічною структурою, за допомогою якої ми в основному і будемо вирішувати завдання - цикл з передумовою (цикл типу ПОКИ).
У циклічному алгоритмі деякі дії повторюються кілька разів (в інформатиці кажуть, що виконується цикл). Виникає питання чому не можна просто багато раз підряд переписати команди, які потрібно виконувати в циклі? По-перше, це незручно, по-друге, громіздко, особливо при великій кількості необхідних повторів, а по-третє, це головне, ми не завжди знаємо заздалегідь скільки саме кроків нам доведеться виконати для конкретних значень вхідних даних. Замість цього число кроків обмеженого деякою умовою - як кажуть умовою виходу з циклу.
| /* Число кроків невідомо,,
але обмежено умовою*/
покласти колоду на козли
намітити місце розрізання
поки поліно не відвалиться
{
пиляти від себе
пиляти на себе
}
покласти поліно в стіс
|
Приклад такого циклу - алгоритм розпилювання колоди: ми не можемо заздалегідь сказати, скільки разів нам треба провести пилкою від себе і на себе - це залежить від щільності дерева, якості пилки і наших зусиль. Однак ми точно знаємо, що треба закінчити роботу, коли чергове відпиляне поліно впаде на землю.
Перехід через дорогу з використанням циклу:
1. підійти до пішохідного переходу
якщо є світлофор, то
{
Поки (немає зеленого світла)
{
2. стояти
}
3. перейти вулицю
}
інакше
{
4. подивитися праворуч.
Якщо машин немає, то
{
5. перейти половину дороги,
}
інакше,
{
Поки (тобто машини)
{
6. стояти
}
7. перейти половину дороги.
}
8. подивитися ліворуч,
Якщо машин немає, то
{
9. перейти дорогу до кінця,
}
інакше,
{
Поки (тобто машини)
{
10. стояти
}
11. перейти дорогу до кінця.
}
}
2 Програми
Людина здатна розуміти сенс команди і часто може «додумати», що від нього хотіли навіть тоді, коли команда задана неточно. Для того, щоб алгоритм був зрозумілий роботові, комп'ютеру або іншій машині, недостатньо лише написати команди, треба ще й оформити алгоритм у такому вигляді, в якому його розуміє машина, тобто записати в формальному вигляді.
У формальному записі алгоритму можна використовувати тільки ті команди, які входять в СКІ виконавця. Крім того, треба дотримуватися спеціальних правил оформлення, які дозволять виконавцю розпізнати команди і визначити послідовність їх виконання.
/* Це назва алгоритму*/
/ * Ця дужка позначає початок алгоритму*/
посадити ріпку/* команд а закінчується знаком
;*/
виростити ріпку;
намагатися витягти ріпку;
покликати Бабку; намагатися витягти ріпку;
покликати Внучку; намагатися витягти ріпку;
покликати Жучку; намагатися витягти ріпку;
покликати Кішку; намагатися витягти ріпку;
покликати Мишку; витягнути ріпку;
/* Тут алгоритм закінчується */
Виконавцем для цього алгоритму є дід - саме він повинен виконувати ці команди.
4 Правила запису алгоритмів для комп'ютерів
Алгоритм можна записати різними способами і навіть на різних мовах. Хоча при цьому виконавець може, звичайно, їх не зрозуміти. Ви знаєте, що є спеціальні види виконавців алгоритмів - комп'ютери. Вони виконують програми.
¨ Програма - це алгоритм, записаний у формі, зрозумілій комп'ютеру.
Існують спецяльні правила запису програм для комп'ютерів. На малюнку вгорі сторінки їх характерні елементи виділені в рамках:
1.будь-який алгоритм має назву;
2.алгоритм починається з відкриваючої фігурної дужки "{" і закінчується закриваючою фігурною дужкою "}"; команди, розташовані між цими дужками, називаються тілом алгоритму;
3. в алгоритм можуть входити тільки ті команди, які є в СКІ виконавця;
4. кожна команда закінчується знаком ";", який позначає кінець команди;
5. для того, щоб нам було легше розбиратися в програмах, використовують коментарі - текстові пояснення, які починаються знаками / * і закінчуються знаками * /; виконавець не звертає уваги на коментарі в алгоритмі.
Незалежно від того, на якій мові програмування буде написана програма, алгоритм розв'язання будь-якої задачі на ЕОМ може бути складений з команд:
• проходження, включає в себе:
• присвоювання;
• введення;
• висновок;
• цикл;
• розгалуження;
• звернення до допоміжного алгоритму.
Практика.
Дано три цілих числа: A, B, C. Перевірити істинність висловлювання: «Справедливо подвійне нерівність A <B <C».
Дано три цілих числа: A, B, C. Перевірити істинність висловлювання: «Рівно два з чисел A, B, C є позитивними».
Дано два числа. Вивести більше з них.
Дано три числа. Знайти суму двох найбільших з них.
Лекція 2. "Формальне представлення алгоритмічних структур, ч.2"
● структура "цикла";
● цикл з передумовою;
● цикл з марнослівністю;
● цикл з параметром.
