Проектування алгоритмів лінійних обчислювальних процесів

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

 

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

В алгоритмі лінійної структури використовуються наступні блочні символи:

- пуск (початок);

- введення;

- виведення;

- зупинка (кінець).

Приклад: Обчислити висоти трикутника зі сторонами a, b, c, використовуючи формули

 ,

 ,

 ,

де  .

Щоб виключити повторювані числа, використовуємо проміжну величину

 ,

тоді .

Значення величин p, t, , ,  зберігаються в комірках пам’яті з відповідними іменами. Алгоритм обчислення представлений на мал. 1.

 

 

 

Рис. 1 Алгоритм лінійної структури

 

3 Контрольні питання

3.1 Перерахувати етапи розв’язання задачі на ЕОМ.

3.2 Визначити поняття “алгоритм” та перелічити його властивості.

3.3 Визначити поняття “програма” розв’язання задачі на ЕОМ.

3.4 Перерахувати способи опису алгоритмів.

3.5 Пояснити правила використання блок-схем для опису алгоритмів.

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

 

ПРОЕКТУВАННЯ АЛГОРИТМІВ АРИФМЕТИЧНИХ

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

 

Навчальний матеріал

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

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

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

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

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

- вводяться необхідні вхідні дані;

- задаються початкове значення суми і значення допоміжних змінних (за необхідності);

- обчислюється значення поточного члена ряду;

- виконується порівняння значення поточного члена ряду з заданою точністю ;

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

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

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

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

На схемі алгоритму (рис. 1) у блоці 3 задаються вхідні значення номера n - го члена ряду, що обчислюється, і початкове значення суми членів ряду S. У даному випадку n = 1 і S = 1, тобто обчислення починаються з другого члена ряду, тому що перший член ряду дорівнює одиниці і не обчислюється за загальною формулою члена ряду.

Накопичення суми виконується в блоці 5 за допомогою рекурсивної залежності:

S = S + Y,

де Y – значення чергового обчисленого члену ряду.

 

	Рис. 1 Алгоритм обчислення суми нескінченного ряду

 

3 Контрольні питання

3.1 Що означає ітераційний циклічний процес?

3.2 Які умови збігу методу ітерацій?

3.3 Вкажіть порядок побудови ітераційного алгоритму.

3.4 Як організується вихід з циклу в ітераційному алгоритмі?

3.5 Яким чином в ітераційних циклах використовуються рекурсивні відношення?

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

3.7 Для яких задач застосовують ітераційні цикли?

 

 

Навчальний матеріал

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

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

Порядок зміни цих параметрів визначається умовами задачі.

При організації внутрішніх циклів необхідно врахувати, що область дії внутрішнього циклу не повинна виходити за область дії зовнішнього циклу.

Приклад 1: Скласти алгоритм обчислення значення функції

В алгоритмі (рис.1) кілька разів обчислюються суми. Параметри циклів змінюються послідовно, тобто на одне значення параметра зовнішнього циклу параметр внутрішнього циклу приймає послідовно усі свої значення. Зафіксувавши значення І в зовнішньому циклі, у внутрішньому циклі виконується накопичення суми при значеннях J, що змінюються від 1 до М. Після чого значення І збільшується в зовнішньому циклі на 1 і внутрішній цикл повторюється. Якщо І > N, тоді виконується вихід з циклу і виводиться накопичений результат.

 

	Рис. 1. Алгоритм вкладеного циклічного процесу

 

Приклад 2: Скласти програму обчислення значень функції

 sin(x+y), якщо x>0 и y<0,

 Z =

 cos(x-y) – в останніх випадках,

 якщо х змінюється від х_н = -5 до х_к = 5 із кроком h_х =1;

y змінюється від y_н = -0,5 до y_к = 0,5 c кроком h_y =0,1.

 

 

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

 

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

3 Контрольні питання

3.1 Визначите поняття "вкладений циклічний процес".

3.2 Які принципи побудови вкладених циклів?

3.3 Як визначається число повторень у вкладених циклічних процесах?

3.4 На яку глибину можуть бути вкладені циклічні процеси?

3.5 Яким чином у вкладених циклічних процесах використовуються рекурсивні відношення?

3.6 Для яких задач застосовуються вкладені циклічні процеси?

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

 

Навчальний матеріал

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

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

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

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

Схема алгоритму задачі при використанні підпрограм складається із декількох алгоритмів, один із яких є основним (головним) і обов’язково має наступні блоки: “початок”, “кінець”; присвоєння формальним параметрам фактичних значень; “підпрограма”, присвоєння фактичним змінним результатів обчислень підпрограм. В інших алгоритмах описуються дії, які виконуються у підпрограмах. Такі алгоритми складаються з блоків: “вхід”, опису обчислювального процесу з використанням формальних параметрів, “вихід”.

При використанні вкладених підпрограм схема алгоритму, що викликає програму повинна містити блочні компоненти основної програми: блоки присвоєння формальним параметрам програми, що викликається, блоки “підпрограма”, блоки присвоєння фактичним змінним головної програми результатів обчислень підпрограми, що викликається.

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

На момент звертання до підпрограми усі вхідні фактичні параметри повинні бути визначені, тобто їх значення повинні бути відомими.

Приклад 1: У дисплейному залі в обігу знаходяться n дисплеїв, кожен з яких може відмовити з імовірністю p. Імовірність того, що за день відмовлять не менше m дисплеїв, можна оцінити за формулою

W= ,

де  – число сполучень з n по k.

Скласти програму розрахунку імовірності w=f(n, m, p) для заданих значень n=15; p = 0,05. Значення m ввести у діалоговому режимі.

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

                     1, якщо х = 0

   F = x! =

                     якщо х > 0

Для обчислення факторіалу використовується підпрограма, рис. 1.

 

 

 

Підпрограма містить оператор присвоєння F=1 та цикл, в якому здійснюється обчислення факторіалу Х!. Слід мати на увазі, що значення Х задається в алгоритмі основної програми до виконання підпрограми.

Перед першим зверненням змінній Х присвоюється значення фактичного параметра N (блок 4 алгоритму головної програми), після цього здійснюється перехід до підпрограми (блок 5). Після обчислення N! управління з підпрограми передається блоку 6, де значення результату F присвоюється фактичній змінній А. Аналогічно обчислюються В=К! та F= (N - К)!.

Приклад 2: У програмі необхідно багаторазово виводити різноманітні заголовки, оздоблюючи вгорі та знизу рядком зірочок, наприклад:

 *************************************

ГРАФІК ПЕРШОЇ ФУНКЦІЇ Y=F (X)

 *************************************

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

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

В основній програмі текстовій змінній А$ (блок 2) присвоюється текст заголовку, що повинен бути надрукований, і управління передається підпрограмі П1 друку заголовку (блок 3). Першим оператором цієї підпрограми є оператор виклику другої підпрограми - друку рядка зірочок (блок 3 підпрограми П2). Друга підпрограма друкує рядок зірочок і повертає управління до першої підпрограми П1, на блок 3, що здійснює друк тексту заголовку. Після цього управління знову передається другій підпрограмі П2. Друкується рядок зірочок, що оздоблює текст заголовку знизу, та передається управління першої підпрограмі і вже з неї здійснюється повернення до основної програми (блок 4). Присвоюючи змінній А$ різноманітний текст, можна звертатися до вкладених підпрограм декілька разів.

 

 

3 Контрольні питання

3.1 При яких умовах доцільно використання підпрограми?

3.2 Визначити поняття формальних та фактичних параметрів.

3.3 Які основні блоки використовуються в алгоритмі головної програми?

3.4 Які основні блоки використовуються в алгоритмі підпрограми?        

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

3.6 Визначити поняття "вкладена підпрограма".

 

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

 

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

В алгоритмі лінійної структури використовуються наступні блочні символи:

- пуск (початок);

- введення;

- виведення;

- зупинка (кінець).

Приклад: Обчислити висоти трикутника зі сторонами a, b, c, використовуючи формули

 ,

 ,

 ,

де  .

Щоб виключити повторювані числа, використовуємо проміжну величину

 ,

тоді .

Значення величин p, t, , ,  зберігаються в комірках пам’яті з відповідними іменами. Алгоритм обчислення представлений на мал. 1.

 

 

 

Рис. 1 Алгоритм лінійної структури

 

3 Контрольні питання

3.1 Перерахувати етапи розв’язання задачі на ЕОМ.

3.2 Визначити поняття “алгоритм” та перелічити його властивості.

3.3 Визначити поняття “програма” розв’язання задачі на ЕОМ.

3.4 Перерахувати способи опису алгоритмів.

3.5 Пояснити правила використання блок-схем для опису алгоритмів.

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