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

 

Двовимірний масив характеризується ідентифікатором, який має два виміри (індекси), і числом значень у кожному вимірі (верхньою межею кожного індексу). Положення елемента в двовимірному масиві визначається індексами. Один вказує на номер рядка, а другий - на номер стовпчика, на перетині яких розташовується елемент. Тобто елемент двовимірного масиву A представляється ідентифікатором A(i,j), де

i - номер рядка масиву A;

j - номер стовпчика масиву A.

Розмір масиву (кількість елементів масиву) – добуток числа рядків на число стовпчиків масиву, тобто для масиву A(10,5) його розмір складає 50.

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

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

Приклад: Із матриці А(10,5) вивести на друк додатні елементи.

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

Щоб скоротити обсяг алгоритму, введення елементів матриці A(I, J) та їх обробка об'єднані. Пропонується наступний порядок виконання вкладеного циклу. У зовнішньому циклі задається параметр циклу І, який дорівнює 1. Так як І<10, то виконуються всі операції, що входять в даний цикл. Першою такою операцією є заголовок внутрішнього циклу, де параметру J задається значення 1, а потім вводиться значення елементу масиву А(1,1). Далі виконується перевірка умови А(1,1)>0. Якщо умова виконується, то збільшується значення лічильника К на 1 і виводиться значення елемента А(1,1); якщо умова не виконується, то виконується перехід на продовження внутрішнього циклу J = 2,3,4,5. Після закінчення внутрішнього циклу у зовнішньому циклі І приймає значення 2 і знов повторюється внутрішній цикл п’ять разів. Після 10 - кратного виконання зовнішнього циклу виконується перехід на блок “кінець”.

 

 

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

3.1 Дайте визначення двовимірного масиву.

3.2 Опишіть алгоритми введення та виведення двовимірних масивів.

3.3 Які операції повинні бути у схемах обробки двовимірних масивів?

3.4 Які характеристики мають двовимірні масиви?

3.5 У чому складається особливість організації циклу при обробці двовимірних масивів?

3.6 Опишіть правила організації вкладеного циклу з урахуванням порядку перебору елементів матриці.

3.7 Як організувати виведення нижньої трикутної матриці в узвичаєному вигляді?

3.8 Як організувати виведення верхньої трикутної матриці в узвичаєному вигляді?

3.9 Як організувати виведення матриці розміром H^хМ елементів в узвичаєному вигляді?

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

 

ПРОЕКТУВАННЯ АЛГОРИТМІВ З ВИКОРИСТАННЯМ ПІДПРОГРАМ

 

 

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

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

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

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

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

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

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

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

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

Приклад 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 Визначити поняття "вкладена підпрограма".