Практична робота "Побудова лінійних та розгалужених алгоритмічних процесів"

Практична робота №1

ПОБУДОВА ЛІНІЙНИХ ТА РОЗГАЛУЖЕНИХ АЛГОРИТМІЧНИХ ПРОЦЕСІВ

Мета: Навчитись складати алгоритми лінійних та розгалужених алгоритмічних процесів. Освоїти правила побудови блок-схем алгоритмів.

ТЕОРЕТИЧНІ ВІДОМОСТІ

1. Поняття алгоритму. Способи запису алгоритмів

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

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

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

Словесний спосіб описування алгоритмів орієнтований на людину-виконавця.

Блок-схеми дозволяють зобразити алгоритм в наочній графічній формі.

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

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

2. Блок-схеми алгоритмів

Таблиця 1. Деякі умовні графічні позначення елементів блок-схем алгоритмів

Назва	Призначення	Функція
Пуск-зупинка		Початок, кінець, переривання процесу обробки даних або виконання програми.
Введення-виведення		Введення або виведення даних
Процес		Виконання операцій, в результаті яких змінюється значення, форма подання або розташування даних.
Рішення		Вибір напрямку виконання алгоритму в залежності від виконання умови.
Модифікація		Організація циклічного процесу. Виконання операцій, що змінюють команди або групи команд, які змінюють програму.
Передвизначений процес		Використання раніше створених і окремо описаних алгоритмів і програм.
Коментар		Зв’язок між елементами схеми і поясненням.
З’єднувач		Вказання зв’язку між перерваними лініями потоку, що зв’язують символи.
Міжсторінковий з’єднувач		Вказання зв’язку між роз’єднаними частинами схем алгоритмів і програми, розташованими на різних листах.
Лінії зв’язку	,	Лінії, що з’єднують елементи схеми.

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

Для запису команд всередині блоків використовується природна мова з елементами математичної символіки.

Наочність схематичного представлення алгоритму має свої переваги! Однак ця наочність швидко втрачається, коли зображується великий алгоритм. В таких випадках в схемі алгоритму виділяються і відокремлюються її окремі частини – модулі, основною умовою яких є один вхід і один вихід. Згодом вони включаються у схему алгоритму як окремі блоки. Такий підхід до складання алгоритму відображає ідею структурного програмування.

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

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

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

До таких операцій відносяться дії зміни значення деяких величин, введення та виведення інформації тощо. Декілька лінійних елементів можуть об'єднуватися і утворювати складену лінійну структуру (див. рис. 1).

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

 

При виконанні операції, яка є розгалуженим елементом, виконується лише одна з дій. В тому випадку, коли умова справджується, продовження виконання алгоритму відбувається за стрілкою «+», в протилежному випадку – за стрілкою «-». Скорочена форма розгалуження у випадку невиконання умови не передбачає ніяких дій (див. рис. 2, 3).

Циклічним елементом алгоритму називається така операція, за допомогою якої здійснюється визначена кількість повторень однієї або декількох дій згідно сформульованої умови. Є два типи повторення: з передумовою та з післяумовою (див. рис. 4, 5).

4. Типи алгоритмів

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

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

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

ПОБУДОВА АЛГОРИТМІВ ЛІНІЙНИХ ОБЧИСЛЮВАЛЬНИХ ПРОЦЕСІВ

Лінійний обчислювальний процес – це такий процес, який має лінійну структуру, тобто послідовність виконання операторів у програмі лінійного обчислювального процесу – пряма, від першого до останнього оператора, записаних в основному блоці програми. Програма не може “перестрибнути” деякі оператори чи виконати їх декілька раз, – всі вони виконуються послідовно в порядку їх запису у вихідному коді.

Простою оптимізацією обчислень називають приведення математичних обчислень до виду, де не використовується піднесення до степеня. Операція піднесення до степеня займає в декілька разів більше процесорного часу, ніж, наприклад, операція множення. Отже, при наявності великої кількості піднесення до степеня у виразах, їх намагаються замінити множенням (формула Горнера).

Поліномом (багаточленом) порядку n, називається формула вигляду:

За формулою Горнера шляхом винесення за дужки спільного множника цей поліном приводиться до такого вигляду:

Тобто, починаючи з першого та другого доданків (старших), виноситься за дужки спільний множник, до якого додається наступний доданок з винесеним спільним множником. В результаті отримуємо винесення в кожному доданку змінної.

Приклад 1

Скласти блок-схему алгоритму знаходження квадрата заданого числа. Результат обрахунку вивести на екран.

Методичні рекомендації

1. У відповідності з поставленим завданням проаналізувати поставлене завдання.

Число задається в програмі, для чого можна використати змінну або константу дійсного значення. Тіло програми має містити присвоєння змінній значення (якщо аргумент оголошений як змінна) та визначення квадрата цього числа.

2. Скласти блок-схему алгоритму задачі.

Розв’язок

Блок-схема буде мати вигляд, зображений на рисунку 6.

Приклад 2

Скласти блок-схему обчислення одного значення поліному за аргументом, зчитаним з клавіатури:

Примітка: для обчислення скористатися формулою Горнера.

 

Методичні рекомендації

1. Проаналізувати поставлену задачу та перевести заданий поліном у формулу Горнера. Заданий поліном:

приводиться до наступної формули Горнера (шляхом почергового винесення за дужки спільного множника двох сусідніх елементів):

2. Скласти блок-схему алгоритму задачі.

Для вирішення поставленої задачі необхідні дві змінні: х (аргумент), у (значення поліному). Спочатку потрібно запросити у користувача введення аргументу х, знайти значення поліному за формулою Горнера, вивести результат.

Розв’язок

Блок-схема задачі буде мати вигляд, зображений на рис. 7.

ПОБУДОВА АЛГОРИТМІВ РОЗГАЛУЖЕНИХ ОБЧИСЛЮВАЛЬНИХ ПРОЦЕСІВ

Приклад 3

Скласти блок-схему алгоритму знаходження значення функції для аргументу, що вводиться з клавіатури, передбачаючи при цьому перевірку на область допустимих значень (ті значення, при яких задана функція визначена). Якщо ж аргумент не входить до області допустимих значень, вивести відповідне повідомлення.

Методичні рекомендації

Спочатку потрібно зробити запит на введення аргументу, проаналізувати його, тобто перевірити, чи належить введене значення області допустимих значень. Для даної функції аргумент повинен бути >0 (в знаменнику ), не дорівнювати 1 чи -1, оскільки при цих значеннях у виразі функції в знаменнику буде нульове значення (на 0 ділити не можна), то в таких випадках необхідно вивести відповідне повідомлення. При інших значеннях х можна знайти значення функції.

Розв’язок

Блок-схема розв'язку задачі зображена на рис 8.

Рис. 8. Блок-схема алгоритму 3

Приклад 4

Скласти блок-схему алгоритму знаходження значення наступної функції (значення аргументу – лише ціле число):

 

Розв’язок

Блок-схема розв'язку задачі зображена на рис 9.

Рис. 9. Блок-схема алгоритму 4

Завдання

Скласти блок-схеми розв’язку задач лінійних та розгалужених алгоритмів згідно варіанта.

Варіанти завдань

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

1. Скласти блок-схему алгоритму знаходження одного значення функції (див. таб.2).
2. Скласти блок-схему алгоритму знаходження одного значення поліному, попередньо привівши його до формули Горнера (див. таб.2).

Таблиця 2. Варіанти завдань

№	Функція	№	Функція
1		14
2		15
3		16
4		17
5		18
6		19
7		20
8		21
9		22
10		23
11		24
12		25
13

 

Розгалужуючі алгоритми

Рівень А

Побудувати блок-схему алгоритму згідно варіанта (див. таб.3)

Таблиця 3. Варіанти завдань

№	Завдання
1	Знайти, чи належить зчитане значення проміжку, межі якого також зчитуються з клавіатури.
2	Знайти максимальне значення серед трьох, зчитаних з клавіатури.
3	Визначити, чи належать одній координатній четверті дві точки, координати яких зчитуються з клавіатури.
4	Визначити, чи всі чотири попередньо зчитані числа є парними.
5	За зчитаним значенням довжини сторін прямокутника А, В та радіусом кола R визначити, чи поміститься це коло в прямокутник.
6	Перевірити, чи є зчитане значення кратним числу, яке також зчитане з клавіатури.
7	Обрахувати швидкість руху потягу за зчитаним значенням відстані та часу та вивести її у одному з вибраних користувачем варіанті: км/год або миль/год.
8	За зчитаним значенням координат точок X, У, визначити, якій координатній четверті ця точка належить.
9	Визначити, чи всі чотири попередньо зчитані числа є додатними.
10	За зчитаним значенням відстані L між двома містами та швидкістю двох велосипедистів V1, V2, визначити, котрий з них прибуде до кінцевого пункту швидше і наскільки часу, при умові одночасного виїзду з початкового пункту.
11	Зчитати з клавіатури значення суми до сплати умовного товару (дійсне значення) та вивести окремо гривні та копійки з відповідними підписами: грн. та коп.
12	За зчитаними координатами трьох точок визначити радіус найбільшого кола серед тих, які проходять через зазначені точки з центром в середині координат.
13	Визначити, чи є стандартною зчитана назва марки монітору і якщо так  то вивести повну назву фірми- виробника (стандартними вважати назви: LG, SAMSUNG, SONY, NOKIA).
14	Визначити податок з заробітної плати, нарахована сума якої зчитується з клавіатури, при умові таких ставок податків: до 300 грн. - 9%, до 700 грн. - 12%, до 1000 - 15%, більше 1000 - 20%.
15	Знайти мінімальне значення серед трьох, зчитаних з клавіатури.
16	За зчитаним значенням координат точок X, У, визначити, якій координатній четверті ця точка належить.
17	Перевірити, чи є зчитане значення кратним числу, яке також зчитане з клавіатури.
18	Обрахувати швидкість руху потягу за зчитаним значенням відстані та часу та вивести її у одному з вибраних користувачем варіанті: км/год або миль/год.
19	Визначити, чи всі чотири попередньо зчитані числа є парними.
20	За зчитаним значенням довжини сторін прямокутника А, В та радіусом кола R визначити, чи поміститься це коло в прямокутник.
21	Знайти, чи належить зчитане значення проміжку, межі якого також зчитуються з клавіатури.
22	Знайти максимальне значення серед трьох, зчитаних з клавіатури.
23	Визначити, чи належать одній координатній четверті дві точки, координати яких зчитуються з клавіатури.
24	Визначити податок з заробітної плати, нарахована сума якої зчитується з клавіатури, при умові таких ставок податків: до 300 грн. - 9%, до 700 грн. - 12%, до 1000 - 15%, більше 1000 - 20%.
25	За зчитаними координатами трьох точок визначити радіус найбільшого кола серед тих, які проходять через зазначені точки з центром в середині координат.

Рівень Б

Знайти значення функції, параметри якої - а,b,с та аргумент х вводяться з клавіатури. Варіанти завдань представлені в таблиці 4.

Таблиця 4. Варіанти завдань

№	Функція	№	Функція
1		14
2		15
3		16
4		17
5		18
6		19
7		20
8		21
9		22
10		23
11		24
12		25
13

Рівень В

Визначити, чи належить точка з координатами (X, У), які зчитуються з клавіатури, області, яка зображена на малюнку (заштрихована область).

 

 

Варіант 1  Варіант 2

 

 

 Варіант 3 Варіант 4

 

 

 

Варіант 5 Варіант 6

             

Варіант 7 Варіант 8

               

 Варіант 9 Варіант 10

    

Варіант 11 Варіант 12

           

 

 Варіант 13 Варіант 14

               

Варіант 15

Висновки

1. Алгоритм – це скінчена чітка послідовність дій, спрямованих на досягнення поставленої мети або розв’язування задач певного типу.
2. Існує чотири способи запису алгоритмів, вибір яких залежить від того, хто його записує або на кого він орієнтований: словесний, описування алгоритмів за допомогою блок-схем, описування алгоритмів мовою псевдокодів, описування алгоритмів мовою програмування.
3. Блок-схеми дозволяють зобразити алгоритм в наочній графічній формі.
4. Будь-який алгоритм можна побудувати за допомогою трьох базових структурних елементів: лінійного, розгалуженого та циклічного.

ВИМОГИ ДО ЗВІТУ

У звіті з практичної роботи повинні бути відображені:

1. Тема, мета практичної роботи.
2. Короткі теоретичні відомості з теми.
3. Завдання практичної роботи.
4. Блок-схеми алгоритмів розв’язку задач.
5. Висновок.

КОНТРОЛЬНІ ЗАПИТАННЯ

1.      Що таке алгоритм?
2.      Які способи запису алгоритму Ви знаєте?
3.      Назвіть базові структури алгоритмів, типи алгоритмів.
4.      Назвіть всі відомі Вам методи вводу/виводу інформації.
5.      Чому в програмах замінюють піднесення до степеня множенням?
6.      Що таке лінійний обчислювальний процес?
7.      Що таке формула Горнера і коли вона використовується?
8.      Що таке розгалуження і коли вони зустрічаються?