Приклади алгоритмів із розгалуженням

Назва, початкове значення, кінцеве значення, крок зміни.

Крок зміни лічильника, що дорівнює одиниці, можна не вказувати

Постановка задачі 1: обчислити експоненту за допомогою ряду

, (2.14)

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

Розв’язання:

Вхідними даними алгоритму є:

- значення показника експоненти - x;

- точність обчислень - ε.

Вихідними даними алгоритму є:

- значення експоненти - у;

- кількість кроків, витрачена на досягнення заданої точності – n

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

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

n! = n-(n -1)!, (n -1)! = (n -1)-(n - 2)!,..., 2! = 2 • 1!. (2.15)

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

Побудуємо алгоритм у словесному вигляді:

- ввести x, ε;

- задати початкове значення параметру циклу: p = 1;

- задати початкове значення суми елементів ряду: S = 1;

- задати початкове значення знаменника: z = 1;

- тіло циклу:

1. обчислити черговий елемент ряду:

2. додати обчислений елемент ряду до суми: S = S + у;

3. збільшити параметр циклу на одиницю: p = p + 1;

4. обчислити нове значення знаменника: z = z * p;

5. якщо черговий елемент ряду менше заданої точності: у < є - вийти з тіла циклу;

6. перейти до кроку 1 тіла циклу;

- кінець тіла циклу

- записати кількість витрачених кроків: n = p;

- вивести S і n.

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

Схема алгоритму розв'язанні задачі представлена на наступному рис. 2.12.

Рис. 2.12 - Схема алгоритму обчислення експоненти

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

- x = 2 (е²=7,39);

- ε = 0,01.

p	x^p	z	у	S
			2,00	3,00
			2,00	5,00
			1,33	6,33
			0,67	6,99
			0,27	7,27
			0,09	7,36
			0,03	7,38

Таким чином, задана точність була досягнута за сім кроків циклу. Результат обчислення: 7,38.

Постановка задачі 2: вивести всі точки з цілочисельними координатами, які потрапляють в коло з радіусом R і центром на початку координат.

Розв’язання:

Вхідні дані алгоритму - радіус кола - R.

Вихідні дані - множина пар цілочисельних координат точок (x, у), які потрапляють в коло.

Будемо вважати, що точка потрапляє в коло тоді, коли відстань від центру кола до неї суворо менше ніж радіус кола.

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

Рис. 2.13 - Ілюстрація до задачі про точки з цілочисельними координатами

Складемо алгоритм у текстовому вигляді:

ввести R;

• кінець тіла зовнішнього циклу

Зауважимо, що в даному алгоритмі використовується так званий вкладений цикл, тобто один цикл (внутрішній) є тілом іншого (зовнішнього). Під час виконання алгоритму на кожен крок зовнішнього циклу припадають всі кроки внутрішнього циклу. Якщо кількість кроків обох циклів однакова і дорівнює N, то загальна кількість кроків, за яку буде повністю виконано зовнішній цикл складатиме N[1]N.

Схема алгоритму представлена на рис. 2.14.

Рис2.14 - Схема алгоритму розв'язання задачі про точки з

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

Дата добавления: 2014-11-08