Розвилка

Лінійні алгоритми

Базові структури алгоритмів.

Кін

Кц

вивод "S = ", S

Логічна структура будь-якого алгоритму може бути представлена комбінацією трьох основних алгоритмічних структур (ОАС): слідування, розгалуження, цикл.

У складніших випадках використовуються суперпозиції (вкладення) ОАС.

Нижче приведені графічні позначення (позначення на блок-схемах) ОАС.

Структура “слідуванняе”	Повнарозвилка	Неповнарозвилка
Цикл с передумовою(цикл ПОКИ)	Цикл с постумовою(цикл ДО)	Цикл с параметром

На схемах СЕРІЯ позначає один або декілька будь-яких операторів; УМОВА є логічний вираз (ЛВ) (якщо його значення ІСТИНА, перехід відбувається по гілці ТАК, інакше — по НІ). На схемі циклу з параметром використані позначення: ПЦ — параметр циклу, ПЗ — початкове значення параметра циклу, КЗ — кінцеве значення параметра циклу, К — крок зміни параметра циклу.

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

У прикладах ми використовуватимемо запис алгоритмів за допомогою блок-схем і словесний опис.

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

Приклад 1. Пішохід йшов по перетнутій місцевості. Його швидкість руху по рівнині v1 км/ч, в гору — v2 км/ч і під гору — v3 км/ч. Час руху відповідно t1, t2 і t3 ч. Який шлях пройшов пішохід?

1. Ввести v1, v2, v3, t1, t2, t3. 2. S1:= v1 * t1. 3. S2:= v2 * t2. 4. S3:= v3 * t3. 5. S:= S1 + S2 + S3. 6. ВивестизначенняS. 7. Кінець.

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

Приклад 2. Дано натуральне тризначне число n, в записі якого немає нулів. Скласти алгоритм, який повертає значення ІСТИНА, якщо вірне твердження: "число n кратне кожній своїй цифрі", і БРЕХНЯ — інакше.

1. Ввести число n 2. A:= n mod 10 {разряд одиниць} 3. B:= n div 100 {разряд сотень} 4. C:= n div 10 mod 10 {десятки} 5. L:= (n mod A=0) and (n mod B=0) and (n mod C=0) 6. ВиведенняL 7. Кінець

На приведеній вище схемі DIV і MOD відповідно операції ділення без остачі і отримання залишку від цілочисельного ділення. У фігурних дужках записані пояснення (коментарі) до операторів.

Досить часто та або інша дія має бути виконана залежно від значення логічного виразу, що виступає як умова. У таких випадках використовується розвилка.

Приклад 1. Обчислити значення функції

1. Ввести x. 2. Якщоx_12, B> y:=_x^2 3. Якщоx<0, то y:=x^4 4. y:= x–2 5. Вивестиy 6. Кінець

При тестуванні алгоритмів з розвилкою необхідно підбирати такі початкові дані, щоб можна було перевірити всі гілки. У приведеному вище прикладі повинно бути принаймні три тестові набори.

Приклад 2. Дано натуральне число n. Якщо число непарне і його подвоєння не приведе до виходу за 32767 (двобайтове ціле число із знаком), подвоїти його, інакше — залишити без зміни.

Щоб задовольнити умові подвоєння, число n має бути непарним і менше 16384.

1. Ввести число n 2. Якщочисло n непарне і меньше 16384, то n:= n * 2 3. Виведення n 4. Кінець

Розглянутий приклад ілюструє неповну розвилку. Також слід зазначити, тут логічний вираз, що є умовою, містить 2 операнди.

Дата добавления: 2014-01-07