Попередня сторінка          Зміст           Наступна сторінка          Електронні посібники ВНТУ

 

ЛАБОРАТОРНА РОБОТА № 4

РОЗРОБКА ПРОГРАМ З ВИКОРИСТАННЯМ ДВОВИМІРНИХ МАСИВІВ

 

         Мета роботи

• Засвоїти техніку використання двовимірних масивів при програмуванні мовою С/С++.
• Ознайомитись зі способами оголошення та ініціалізації двовимірних масивів.
• Засвоїти способи виділення пам’яті для динамічних масивів.
• Навчитись будувати математичну модель задачі.
• Засвоїти методи перевірки правильності вхідних даних.

 

 

        

       ТЕОРЕТИЧНІ ВІДОМОСТІ

 

Багатовимірні масиви

Двовимірний масив (матриця) можна представити як одновимірний масив, кожний елемент якого – масив. Тривимірний масив – це масив, кожний елемент якого являє собою двовимірну матрицю.

char Matrix2D[6][9];              // Двовимірний масив 6x9 елементів

unsigned long Arr3D[4][2][8];     // Тривимірний

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

int Mass[3][2][4] = {1,2,3,4,5,6,7,8,9,10,11,12,

                 13,14,15,16,17,18,19,20,21,22,23,24};

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

int Mass[3][2][4]={{{l,2,3,4},{5,6,7,8}},

                  {{9,10,ll,12},{13,14,15,16}},

                  {{17,18,19,20},{21,22,23,24}};

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

int main()

{

  char x[][3]={{9,8,7},{6,5,4},{3,2,1}};

  for(int i=0; i<3; i++)

  {   

       for(int j=0; j<3; j++)

            printf("%d ", (int)x[i][j]);

       printf("\n");

  }

  return 0;

}

Динамічне виділення пам’яті під  масиви

Змінні у програмах повинні розміщатися в одному з трьох місць: в області даних програми, в області стеку, в області вільної пам’яті (купи).

Кожній змінній у програмі може відводитися пам’ять або статично (в момент завантаження), або динамічно (у процесі виконання програми).

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

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

Виділення пам’яті можна здійснювати двома способами.

І спосіб: функції malloc(), calloc(), free(). Ці функції описані у заголо­вочному файлі <stdlib.h> або <malloc.h>

Функція malloc(size) виділяє size байтів з купи. У випадку успішного виділення пам’яті покажчик встановлюється на виділений блок пам’яті. При невдалому виділенні пам’яті функція повертає NULL.

Функція calloc(num, size), окрім виділення області пам’яті під масив об’єктів, ще здійснює ініціалізацію елементів масиву нульовими значеннями. Тут num вказує, скільки елементів буде зберігатися у масиві, а size – розмір кожного елемента у байтах.

Наприклад, якщо необхідно виділити пам’ять для масиву з n цілих чисел типу long, це можна зробити за допомогою оператора:

long * fptr = (long *)malloc(n*sizeof(long));

Якщо необхідно виділити пам’ять під двовимірний масив розмірності m×n, це можна зробити за допомогою оператора

float* fptr = (float*)malloc(n*m*sizeof(float));

Функція free(*block) звільняє пам’ять, на яку вказує покажчик block.

ІІ спосіб: функції new(),  delete(). Ці функції з’явилися в С++.

malloc(), calloc(), free() працюють і в С, і в С++. Нові опе­ра­то­ри гнучкого розподілення пам’яті new() i delete() мають додаткові можли­вості.

Якщо оператори malloc(), calloc() повертають пустий покаж­чик, який далі пере­творюється до потрібного типу, то оператор new() повертає покаж­чик на той тип, для якого виділяється пам’ять, і додаткових перетворень не потребує.

Синтаксис операторів:

тип *ім’я_масиву = new тип [тип число];

. . .

delete[] ім’я;

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

Задача №1. Реалізувати програму, яка обчислює суму елементів, що розта­шовані на обох діагоналях квадратної матриці.

Формалізація задачі

1.   Вхідні дані: N – максимальна розмірність

      матриці (матриця квадратна,

      оскільки мова йде про діагоналі матриці; 

      n – реальна розмірність матриці А.

2.   Вихідні дані: S – сума елементів обох діагоналей.

3.   Здійснити перевірку коректності вхідних даних:

4.   Для заповнення елементів матриці використаємо

      генератор випадкових чисел.

5.   Для можливості здійснення перевірки правильності

       обчислень доцільно вивес­ти матрицю на екран.

 

Математична модель задачі.

 

Нехай задана квадратна матриця А розміром n×n:

 

      А = 

А00	А01	A02	…	A0,n-1
A10	A11	A12	…	A1,n-1
A20	A21	A22	…	A2,n-1
…	…	…	…	…
An-1,0	An-1,1	An-1,2	…	An-1,n-1

 

Необхідно знайти

         S = S₁ + S₂ ,

де

S₁ = A₀₀ + A₁₁ + … + A_n-1,n-1 = ;

S₂ = A_n-1,0 + A_n-2,1 + … + A_0,n-1 = ;

Для знаходження S₁ і S₂ доцільно

використати оператор циклу for.

Оскільки для обчислення обох частинних сум S₁ і S₂

 змінна циклу і змінюється однаково (і=0,…,n-1),

то обраху­вання обох сум можна виконати в одному циклі.

 

 Лістинг програми

 

#include "stdafx.h"

#include <iostream>

 

Схема роботи програми

 

    #include <conio.h>

    #include <locale.h>

    #define N 10

    using namespace std;

    int main()

    { setlocale(0,"");

      int a[N][N];

      int n=N+1;

      int A=0, B=0, S, S1=0, S2=0;

      while(n>N) // перевірка правильності введення

      {

        printf("\nВвед1ть розм1рн1сть матриц1: n = ");

        scanf_s("%d",&n);

      }

      while (A>=B)

      { 

         printf("\nВвед1ть границ1 пром1жку A i B: ");

         scanf_s("%d %d",&A, &B);

      }

      printf("\n\nМатриця А:");

      for (int i=0;i<n;i++)

      {    printf("\n\n");

          for (int j=0;j<n;j++)

          {    a[i][j]=rand()%(B-A)+A;

               printf("%5d",a[i][j]);

          }

      }

      for (int i=0;i<n;i++)// підрахунок суми

      {   

           S1 += a[i][i];

          S2 += a[n-1-i][i];

      }

      S = S1 + S2;

      printf("\n\nСума діагональних елемент1в S = %7d",S);

      return 0;

    }

Результати виконання програми:

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

Задача №2.  Заповнити прямокутну матрицю випадковими числами з інтервалу (а, b). Створити матрицю, що містить стільки ж стовпців, як і вхідна матриця, і 3 рядки: 1-й рядок – мак­си­маль­ні значення відповідних стовпців, 2-й – середні арифметичні значення елементів стовпця, 3-й рядок – мінімальні значення відповідних стовпців.

Математична модель задачі.

Нехай маємо матрицю А розмірністю n×m.

Необхідно отримати матрицю В:

В_0j = max{A_ij,  i=0, …, n-1} – максимальне значення серед елементів j-ого стовпця (j=0,…,m-1);

В_1j = avg{A_ij,  i=0, …, n-1} = (A_0j+A_1j+…+A_n-1,j)/n – середнє значення елементів стовпця (j=0,…,m-1);

В_2j = min{A_ij,  i=0, …, n-1} – максимальне значення серед елементів стовпця (j=0,…,m-1).

Формалізація завдання

1. Вхідні дані: n, m – кількість рядків і стовпців матриці А відповідно, a, b – границі інтервалу для елементів матриці.
2. Вихідні дані: матриця В, що містить максимальні, середні, мінімальні зна­чення стовпців.
3. Розмірність матриці задається  у про­­цесі роботи програми, отже, для неї пам’ять будемо виділяти дина­мічно (з купи).
4. Границі інтервалу (а, b) вводимо з клавіатури, елементи матриці запов­нюємо за допомогою генератора випадкових чисел.
5. Матрицю В доцільно оголосити дій­сною, оскільки серед її елементів будуть значення середнього ариф­ме­­тичного, а це – результат роз­рахунку.Пошук мінімального і макси­маль­ного елементів будемо здій­снювати одночасно, пере­бираючи і порів­ню­ючи усі елементи стовпця по черзі (використаємо оператор циклу).
6. Для знаходження середнього ариф­ме­тичного значення треба накопи­чувати суму елементів стовпця, що також можна робити у тому ж самому циклі.

Схема роботи програми 

Лістинг програми

#include <iostream>

#include <conio.h>

#include <new.h>

#include <locale.h>

using namespace std;

int main()

{  setlocale(0,"");

   int n, m, a=0, b=0;

   cout<<" \nВвед1ть розм1рнoстi масиву n i m:\n";  

   cin>>n>>m;

   cout<<"\n n="<<n<<"  m="<<m;

   while (a>=b) 

   {        //перевірка правильності

      cout<<" \n\n  Введ1ть границ1 1нтервалу a i b:\n";

      cin>>a>>b;

      cout<<"\n a="<<a<<" b="<<b;

    }

    int** arr = new int*[n];

    cout<<"\n\n  Початковий  масив:\n";

    for (int i=0;i<n;i++)

    { arr[i] = new int[m];

      cout<<"\n";

      for (int j=0;j<m;j++)

      {    

            arr[i][j]=rand()%(b-a)+a;

            printf("%7d",arr[i][j]);

      }

    }

    float** brr = new float*[3];

    for (int i=0;i<3;i++)

        brr[i] = new float[m];

    for (int j=0;j<m;j++)

    {  // по стовпцях

        int min=b; // початкове значення мінімуму у стовпці

            int max=a;  // початкове значення максимуму  у стовпці

            float s=0;  // для накопичення суми у сер. арифм.  у стовпці

            for (int i=0;i<n;i++)

            {    

                  if (arr[i][j]>max)  max = arr[i][j];

                  if (arr[i][j]<min)  min = arr[i][j];

                  s += arr[i][j];

            }

            s = s/n;    // обчислюємо сер.арифм.

            brr[0][j] = max; brr[1][j] = s;      brr[2][j] = min;

      }

      cout<<"\n\n  Результуючий масив:\n";

      for (int i=0;i<3;i++)

      {    

            cout<<"\n";

            for (int j=0;j<m;j++)

                  if (i==1) printf("%7.2f",brr[i][j]);

                  else      printf("%7.0f",brr[i][j]);

      }

      delete[] arr;     delete[] brr;

      _getch();

      return 0;

}

Результат роботи програми

 

Рекомендації

 

1.     Динамічне виділення пам’яті для одновимірного масиву A (цілих чисел) розміром n і заповнення елементів масиву випадковими числами:

    int* A = new int[n];

   for (int i=0;j<n;j++)

        A[i]=rand()%RAND_MAX+1;

2.     Динамічне виділення пам’яті для двовиимірного масиву arr (цілих чисел) розміром n×m та його заповнення випадковими числами:

int** A = new int*[n];

for (int i=0;i<n;i++)

{

     arr[i] = new int[m];

      for (int j=0;j<m;j++)

           arr[i][j]=rand()%RAND_MAX+1;

 }

 

Порядок виконання роботи

 

1. Ознайомитись з теоретичним матеріалом.
2. Дослідити процес реалізації завдань прикладів, відлагодити наведені програму на своєму комп’ютері.
3. Розробити власні програми, які реалізує індивідуальне завдання.
4. Підготувати звіт, який включатиме:
•  варіант і текст індивідуального завдання;
•  формалізацію завдання (включаючи математичну модель задачі);
•  схему роботи програми;
•  лістинг програми;
•  роздруківку трьох контрольних прикладів (вигляд екрану з результатами (різні значення вхідних даних);
•  висновки.

 

Варіанти індивідуальних завдань

 

Задача 1. Розробити програму, дотримаючись таких вимог: викорис­то­вувати статичні масиви; максимальні розміри масиву (N i M) – статичні константи; реальні розміри  масиву n  i  m (n<N, m<M) – ввести з кла­ві­атури (при цьому здійснювати перевірку правильності введення даних); елементи масиву – псевдовипадкові числа, згенеровані на інтервалі [a, b], де a і b (a<b) вводяться з клавіатури; усі вхідні дані і також елементи масиву виводити на екран.

Задача 2. Змінити код програми (задача №1) таким чином, щоб вико­ристовувались не статичні масиви і статичні константи для їх оголошення, а динамічні масиви. У звіт включити лише лістинг програми та роздруківку трьох контрольних прикладів.

Задача 3. Розробити програму, дотримаючись таких вимог: викори­с­товувати динамічні масиви; реальні розміри  масиву n  i  m  ввести з клавіатури; елементи масиву – псевдовипадкові числа на інтервалі [a,b], де a і b (a<b) вводяться з клавіатури; усі вхідні дані, елементи вхідного і вихідного масивів виводяться на екран у зручному для перегляду вигляді. Підготувати звіт у повному обсязі.

1	Заповнити матрицю А випадковими числами. Відобразити матрицю симетрично відносно головної діагоналі. Знайти максимальний і мінімальний елемент головної діагоналі.
2	Заповнити матрицю А випадковими числами. Створити одновимірний масив В, елементи якого – кількість додатних чисел відповідного рядка. На головній діагоналі розмістити суми елементів, які лежать на тому ж рядку і у тому ж стовпці.
3	Дана цілочисельна прямокутна матриця А. Визначити кількість рядків, що не містять жодного нульового елемента. Створити одновимірний масив В, елементами якого є максимальні значення відповідних рядків матриці А.
4	Дана цілочисельна прямокутна матриця А. Ввести ціле число с (а<c<b). Підрахувати середнє арифметичне значення елементів головної і побічної діагоналей. Створити іншу матрицю В, в якій елементи, менші за с замінити на 0, а елементи, більші за с, замінити на 1.
5	Заповніть матрицю А випадковими числами. Знайти середнє арифметичне усіх елементів матриці. Відобразити головну і побічну діагоналі симетрично щодо вертикальної осі.
6	Заповнити прямокутну матрицю випадковими числами. Відобразити верхню половину матриці на нижню дзеркально симетрично відносно горизонтальної осі. Знайти і вивести на друк послідовність елементів матриці, які попадають в інтервал [a/2, b/2].
7	Заповнити матрицю випадковими числами. Знайти номери рядків і стовпців, які містять мінімальний і максимальний елементи матриці. На побічної діагоналі розмістити суми елементів, які лежатьна тому ж рядку і у тому самому стовпці.
8	Заповнити матрицю А випадковими дійсними числами. Створити матрицю В, яка має стільки ж рядків, як і матриця А, і 5 стовпчиків: 1-й стовпчик буде містити мінімальні елементи відповідного рядка, 2-й – максимальні, 3-й – середні арифметичні значення, 4-й – кількість додатних елементів, 5-й – кількість від’ємних елементів відповідного рядка.
9	Заповнити матрицю випадковими числами. Відобразити головну і побічну діагоналі симетричновідносно горизонтальної осі. Знайти максимальне і мінімальне значення головної і побічної діагоналей.
10	Дана прямокутна цілочисельна матриця. Визначити добуток елементів в тих рядках, які не містять від'ємних елементів. Підрахувати  максимум і мінімум серед сум елементів діагоналей на головній і побічній діагоналях матриці.
11	Заповнити прямокутну матрицю випадковими числами. Відобразити праву половину матриці на ліву дзеркальносиметрично щодо вертикальної осі. Підрахувати кількість додатних і від’ємних елементів у матриці.
12	Дана прямокутна дійсна матриця. Визначити суму елементів в тих стовпцях, які не містять від'ємних елементів. Визначити омер рядка матриці, сума елементів якої максимальна.
13	Дана прямокутна дійсна матриця. Підрахувати кількість парних і непарних елементів на головній і побічній діагоналях матриці. Визначити номер стовпця, сума елементів якого мінімальна.
14	Дана прямокутна цілочисельна матриця. Знайти середнє арифметичне усіх елементів матриці. Знайти і вивести на друк послідовність елементів матриці, які попадають в інтервал [a/4, b/4].
15	Дана цілочисельна матриця А. Ввести ціле число с (а<с<b). Створити іншу матрицю В, в якій елементи, більші за с замінити на 1, а елементи, більші за с, замінити на -1. Підрахувати середнє арифметичне значення елементів головної і побічної діагоналі.

* Задача 4. Одна із задач операційних систем – розподіл пам’яті між при­кладними програмами та між користувачами. Написати модуль для операційної системи, який не дозволятиме користувачам Alice, Bob та Carl отримувати оперативної пам’яті більше, ніж їм дозволено.

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

 

 

        

 

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

 

1. В чому різниця між статичними та динамічними масивами?
2. Коли і звідки видялється пам’ять для статичних і динамічних масивів?
3. Як оголосити одновимірний динамічний масив?
4. Як оголосити динамічний двовимірний масив?
5. Наведіть фрагмент коду для заповнення масиву цілими (дійсними) випадковими числами.
6. Наведіть фрагмент коду для обчислення суми (добутку) елементів одновимірного масиву?
7. Наведіть фрагмент коду для підрахунку суми (добутку) елементів певного рядка (стовпця) двовимірного масиву?