Печатать книгуПечатать книгу

§ 15. Двухмерныя масівы

Сайт: Профильное обучение
Курс: Інфарматыка. 10 клас (Павышаны ўзровень)
Книга: § 15. Двухмерныя масівы
Напечатано:: Гость
Дата: Среда, 8 Май 2024, 04:29

Оглавление

15.1. Апісанне двухмернага масіву

Колькасць індэксаў, па якіх звяртаюцца да элемента ў масіве, вызначае размернасць масіву.

Акрамя аднамерных, могуць выкарыстоўвацца двухмерныя, трохмерныя і іншыя масівы.

Двухмерны масіў — масіў, элементамі якога з’яўляюцца аднамерныя масівы. Яго можна выявіць як табліцу з данымі, у якой кожны радок — лінейны масіў. Зварот да элемента ажыццяўляецца па двух індэксах: a[3][5] — элемент, змешчаны ў радку, які мае індэкс тры, і слупку з індэксам пяць. Прыкладам выкарыстання двухмернага масіву з’яўляецца ліст электроннай табліцы.

Двухмерны масіў апісваюць наступным чынам:

vector <vector <тып элементаў>> імя_масіву
(колькасць радкоў, vector <тып элементаў>(колькасць слупкоў));

Структура апісання здаецца дастаткова складанай, аднак яна цалкам адлюстроўвае сутнасць: двухмерны вектар — лінейны вектар, элементамі якога з’яўляюцца лінейныя вектары. Другі параметр у круглых дужках паказвае, якім значэннем трэба запоўніць кожны радок. У прыкладзе 15.1 паказана, як можна апісваць двухмерныя вектары.

Па аналагічнай схеме можна апісваць масівы вялікіх размернасцяў.

Шматмерныя масівы выкарыстоўваюцца ў вылічальнай матэматыцы. Пры  мадэліраванні аб’ектаў, працэсаў і з’яў шматмерныя масівы дазваляюць захоўваць параметры мадэлі і дыяпазоны іх змянення.

Для шматмерных масіваў выкарыстоўваюць наступныя назвы: аднамерны масіў — вектар, двухмерны масіў — матрыца (прамавугольная табліца), трохмерны масіў — куб (набор аднатыпных табліц).

Для вызначэння шматмернага масіву большай размернасці выкарыстоўваюць паняцце тэнзар. Чатырохмерны, пяцімерны, шматмерны масіў — тэнзар.

Прыклад 15.1. Апісанне двухмерных масіваў.

Апісанне двухмернага масіву цэлых лікаў з 10 радкоў і 10 слупкоў.

  vector <vector <int>> d(10, vector <int> (10));  

Апісанне двухмернага масіву, памеры якога ўводзяць з клавіятуры:

cout << "kol-vo strok i";

cout << "stolbcov" << endl;

cin >> m >> n;

vector <vector <int>> d(m, vector <int> (n));

Выкарыстанне typedef (вызначэнне тыпу) для апісання двухмернага масіву:

typedef vector <int> lv;

int main()

{

  int n, m;

  cout << "kol-vo strok i";

  cout << "stolbcov" << endl;

  cin >> m >> n;

  vector <lv> d(n, lv (m));

…

15.2. Фарміраванне двухмерных масіваў

Значэнні элементаў двухмернага масіву можна задаваць тымі ж спосабамі, што і элементаў аднамернага масіву.

Канстантныя значэнні элементам масіву можна задаць пры апісанні, запісаўшы іх у фігурныя дужкі (прыклад 15.2). Колькасць радкоў і слупкоў пры гэтым не паказваюць, памеры вызначаюцца аўтаматычна.

Даныя ў масіў могуць быць прачытаны з клавіятуры (прыклад 15.3) ці з файла. Задаваць значэнні элементам можна выпадковым чынам (прыклад 15.4). Для таго каб звярнуцца да кожнага элемента двухмернага масіву, неабходна два ўкладзеныя цыклы: першы будзе па чарзе фіксаваць нумар радка, а другі перабіраць усе элементы дадзенага радка.

Выводзяць элементы двухмернага масіву ў выглядзе табліцы, пераводзячы курсор пасля вываду чарговага радка (вывад элементаў рэалізаваны пры атрыманні выпадковых значэнняў у прыкладзе 15.4).

Калі ў масіве ёсць лікі з рознай колькасцю лічбаў, то ў якасці раздзяляльніка паміж элементамі ў адным радку можна выкарыстоўваць сімвал табуляцыі (пыклад 15.5) ці задаць шырыню для вываду значэння з дапамогай каманды setw (прыклад 15.6)

Прыклад 15.7. Зададзены лік n. Сфарміраваць двухмерны масіў з n радкоў і n слупкоў, які выглядае наступным чынам:

Этапы выканання задання

I. Зыходныя даныя: лік n.

II. Вынік: двухмерны масіў d.

III. Алгарытм рашэння задачы.

1. Увод зыходных даных.
2. Запаўняць масіў будзем у цыкле наступным чынам:

2.1. Пры апісанні ўсе элементы роўныя 0.
2.2. Элементы ў першым і апошнім радках, а таксама ў першым і апошнім слупках роўныя 1.
2.3. Элементы на дыяганалі роўны нумару радка +1.

3. Вывад выніку.

IV. Апісанне пераменных:
n – int, d – vector<vector <int>>.

Прыклад 15.2. Канстантныя значэнні ў двухмерным масіве:

vector <vector <int>> d = 

               {{1, 0, 0},

                {0, 1, 0},

                {0, 0, 1}};

Прыклад 15.3. Увод элементаў з клавіятуры:

cin >> m >> n; 

vector< vector<int> > d(m, vector <int>(n));

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

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

    cin >> d[i][j];

Прыклад 15.4. Выпадковыя значэнні [—5, 5]:

cin >> m >> n;

vector< vector<int> > d(m, vector <int>(n));

for (int i = 0; i < m; i++) {

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

    d[i][j] = rand() % 11 - 5;

    cout << d[i][j] << " ";

  }

  cout << endl;

}

Прыклад 15.5. Вывад элементаў праз табуляцыю:

for (int i = 0; i < m; i++) {

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

    cout << d[i][j] << '\t';

  cout << endl;

}

Прыклад 15.6. Вывад элементаў з устаноўкай шырыні друку:

for (int i = 0; i < m; i++) {

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

    cout << setw(5) << d[i][j];

  cout << endl;

}

Вынік вываду з прыкладаў 15.5 і 15.6.

Прыклад 15.7.

V. Праграма:

#include <iostream>

#include <vector>

#include <iomanip>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <vector <int>> d(n, vector <int> (n));

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

    d[0][i] = 1;

    d[n - 1][i] = 1;

    d[i][0] = 1;

    d[i][n - 1] = 1;

    d[i][i] = i + 1;

  }

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

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

      cout << setw(3) << d[i][j];

    cout << endl;

  }

  return 0;

}

VI. Тэсціраванне.

15.3. Апрацоўка двухмерных масіваў

Апрацоўка двухмерных масіваў дазваляе атрымаць якія-небудзь вынікі шляхам аналізу даных у масіве. Сам масіў пры гэтым не змяняецца. Задачы пошуку элементаў, якія задавальняюць умову, падліку сумы, пошуку максімальнага і інш. шмат у чым рашаюцца аналагічна таму, як гэта адбывалася для лінейных масіваў.

Прыклад 15.8. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Палічыць суму тых элементаў масіву, у якіх сума квадратаў нумара радка і нумара слупка роўная зададзенаму ліку x.

Этапы выканання задання

I.  Зыходныя даныя: пераменныя m і n (колькасць радкоў і слупкоў у масіве), d — двухмерны масіў, x (лік).

II.  Вынік: пераменная s (сума шуканых элементаў).

III. Алгарытм рашэння задачы..

1. Увод зыходных даных. Масіў уводзіцца паэлементна. 
2. Вызначэнне пачатковага значэння для сумы (s = 0). 
3. Правяраем бягучы элемент. Калі ён задавальняе ўмову, то дабаўляем яго да сумы. 
4. Вывад выніку.

IV. Апісанне пераменных: n, x, s – int, d – vector<vector <int>>

Прыклад 15.9. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Вызначыць, ці ёсць у масіве хоць бы адзін элемент, кратны x. Калі так, то вывесці індэксы яго месцазнаходжання.

Этапы выканання задання

I. Зыходныя даныя: пераменныя m і n (колькасць радкоў і слупкоў у масіве), d — двухмерны масіў, x (лік).

II. Вынік: пераменныя r, с (нумары радка і слупка, у якіх знойдзены элемент) або паведамленне «не знойдзены».

III. Алгарытм рашэння задач.

1. Увод зыходных даных. Масіў запаўняецца выпадковымі лікамі. 
2. Вызначэнне пачатковага значэння для шуканых індэксаў (r = -1, c = -1). 
3. Праверка бягучага элемента. Калі ён задавальняе ўмову, то мяняем значэнні r і c. 
4. Вывад выніку. Калі пераменныя r і c не змяніліся, то выводзім паведамленне, што элемент не знойдзены, інакш выводзім іх значэнні.

IV. Апісанне пераменных: n, x, r, c – int, d – vector<vector <int>>

Калі ў масіве некалькі элементаў, якія задавальняюць умову задачы, то будзе выведзены апошні знойдзены элемент. Калі патрэбны першы элемент, то можна ўвесці дадатковую пераменную-флаг, якая будзе роўная true, пакуль значэнні r і c не змяніліся. Пасля іх змянення яна стане false і значэнні r і c больш змяняцца не будуць (прыклад 15.10).

Прыклад 15.11. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Знайсці мінімальны і максімальны элементы і вывесці індэксы іх месцазнаходжання.

Этапы выканання задання

I. Зыходныя даныя: пераменныя m і n — колькасць радкоў і слупкоў у масіве, d — двухмерны масіў, x — лік.

II. Вынік: пераменныя r_min, c_min, r_max, c_max — нумары радка і слупка, у якіх знойдзены элемент.

III. Алгарытм рашэння задачы.

1. Увод зыходных даных. Масіў запаўняецца выпадковымі лікамі.
2. Вызначэнне пачатковага значэння для шуканых індэксаў (r_min = 0, c_min = 0, r_max = 0, c_max = 0).
3. Правяраем бягучы элемент. Калі ён большы за бягучы максімальны, то змяняем значэнні r_max, c_max.
4. Правяраем бягучы элемент. Калі ён меншы за бягучы мінімальны, то змяняем значэнні r_min, c_min.
5. Вывад выніку.

IV. Апісанне пераменных: n, m, n_min, c_min, r_max, c_max – int, d – vector<vector <int>>

Калі ў масіве некалькі элементаў, роўных максімальнаму (мінімальнаму), то будзе выводзіцца месцазнаходжанне першага з такіх элементаў. Калі трэба атрымаць месцазнаходжанне апошняга, то дастаткова замяніць знак «>» («<») на «>=» («<=»).

Прыклад 15.8.

V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int m, n;

  cout << "kol-vo strok m=";

  cin >> m;

  cout << "kol-vo stolbcov n=";

  cin >> n;

  cout << "elementy" << endl;

  vector <vector <int>> d(m, vector <int> (n));

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

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

      cin >> d[i][j];

  int x;

  cout << "x = ";

  cin >> x;

  int s = 0;

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

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

      if (i * i + j * j == x)

        s += d[i][j];

  cout << "summa = " << s << endl;

  return 0;

}

 VI. Тэсціраванне.

VII. Аналіз вынікаў. Будуць падсумаваны элементы, якія маюць нумары [1][2] і [2][1] (яны вылучаны).

У матэматыцы для матрыцы вызначаны паняцці галоўная дыяганаль і пабочная дыяганаль. На галоўнай дыяганалі знаходзяцца элементы матрыцы d[i][j], для якіх правільная ўмова i = j. Для элементаў пабочнай дыяганалі: i + j = n – 1 (n — число столбцов, нумерация с 0).

Прыклад 15.9.

V. Праграма:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdio>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int m, n;

  cout << "kol-vo strok m=";

  cin >> m;

  cout << "kol-vo stolbcov n=";

  cin >> n;

  cout << "elementy" << endl;

  vector <vector <int>> d(m, vector <int> (n));

  for (int i = 0; i < m; i++){

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

      d[i][j] = rand() % 100;

      cout << d[i][j] << " ";

    }

    cout << endl;

  }

  int x;

  cout << "x = ";

  cin >> x;

  int r = -1, c = -1;

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

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

      if (d[i][j] % x == 0){

        r = i;

        c = j;

      }

  if (r == -1 && c == -1)

    cout << "ne naiden";

  else {

    cout << d[r][c];

    cout << " naiden na meste ";

    cout << r << " " << c;

  }

  cout << endl;

  return 0;

}

 VI. Тэсціраванне.

Прыклад 15.10. Фрагмент праграмы:

bool f = true;

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

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

    if (f && d[i][j] % x == 0){

      r = i;

      c = j;

       f = false;

    }

Прыклад 15.11.

V. Праграма:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdio>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int m, n;

  cout << "kol-vo strok m=";

  cin >> m;

  cout << "kol-vo stolbcov n=";

  cin >> n;

  cout << "elementy" << endl;

  vector <vector <int>> d(m, vector <int> (n));

  for (int i = 0; i < m; i++){

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

      d[i][j] = rand() % 100;

      cout << d[i][j] << " ";

    }

    cout << endl;

  }

  int r_min = 0, c_min = 0;

  int r_max = 0, c_max = 0;

  for (int i = 0; i < m; i++){

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

      if (d[i][j] > d[r_max][c_max]){

       r_max = i;

       c_max = j;

     }

     if (d[i][j] < d[r_min][c_min]){

       r_min = i;

       c_min = j;

    }

  }

  cout << "max = " << d[r_max][c_max];

  cout << " naiden na meste ";

  cout << r_max << " " << c_max;

  cout << endl;

  cout << "min = " << d[r_min][c_min];

  cout << " naiden na meste ";

  cout << r_min << " " << c_min;

  cout << endl;

  return 0;

}

 VI. Тэсціраванне.

15.4. Пераўтварэнне двухмерных масіваў

Сярод задач пераўтварэння двухмернага масіву можна вылучыць наступныя:

  • пераўтварэнне элементаў масіву ў залежнасці ад умоў;
  • абмен месцамі двух радкоў;
  • выдаленне радка;
  • устаўка радка.

Рашэнне гэтых задач шмат у чым аналагічна рашэнню адпаведных задач для лінейнага масіву.

Прыклад 15.12. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Памяняць радкі ў матрыцы: першы з апошнім, другі з перадапошнім і г. д. Напрыклад:

Этапы выканання задання

I. Зыходныя даныя: пераменныя m і n — колькасць радкоў і слупкоў у масіве, d — двухмерны масіў.

II. Вынік: пераўтвораны масіў.

III. Алгарытм рашэння задачы.

1. Увод зыходных даных (з файла). 
2. У цыкле да паловы ад колькасці радкоў мяняем месцамі два элементы лінейнага масіву. 
3. Для абмену месцамі двух радкоў выкарыстоўваем метад swap.
4. Вывад выніку (у файл).

IV. Апісанне пераменных: n, m – int, d – vector<vector <int>>

Прыклад 15.13. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Выдаліць у ім слупкі з нумарамі ад k1 да k2.

Этапы выканання задання

 I. Зыходныя даныя: пераменныя m і n — (колькасць радкоў і слупкоў у масіве), d — двухмерны масіў, k1 і k2 — нумары слупкоў.

II.  Вынік: пераўтвораны масіў.

III. Алгарытм рашэння задачы.

1. Увод зыходных даных (з файла).
2. Ствараем масіў b, які будзе захоўваць у транспаніраваным выглядзе наш зыходны масіў. У ім будзем працаваць з радкамі. 
3. Выкарыстоўваючы метад erase, выдалім дыяпазон даных, вызначаны ітэратарамі b.begin() + k1 і b.begin() + k2 + 1 (слупок k2 таксама трэба выдаліць, таму +1). 
4. Вывад выніку (у файл). Для карэктнага вываду трэба памяняць месцамі цыклы, якія вызначаюць радок і слупок.

IV. Апісанне пераменных: n, m, k1, k2 – int, d – vector<vector <int>>

Пры захоўванні двухмернага вектара ў памяці камп’ютара яго радкі запісваюцца паслядоўна, адзін за адным. Такое захоўванне не дазваляе ў яўным выглядзе вылучыць слупок матрыцы. Калі ўзнікае неабходнасць апрацоўкі двухмернага масіву «па слупках», то можна ствараць  і выкарыстоўваць транспаніраваную [1]  матрыцу.

Прыклад 15.12

V. Праграма:

#include <iostream>

#include <fstream>

#include <vector>

 

using namespace std;

 

int main()

{

  ifstream fin("input.txt");

  ofstream fout ("output.txt");

  int m, n;

  fin >> m >> n;

  vector <vector <int>> d(m, vector <int> (n));

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

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

      fin >> d[i][j];

  for (int i = 0; i < m / 2; i++)

    d[i].swap(d[m - i - 1]);

  for (int i = 0; i < m; i++){

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

      fout << d[i][j] << " ";

    fout << endl;

  }

  return 0;

}

 VI. Тэсціраванне.

           

Прыклад 15.13.

 V. Праграма:

#include <iostream>

#include <fstream>

#include <vector>

 

using namespace std;

 

int main()

{

  ifstream fin("input.txt");

  ofstream fout ("output.txt");

  int m, n;

  fin >> m >> n;

  vector <vector <int>> d(m, vector <int> (n));

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

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

      fin >> d[i][j];

  ///транспонирование

  vector <vector <int>> b(n, vector <int> (m));

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

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

      b[j][i] = d[i][j];

  int k1, k2;

  fin >> k1 >> k2;

  b.erase(b.begin() + k1, 
         b.begin() + k2 + 1);

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

    for (int i = 0; i < b.size(); i++)

      fout << b[i][j] << " ";

    fout << endl;

  }

  return 0;

}

 VI. Тэсціраванне.

  


[1] Транспаніраванне матрыцы — аперацыя над матрыцай, калі яе слупкі становяцца радкамі з тымі ж нумарамі.

Пытанні да параграфу

1. Што такое размернасць масіву?

2. Як апісваецца двухмерны масіў?

3. Як знайсці мінімальны (максімальны) элемент у двухмерным масіве?

4. Якія аперацыі пераўтварэння двухмернага масіву вы можаце назваць?

Практыкаванні

    

1. Сфарміраваць двухмерныя масівы з n радкоў і n слупкоў, якія выглядаюць наступным чынам:

1.  2. 
3.  4. 

2. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Знайдзіце сумы тых элементаў з масіву, якія задавальняюць наступныя умовы.

    1. Рознасць нумара радка і нумара слупка роўна 1.
    2. Модуль рознасці нумара радка і нумара слупка роўны ліку x.
    3. Кратны ліку х.
    4. Размешчаны ніжэй за галоўную дыяганаль.
    5. Размешчаны вышэй за пабочную дыяганаль.

3. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Вызначыць, ці ёсць у масіве хоць бы адзін элемент, які задавальняе ўмову. Калі так, то вывесці індэксы яго месцазнаходжання.

    1. Роўны пяці элемент.
    2. Элемент, які з’яўляецца адмоўным лікам.
    3. Элемент, які дзеліцца на 3 і на 5.
    4. Элемент, які пры дзяленні на 3 і на 5 дае няцотныя астачы.

4. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Неабходна выканаць названыя дзеянні.

    1. Вывесці нумар радка, які змяшчае мінімальны элемент.
    2. Вывесці нумар слупка, які змяшчае максімальны элемент.
    3. Вывесці нумары ўсіх радкоў, у якіх ёсць элемент, роўны мінімальнаму.
    4. Вывесці нумары ўсіх слупкоў, у якіх ёсць элемент, роўны максімальнаму..

5. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Ажыццявіць абмены.

    1. Слупкі 0 begin mathsize 18px style left right double arrow end style (m – 1), 1  begin mathsize 18px style left right double arrow end style (m – 2),  ... (першы з апошнім, другі з перадапошнім...).
    2. Радкі 0 begin mathsize 18px style rightwards double arrow end style 1, 1 begin mathsize 18px style rightwards double arrow end style 2, ..., (m – 1) begin mathsize 18px style rightwards double arrow end style 0 (цыклічна ўніз на адзін).
    3. Слупкі 1 begin mathsize 18px style rightwards double arrow end style 0, 2 begin mathsize 18px style rightwards double arrow end style 1, ... 0 begin mathsize 18px style rightwards double arrow end style (n – 1) (цыклічна ўлева на адзін).
    4. Радкі 2 begin mathsize 18px style rightwards double arrow end style 0, 3 begin mathsize 18px style rightwards double arrow end style 1, 4 begin mathsize 18px style rightwards double arrow end style 2, ... (цыклічна ўверх на два).

6. Зададзены двухмерны масіў d з m радкоў і n слупкоў. Выдаліць названыя элементы.

    1. Радкі, у якіх ёсць лікі, што з’яўляюцца поўнымі квадратамі.
    2. Радкі, нумары якіх з’яўляюцца ступенню двойкі.
    3. Слупкі з нумарамі, кратнымі тром.
    4. Слупкі, у якіх ёсць простыя лікі.