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

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

Введення - виведення елементів масиву виконується поелементно. Можливі два способи.

Спосіб 1. Безпосереднє введення-виведення елементів масиву, яке позначається на блок-схемі алгоритму при введенні значень елементів блоками “введення” або “процес” та при виведенні блоком “виведення”.

Такий спосіб доцільно застосовувати, коли масиви мають малі розміри.

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

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

Приклад 1: Вивести на друк елементи цілочисельного масиву N=[n1, n2, n3,..., n50], які кратні трьом. Сполучимо операції введення поточного значення елемента масиву і його опрацювання.

	Рис.1. Алгоритм знаходження елементів масиву кратних до трьох.

Рис. 1 Алгоритм визначення елементів масиву, кратних 3.

Якщо ж потрібно запам'ятати всі значення результатів у пам'яті, то необхідно виділити масив для результатів, і обчислити результат як змінну з індексом.

Приклад 2: Переписати підряд у масив Y додатні елементи масиву (x1, x2, x3,..., x20), а в масив Z - від’ємні.

Особливість рішення полягає в тому, що елементи, які записуються в масиви Z і Y, повинні розташовуватися підряд без пропусків. Це призведе до того, що індекси змінних y_k та z_j набудуть значень, відмінні від значень індексів змінної x_i. Тому в циклі необхідно змінювати значення k та j кожний раз перед записом відповідного елементу x, тобто необхідно використати спосіб організації циклу з кількома параметрами, які одночасно змінюються (рис. 2.).

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

z₁ = z₀ + y₁ = y₁

z₂ = z₁ + y₂ = (y₁) + y₂

..............................

z_i = z_i-1 + y_i = (y₁ + y₂)+y_i

..............................

z_n = z_n-1 + y_n

z_n =

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

z₁ = z₀ * y₁ = y₁

z₂ = z₁* y₂ = (y₁) * y₂

.............................

z_i = z_i-1 * y_i = (y₁ * y₂)*y_i

..............................

z_n = z_n-1 * y _n

z_n =

Якщо не потрібно зберігати у пам’яті комп’ютера додатки і проміжні добутки, вони представляються простими змінними; і тоді рекурентна формула для накопичення добутку має вигляд:

z = z * y.

де y - множник; z - проміжний добуток.

Перед циклом за початкове значення добутку, як правило, приймається одиниця: z₀ = 1.

Приклад 3: Скласти алгоритм обчислення математичного сподівання m_x випадкової величини x, використовуючи розрахункову формулу

m_x =

для початкових даних: n = 5; р_i = {0.3; 0.25; 0.2; 0.1; 0.15};

x_i = {90; 80; 120; 95; 110}.

Початковими даними для обчислення є проста змінна N та два масиви: P і X. Результат обчислення збережемо у простій змінній S. Для накопичення суми організується цикл, параметром якого є індекс I, який змінюється від 1 до N. (рис.3.)

Приклад 4: Скласти алгоритм обчислення середнього геометричного додатних елементів масиву. Схема алгоритму наведена на рис.4.

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

Якщо поточне значення більше від найбільшого (МАХ) з усіх попередніх, то МАХ присвоюється значення поточного. У протилежному випадку зберігається попереднє значення. Процес можна описати наступною залежністю:

y_i, якщо y_i> y_max

y_max =

y_max, якщо y_i £ y_max

Після закінчення циклу значення y_max буде найбільшим з усіх розглянутих значень y_i.

Аналогічним чином знаходиться найменше (MIN) серед набору елементів, із використанням залежності:

y_i, якщо y_i< y_min

y_min =

y_min, якщо y_i ³ y_min

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

Приклад 5: Скласти алгоритм знаходження найбільшого та найменшого елемента масиву (х₁, х₂, ….х_k) та їх порядкових номерів.

Особливість пошуку полягає в тому, що необхідно знаходити номер найбільшого та найменшого елемента. Прийнявши за початкове значення і максимальний і мінімальний елемент, запам’ятаємо їх номери і_max = 1 і і_min= 1. У циклі при виконанні умов x_i> x_max та х_i< х_min присвоюють, відповідно, x_max=x_і, і_max = і та х_min=х_i , і_min = і (рис. 5.)

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

3.1 Дайте визначення масиву.

3.2 Які характеристики мають масиви?

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

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

3.5 Як організувати рахунок кількості елементів?

3.6 Як організувати процес формування нових масивів у процесі розв’язання задач?

3.7 Як організувати знаходження найбільшого і найменшого елементів масиву?

3.8 Як організувати процес упорядкування елементів масиву?

3.9 У чому особливість організації циклу при обробці масивів?