Побудова циклічних алгоритмів

 

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

 

Завдання для підготовки до виконання лабораторної роботи

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

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

 

 

ЗАГАЛЬНІ положення

 

Цикл - це фрагмент обчислювального процесу, що повторюється багаторазово.

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

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

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

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

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

1) початкове значення змінної, яке буде змінюватися під час повторення циклу;

2) кінцеве значення цієї змінної;

3) крок зміни перед кожним новим повторенням циклу.

4) Необхідно контролювати поточне значення лічильника циклу для перевірки умови виходу з циклу. Такою умовою може бути:

1) перевищення лічильником циклу кінцевого значення;

2) виконання заданої кількості повторень;

3) досягнення заданої точності розрахунків.

Розрізняють арифметичні та ітераційні цикли:

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

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

 

Вкладений цикл. Алгоритм, тіло циклу якого містить ще один цикл називається алгоритмом із вкладеним циклом.

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

Приклади розв’язання задач. Задача 1. Скласти схему алгоритму циклічного обчислюваного процесу

 

для .

Вивести до друку значення змінних х, у.

Розв’язання. Для циклічного процесу характерним є повторення набору операцій над різними даними. В наведеній задачі існує чотири таких набори:

1) підрахунок суми ;

2) підрахунок факторіалу числа k!;

3) підрахунок добутку ;

4) підрахунок значення у для кожного зі значень параметра х.

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

 

Підрахунок суми. Числа знизу та зверху знака суми позначають границі зміни значення змінної і. Позначимо змінну, в якій буде зберігатися результат обчислень через S, тоді S=1²+2²+3²+4²+5²+6²+7²+8²+9²+10². В даному випадку виконуються операції піднесення до другого степеня та додавання до змінної, значення якої змінюється від 1 до 10 з кроком 1. Якщо розбити цей процес на окремі кроки, то кожен крок буде полягати в додаванні до попереднього результату значення змінної і, піднесеного до другого степеня та зміни цього значення на одиницю. У математичних виразах такі дії можна записати у вигляді: S=S+i², i=i+1. Блок-схема алгоритму розрахунку в даному випадку матиме вигляд, наведений на рисунку 5, а (параметр n задано таким, що дорівнює 10).

З точки зору реалізації на комп’ютері формула S=S+i² має свою специфіку: на першому кроці значення змінної S є невідомим; у комірці пам’яті, яку буде відведено під дану змінну, може міститися будь-яке значення (наприклад, код символу @), що може спотворити результат підрахунків суми. Тому, перш ніж починати цикл, треба надати змінній S значення, яке не змінить результат, для суми – це нуль.

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

 

а б

 

Рисунок 5 – Блок-схема алгоритму підрахунку суми

 

У наведених циклах лічильником є змінна i, початкове значення якої – 1 (блок 4), кінцеве – n= 10, крок зміни лічильника 1 (блок 6), а умовою виходу з циклу є перевищення лічильником кінцевого значення (i>n), перевірка якої у блоці 7. До тих пір, поки умова блоку 7 не виконується, процес повертається до блоку 5, де виконується тіло циклу (формула блоку 5) та збільшення значення лічильника циклу на крок (блок 6).

Підрахунок факторіалу. Факторіалом числа k (k!) є добуток всіх натуральних чисел: від 1 до k включно. Позначимо змінну, яка містить значення факторіалу, через F, тоді F=1∗2∗3∗…∗ (k-1)∗k.

Якщо розбити процес підрахунків на окремі кроки, то кожен крок складатиметься з множення результату, отриманого на попередньому кроці на нове значення, тобто F=F∗i, причому значення і змінюється від 1 до k з кроком 1.

Блок-схему алгоритму розрахунку факторіалу зображено на рис. 6.

Рисунок 6 – Блок-схема алгоритму k!

 

Так само, як і в підрахунку суми перш ніж виконувати цикл слід змінній, яка буде містити результат, надати значення, яке не змінить результат. Для операції добутку – це 1 (блок 3).

У наведеному циклі лічильником є змінна i, початковим значенням якої є 1 (блок 4), кінцевим – k, кроком зміни лічильника – 1 (блок 6), а умовою виходу з циклу – перевищення лічильником кінцевого значення (i>k), перевірка якого виконується в блоці 7. Поки умова блоку 7 не виконується, процес повертається до блоку 5, де виконується тіло циклу (формула блоку 5) та збільшення значення лічильника циклу на крок (блок 6).

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

Якщо під знаком добутку стоїть складніша формула, наприклад: , то блок-схема алгоритму матиме вигляд, наведений на рисунку 7, б.

 

а б

 

Рисунок 7 – Блок-схеми для розрахунку добутків

 

У блок-схемах алгоритмів циклічних обчислюваних процесів для зручності прийнято використовувати блок циклу, до якого заносять початкове, кінцеве значення лічильника циклу та крок зміни лічильника (якщо крок дорівнює 1, його не вказують). Такий блок замінює блоки 4, 6 та 7 і має два вхідні потоки (від попереднього блоку та від кінця тіла циклу в разі невиконання умови виходу з циклу) та два вихідні потоки (до блоку тіла циклу та до наступних блоків алгоритму в разі виконання умови виходу з циклу). Блок-схеми розрахунків суми, факторіалу та добутку з блоком циклу наведено на рисунках 8 а, б, в відповідно.

 

а б

в

 

Рисунок 8 – Блок-схеми з блоком циклу

Кінцевий вигляд схеми алгоритму для всієї задачі наведено на рисунку 9.

Рисунок 9 – Алгоритм циклічного обчислювального процесу

Підрахунок у. Значення у залежить від значення х, яке набуває не одне а декілька значень (х =1, 1.1, 1.2, …, 4.8, 5), тому для знаходження та виведення значення у слід організувати цикл відносно змінної х.

У даному циклі лічильником є змінна х, початковим значенням якої є 1, кінцевим – 5, кроком зміни – 0,1, а умовою виходу з циклу – перевищення лічильником циклу кінцевого значення (блок 16). Тіло циклу складають блоки 17 (підрахунок значення у) та 18 (виведення значень х та у на екран).

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

Задача 2. Скласти схему алгоритму циклічного обчислюваного процесу із вкладеним циклом:

,

 

Вивести до друку значення змінної у.

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

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

 

Рисунок 9 – Блок-схема алгоритму із вкладеними циклами

 

Задача 3. Скласти схему алгоритму циклічного обчислюваного процесу із вкладеними циклами:

,

 

Вивести до друку значення змінної у.

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

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

 

 

Рисунок 10 – Блок-схема алгоритму з подвійним вкладенням циклів

Задача 4. Скласти схему алгоритму обчислюваного процесу:

 

 

 

у випадку, якщо змінна х змінюється від -10 до 5 з кроком 0.5.

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

Значення змінних D та C залежать від змінної х, яка набуває значення в діапазоні від -10 до 5 з кроком 0,5, тому на початку складання алгоритму слід організувати цикл. Лічильником циклу є змінна х, початкове значення лічильника – 10, кінцеве – 5, крок зміни – 0,5, умовою виходу з циклу є перевищення лічильником свого кінцевого значення.

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

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

Рисунок 11 – Блок-схема алгоритму циклічного та розгалуженого обчислюваного процесу