Поняття алгоритму

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

Слово алгоритм походить від algorithmi - латинської форми написання імені великого математика IХ ст. аль-Хорезмі, який сформулював правила виконання арифметичних дій. Спочатку під алгоритмами розуміли тільки правила виконання чотирьох арифметичних дій над багатозначними числами. Надалі це поняття почали використовувати взагалі для позначення послідовності дій, що призводять до рішення поставленої задачі.

Приклад 1.

Обчислити значення по формулі у = (ах + b)(сх - p), для будь-якого значення х.

Щоб вирішити цю задачу, досить виконати послідовність наступних дій:

1) помножити a на х, результат позначити R1;

2) R1 скласти з b, результат позначити R2;

3) помножити c на х, результат позначити R3;

4) від R3 відняти p, результат позначити R4;

5) помножити R2 на R4, вважати результат за значення y.

Ця послідовність є| алгоритмом рішення поставленої задачі. Для людини, що виконує дії, вже необов'язково знати початкову формулу для обчислення значення y. Потрібно всього лише чітко слідувати вказаній послідовності, виконуючи її пункт за пунктом.

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

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

Приклад 2.

Знайти найбільший загальний дільник двох натуральних чисел m і n.

Складемо алгоритм рішення цієї задачі, заснований на властивості, якщо m > n, то найбільший загальний дільник чисел m, n такий же, як і чисел m - n.

Алгоритм буде таким:

1) якщо числа рівні, то взяти будь-яке з них за відповідь, інакше продовжити виконання алгоритму;

2) визначити більше з чисел;

3) замінити більше число різницею більшого і меншого чисел;

4) почати алгоритм спочатку.

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

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

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

Приклад 3.

Побудувати графік функції у = а|х| при а> 0.

Алгоритм побудови має наступний вигляд (рисунок 1.1):

Рисунок 1.1. Алгоритм побудови графіка функції у = а|х|

Для його реалізації необхідно виконати наступні дії:

1) накреслити графік функції — пряму;

2) стерти частину графіка лівіше за вісь ординат;

3) симетрично відобразити частину графіка, що залишилася, відносно осі ординат.

Приклади алгоритмів показують, що запис алгоритму поділяється на окремі вказівки виконати деяку закінчену дію. Кожна така вказівка називається командою. Команди алгоритму виконуються одна за одною. На кожному кроці виконання алгоритму виконавцеві точно відомо, яка команда повинна виконуватися наступною.

Почергове виконання команд алгоритму за кінцеве число кроків приводить до рішення задачі (досягнення мети).

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

Сукупність команд, які можуть бути виконані виконавцем, називається системою команд виконавця.

Приклад 4.

Розглянемо поняття алгоритму:

обчислення суми елементів вектора а = (a₁, a₂,..., а_n), тобто .

Для визначення суми застосуємо алгоритм її накопичення, використовуючи рекурентне співвідношення

S_i: = S_i-1 + a_i; S₀ = 0; i: = 1, 2,..., n.

де S_i - поточне значення суми;

S_i-1 - попереднє її значення;

S₀ - початкове значення суми;

a_i - значення поточного елементу вектора.

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

Алгоритм обчислення суми запишемо у вигляді такої послідовності вказівок:

1. Привласнити S значення 0 і перейти до п. 2.

2. Привласнити i значення 1 та перейти до п. 3.

3. Обчислити нове значення суми, додавши а_і, до її попереднього значення, тобто, S: = S + a_i та перейти до п. 4.

4. Збільшити значення i на 1, тобто i = i + 1, та перейти до п. 5.

5. Порівняти значення i та n: якщо i £ n, то перейти до п. 3,
інакше - до п. 6.

6. Вивести результат S, тобто суму елементів вектора а.

Алгоритм має такі основні властивості:

· детермінованість (визначеність) - однозначність результату обчислювального процесу при заданих початкових даних;

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

· масовість - забезпечення рішення будь-якої задачі з класу однотипних;

· результативність - забезпечення отримання результату через кінцеве число кроків.

3. Схеми алгоритмів

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

Прикладом словесного опису алгоритму є приведене вище обчислення суми елементів вектора.

Запис алгоритму алгоритмічною мовою вимагає точного дотримання правил певної мови, оскільки він має бути зрозумілим не тільки людині, а і комп'ютеру. Такий спосіб надання алгоритму буде розглянутий далі під час вивчення мови програмування Visual Basic (VB).

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

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

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

Ці фігури з'єднуються між собою лініями потоку, які указують наступні можливі кроки. Усередині фігури дається опис відповідного етапу, якщо він не є дуже громіздким. Інакше такий опис приводиться в збільшенні до схеми, а замість нього у відповідної фігури записується номер. Біля фігури можуть бути деякі зауваження, пояснення.

Символам привласнюють порядкові «номери», які проставляються в розриві лінії контуру в лівій частині верхньої сторони зображення символу. Лінії потоку проводять паралельно лініям зовнішньої рамки схеми. Напрями ліній потоку зверху вниз і зліва направо прийнято називати основними, якщо вони не мають зломів. Стрілками їх можна не позначати. У інших випадках напрям обов'язково позначають стрілкою. Лінію потоку, як правило, підводять до середини символу.

Відстань між паралельними лініями потоку має бути не меншою 3 мм, між символами - не меншою 5 мм. Лінію потоку можна обривати, використовуючи на місці обриву з'єднувачі, якщо схема виконана на двох і більше листах, або якщо символи, які з'єднуються, розташовані на значній відстані один від одного. Запис усередині символу або поряд з ним потрібно виконувати машинописом з одним інтервалом або креслярським шрифтом.

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

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

У таблиці 1.1 наведені символи, які часто використовуються в схемах алгоритмів.

Таблиця 1.1. Символи, які часто використовуються в схемах алгоритмів

№ з/п	Назва символу	Графічне зображення	Функції символу
1.	Процес		Виконання операцій або групи дій.
2.	Умова		Вибір напряму виконання алгоритму або програми в залежності умови.
3.	Введення-виведення		Введення або виведення необхідних даних.
4.	З'єднувач		Позначення зв'язку між перерваними лініями потоків.
5.	Початок-кінець		Початок, кінець, переривання процесу обробки даних або виконання програми.
6.	Коментар		Пояснення до елементів схеми, або процесу.
7.	Лінія потоку		Позначення послідовності зв'язку.

Розмір а повинен вибиратися з ряду 10, 15. 20 мм. Допускається збільшувати розмір а на число кратне 5. Розмір b = 1, 5 а.

Більш детально з правилами виконання схем алгоритмів та символами, що в них використовуються можна ознайомитись в ГОСТ 19.701-90.

Розглянемо детально процес побудови схеми алгоритму.

Рисунок 1.2. Схема алгоритму визначення суми елементів вектору а

Приклад 5.

Є масив цілих чисел, організованих у формі вектора а. Кількість елементів вектору - n. Визначити суму S елементів вектору а.

Словесний опис алгоритму представлений вище (див. Приклад 4). Схема алгоритму зображена на рисунку 1.2. Пояснимо її:

1. Схема починається з символу «Початок-кінець». Кожен обчислювальний процес має початок. Це відображається на схемі. Усередині символу записується слово «Початок».

2. Спочатку дані вводяться в пам'ять комп'ютера. Для позначення цієї операції використовується символ «Введення - виведення», усередині якого записуються слово «Введення». Вектор а, його вимірність n.

3. Сумі привласнюється початкове значення, яке дорівнює нулю (S = 0). Це означає пересилку 0 в область пам'яті, призначену для накопичення суми. Операція на схемі відображається символом «Процес». Прийняте позначення суми S розшифровується символом «Коментар».

4. Індекс i, що визначає порядковий номер елементу, має значення 1. При i = 1 відбувається звернення до першого елементу вектора.

5. До суми S (на першому кроці i = 1, S = 0 і а = а₁) додається значення елементу вектора а_i (S = S + a_i). В області пам'яті S записується нове значення суми.

6. Із збільшенням значення i на 1 (i = i + 1) визначається порядковий номер чергового елементу вектора. Для цього використовується символ «Процес».

7. Кількість елементів вектора рівна n. Отже, операція накопичення елементів вектору S = S + а_i повторюватиметься n разів, для чого здійснюється перевірка: продовжувати обчислення суми чи ні. Для вибору напряму обчислень застосовується символ " Умова".

Усередині нього указується перевірка i £ n. Якщо i не перевищило максимального значення n, то операція обчислення суми повторюється (перехід до символу 5), інакше виводиться отримана сума S (перехід до символу 8).

8. Здійснюється виведення результату S. Ця операція відображається на схемі символом «Введення-виведення», усередині якої записуються слово «Вивід» і позначення суми S.

Схема закінчується символом «Початок-кінець», у середині якого записується слово «Кінець».

Для кожного символу в розриві контуру приводиться його порядковий номер. Слова «Так» і «Ні» в символі «Умова» розміщуються праворуч від лінії потоку або над нею, що визначають напрям дії в залежності від результату логічного виразу в символі.

4. Графічне зображення різних видів обчислювальних процесів

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

· лінійні;

· розгалужені;

· циклічні.

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

4.1. Графічне зображення лінійних обчислювальних процесів

Рисунок 1.3. Схема алгоритму обчислення значення виразу у = (ах + b)(сх - p)

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

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

· введення початкових даних;

· обчислення за формулами;

· виведення результату.

На рисунку 1.3 зображена схема алгоритму лінійного обчислювального процесу значення виразу у = (ах + b)(сх - p). Алгоритм рішення цієї задачі розглянуто в Прикладі 1.

4.2. Графічне зображення розгалужених обчислювальних процесів

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

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

«Так» - умова виконана;

«Ні» - умова - не виконана.

Умова вказується усередині символу «Умова».

4.3. Графічне зображення циклічних обчислювальних процесів

Для більшості обчислювальних процесів характерною є повторення блоку дій.

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

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

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

Розрізняють три види циклів:

· з перед - умовою;

· з пост - умовою;

· з параметром.

Перші два види циклів використовуються тоді, коли заздалегідь невідома кількість повторень (рисунки 1.4, 1.5).

Рисунок 1.4. Схема циклу з перед - умовою

Рисунок 1.5. Схема циклу з пост - умовою

У циклі з перед - умовою спочатку перевіряється умова (звідси і назва - цикл з перед - умовою) і, якщо умова виконується, то здійснюється дія. Потім знову перевіряється умова і так далі. Виконання циклу припиняється, коли умова перестає виконуватися. Для цього необхідно, щоб дія в циклі впливала на зміну умови. Інакше відбудеться " зациклення" - нескінченне виконання циклу. Воно є типовою помилкою у разі використання циклів.

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

Рисунок 1.6. Схема циклу з параметром

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

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

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

Приклад 6.

Побудувати схему алгоритму визначення максимального елемента вектора а і його порядкового номера. Вектор а складається з n елементів.

Ідея алгоритму полягає в тому, що максимальний елемент вектора визначається після послідовного порівняння елементів. Береться перша пара елементів і виявляється більший з них. Потім його порівнюють з черговим елементом і так далі. Кожного разу визначають, який з елементів є більшим, і, крім того, запам'ятовують його порядковий номер. Схема алгоритму показана на рисунку 1.7.

Рисунок 1.7. Схема алгоритму визначення максимального елементу вектора а та його порядкового номера

Контрольні завдання по темі

1. Теоретичні питання

1. Які основні властивості алгоритмів?

2. Які основні способи опису алгоритмів?

3. Як зображається базова структура лінійного алгоритму?

4. Як зображається базова структура розгалуженого алгоритму?

5. Як зображається базова структура циклічного алгоритму?

6. Які існують види циклічних алгоритмів?

7. У чому різниця між циклами з пост - умовою і перед - умовою?

Тести

1. Алгоритм - це:

а) вказівка на виконання дій;

б) система правил, що описує послідовність дій, які необхідно виконати для вирішення завдання;

в) процес виконання обчислень, що приводять до рішення задачі;

г) немає правильної відповіді.

2. Скільки видів обчислювальних процесів існує:

а) 2; б) 3; в) 4; г) 5.

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

а) лінійний; б) розгалужений;

в) вибірковий; г) циклічний.

4. Вкажіть властивості алгоритму:

а) інформативність; дискретність; масовість; оперативність;

б) визначеність; дискретність; масовість; оперативність;

в) визначеність; дискретність; масовість; циклічність;

г) визначеність; дискретність; масовість; результативність.

5. Скільки основних властивостей має алгоритм?

а) 2; б) 3; в) 4; г) 5.

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

а) лінійним; б) багатократним;

в) розгалуженим; г) циклічним.

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

а) лінійним; б) багатократним;

в) розгалуженим; г) циклічним.

8. Лінії, що сполучають фігури (символи) в схемі алгоритму і проведені паралельно лініям зовнішньої рамки називаються:

а) лініями зв'язку; б) лініями потоків;

в) сполучними лініями; г) стрілками.

9. Лінії потоків в схемі алгоритму називаються основними, якщо вони проведені:

а) зліва направо і не мають зломів;

б) справа наліво і не мають зломів;

в) у будь-якому напрямі паралельно зовнішній рамці;

г) із стрілками.

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

а) містить один або декілька циклів;

б) не містить логічних умов і має одну гілку обчислень;

в) містить одне або декілька логічних умов;

г) жодна характеристика не підходить.

11. Циклічний алгоритм:

а) містить один або декілька циклів;

б) не містить логічних умов і має одну гілку обчислень;

в) містить одну або декілька логічних умов;

г) жодна характеристика не підходить.

12. Розгалужений (що гілкується) алгоритм:

а) містить один або декілька циклів;

б) не містить логічних умов і має одну гілку обчислень;

в) містить одну або декілька логічних умов;

г) жодна характеристика не підходить.

13. Схема алгоритму – це:

а) послідовність виконання дій для вирішення завдання і досягнення мети;

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

в) словесний опис послідовності виконання дій для вирішення завдання і досягнення мети;

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

14. Програма – це:

а) система правил, що описує послідовність дій які необхідно виконати для вирішення завдання;

б) вказівка на виконання дій із заданого набору;

в) послідовність команд, що реалізує алгоритм рішення задачі;

г) область зовнішньої пам'яті для зберігання текстових, числових даних і іншої інформації.

3. Практичні завдання

Надати словесний опис та побудувати схему алгоритму:

1. Знаходження остатку від ділення числа а на число в.

2. Розкладення числа а на прості множники.

3. Підрахування кількості літер «а» у заданому слові.

4. Знаходження матриці С, що є сумою двох матриць та .

5. Отримання нової послідовності з 0 і 1, де всі парні елементи даної послідовності замінити 0, а всі непарні елементи даної послідовності замінити 1.

6. Визначення номера найменшого елементу в послідовності .

7. Визначення " щасливого" квитка. (Квиток називається щасливим, якщо сума перших цифр номера квитка дорівнює сумі останніх цифр.) Номер квитка 10-ти значне число.

8. Перевірки, чи належить крапка М(х, у) фігурі заданій системою нерівностей: (координати точки М задані).

9. Обчислення суми , при умові, що a –константа.

10. Обчислення ідеальної маси людини за формулами де, а і b константи, а – зріст людини в см, b – вік в роках.

11. Розрахунку середнього арифметичного елементів з парними номерами набору .

Створення макросів для автоматизації дій, які найбільш часто використовуються
(практичне заняття)

При роботі з додатками пакету Microsoft Office іноді необхідно виконувати декілька разів послідовність декількох команд (дій). Таку послідовність дій можна записати на вбудованій макромові. Такий алгоритм називається макросом. Його можна виконувати всякий раз, коли необхідно виконати дане завдання. Подальший запуск макросу викликає повторення команд. Такі макроси можливо поділити на дві групи.

Перша група: макрос створюється автоматично за допомогою вбудованого макрорекордеру, який переводе Ваші дії у додатку на макромову і зберігає макрос.

Друга група: користувач створює макрос самостійно, знаючи макромову.

Отже, Макрос - це послідовність команд і функцій, що зберігаються в модулі Visual Basic.

Розглянемо різні способи створення та управління макросами першої групи.

1. Створення та управління макросами першої групи

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

Всі кроки і команди, що виконуються макросом, повинні бути спланованими перед записом або написанням макросу. Якщо при записі макросу була допущена помилка, зроблені виправлення також будуть записані. Visual Basic зберігає кожен записаний макрос в окремому модулі, приєднаному до документу в нашому випадку Excel.