Базовими алгоритмами обробки одновимірних масивів є алгоритми:
- ініціалізації масиву
- виведення масиву
- обчислення узагальнувальних характеристик (сум елементів, добутків і т.п.)
- підрахунку кількості елементів, що задовольняють умові
- пошуку заданого елемента
- пошуку максимального або мінімального елемента
Базові алгоритми зручно реалізовувати у вигляді функцій, які згодом будуть використані як «архітектурні блоки» при розв’язанні більш складних задач.
Для наступних прикладів будемо вважати, що головна функція має наступний вигляд:
|
1 2 3 4 5 6 7 8 9 |
int main() { const int SIZE = 10; // оголошення та ініціалізація константи розміру масиву int mas[SIZE]; // оголошення масиву цілих чисел //тут буде виклик функцій system("pause"); return 0; } |
1. Ініціалізація масиву
Для заповнення масиву даними необхідно послідовно перебрати всі елементи масиву і записати в них деякі значення. Для перебору масиву найбільш зручно використовувати оператор циклу for, в якому за допомогою лічильника перебираються індекси елементів масиву.
1.1 Заповнення елементів масиву з клавіатури:
|
1 2 3 4 |
void fillMas(int mas[], int size) { for (int i = 0; i < size; i++) cin>>mas[i]; } |
1.2 Заповнення елементів масиву випадковими числами за допомогою функції rand():
|
1 2 3 4 5 |
void fillMas(int mas[], int size) { srand(time(NULL)); for (int i = 0; i < size; i++) mas[i] = rand(); } |
1.3 Обчислення елементів масиву за формулою:
Приклад. Заповнити масив квадратами цілих чисел від 1 до n.
|
1 2 3 4 |
void fillMas(int mas[], int n) { for (int i = 0; i < n; i++) mas[i] = pow(i+1,2); } |
2. Виведення масиву
Для виведення масиву необхідно послідовно перебрати всі елементи масиву та вивести їх значення на екран:
|
1 2 3 4 |
void printMas(int mas[], int size) { for (int i = 0; i < size; i++) cout<< mas[i]<<" "; } |
3. Обчислення узагальнувальних характеристик
Приклад. Обчислити суму елементів масиву.
|
1 2 3 4 5 6 7 |
int sumMas(int mas[], int size) { int sum = 0; for (int i = 0; i < size; i++) { sum += mas[i]; } return sum; } |
4. Підрахунок кількості елементів, що задовольняють заданій умові
Приклад. Підрахувати кількість додатних чисел серед елементів масиву.
|
1 2 3 4 5 6 7 8 |
int positivAmount(int mas[], int size) { int count = 0; for (int i = 0; i < size; i++) { if (mas[i] > 0) count++; } return count; } |
5. Пошук заданого елемента
Пошук в масиві полягає у визначенні індексу елемента, значення якого дорівнює заданому. Для здійснення пошуку необхідно послідовно перебрати всі елементи масиву. Такий вид пошуку називається лінійним.
Нехай value – значення, яке необхідно знайти в масиві mas[size]:
|
1 2 3 4 5 6 7 |
int findValue(int mas[], int size, int value) { for (int i = 0; i < size; i++) { if (mas[i] == value) return i; } return -1; } |
Функція повертає індекс першого знайденого елемента, рівного value. Якщо значення не знайдене, повертає -1. Головна функція для цієї задачі може мати наступний вигляд:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
int main() { const int SIZE = 10; int mas[SIZE]; fillMas(mas, SIZE); //ініціалізація масиву int result, value; cin >> value; //введення значення, яке необхідно знайти result = findValue(mas, SIZE, value); //виклик функції пошуку if (result != -1) cout << "Element index is " << result; else cout << "Value not found "; system("pause"); return 0; } |
Якщо значення елементів в масиві повторюються, то такий пошук дозволить знайти лише перший з таких елементів. Функція виведення таких елементів може мати наступний вигляд:
|
1 2 3 4 5 6 7 8 9 10 11 |
void findValue(int mas[], int size, int value) { bool found = false; for (int i = 0; i < size; i++) { if (mas[i] == value) { cout << "Value found in" << i << "place" << endl; found = true; } } if (found == false) cout << "Value not found" << endl; } |
В цій функції використовується змінна булевого типу found, яка перед виконанням циклу пошуку має значення false , а коли хоча б один елемент знайдено, набуає значення true. Вона дає можливість визначити результат пошуку і вивести відповідне повідомлення, якщо жодного елементу не знайдено.
6. Пошук максимального та мінімального елемента
Для визначення максимального (мінімального) елемента визначається додаткова змінна max (min), в яку в результаті виконання програми запишеться максимальне (мінімальне) значення. На початку програми цій змінній присвоюється значення першого елемента.
Починається перебір масиву з одночасною перевіркою чи є поточний елемент більше максимального (менше мінімального). Якщо умова істина, значення елемента присвоюється змінній max(min):
|
1 2 3 4 5 6 7 8 |
int maxValue(int mas[], int size) { int max = mas[0]; for (int i = 1; i < size; i++) { if (mas[i] > max) max = mas[i]; } return max; } |
Цей алгоритм дозволяє знайти значення максимального елемента масива. Якщо необхідно знайти індекс максимального елемента, то можна використати наступну функцію:
|
1 2 3 4 5 6 7 8 |
int maxElement(int mas[], int size) { int index_max = 0; for (int i = 1; i < size; i++) { if (mas[i] > mas[index_max]) index_max = i; } return index_max; } |
Зверніть увагу! Якщо в масиві елементи повторюється і є декілька максимальних елементів, дана функція знайде індекс першого з них.