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

§ 14. Пераўтварэнне элементаў масіву

Сайт: Профильное обучение
Курс: Інфарматыка. 10 клас (Павышаны ўзровень)
Книга: § 14. Пераўтварэнне элементаў масіву
Напечатано:: Гость
Дата: Вторник, 7 Май 2024, 03:14

Оглавление

14.1. Асноўныя задачы

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

1. Змяненне элементаў масіву ў залежнасці ад умоў.
2. Абмен месцамі элементаў у масіве.
3. Выдаленне элемента з масіву.
4. Устаўка элемента ў масіў.

Разгледзім падрабязней кожную з задач.

Некаторыя з задач пераўтварэння масіваў сустракаюцца вельмі часта. Таму ў клас vector былі дабаўлены функцыі, якія дазваляюць ператвараць масівы.

Шмат якія з функцый для пераўтварэння вектараў аналагічныя функцыям пераўтварэння радкоў як па сінтаксісе, так і выконваемым дзеянні. Спіс функцый можна паглядзець у Дадатку да главы 1.

14.2. Змяненне элементаў масіву ў залежнасці ад умоў

Прыклад 14.1. Зададзены аднамерны масіў цэлых лікаў. Пераўтварыць яго элементы па наступным правіле: дадатныя элементы замяніць значэннем 2, а адмоўныя — павялічыць на 5.

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

I. Зыходныя даныя: аднамерны масіў а, колькасць элементаў n.

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

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

1. Увод зыходных даных.
2. У цыкле правяраем бягучы элемент. Калі ён дадатны, то замяняем яго на 2. Калі адмоўны, то прыбаўляем да яго 5. Важна памятаць, што адмаўленнем умовы «элемент дадатны» з’яўляецца ўмова «элемент не дадатны», што мае на ўвазе магчымасць роўнасці элемента 0 (нулі не змяняюцца). Таму патрэбны два аператары галінавання для праверкі ўмовы задачы.
3. Вывад выніку.

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

Прыклад 14.1.

V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

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

    if (a[i] > 0)

      a[i] = 2;

    if (a[i] < 0)

      a[i] += 5 ;

  }

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

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

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

VII. Аналіз вынікаў. Элементы 3 і 5 заменены на 2, элементы —2 і —1 павялічаны на 5, элемент 0 застаўся нязменным, што адпавядае ўмове задачы..

14.3. Абмен месцамі элементаў у масіве

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

buf := a[i];

a[i] := a[k];

a[k] := buf;

Для абмену элементаў можна выкарыстоўваць убудаваную функцыю swap: swap(a[i], a[k]).

Прыклад 14.2. Зададзены аднамерны масіў цэлых лікаў. Памяняць месцамі максімальны і мінімальны элементы масіву. Мяркуецца, што кожны з іх сустракаецца ў масіве толькі адзін раз.

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

I. Зыходныя даныя: аднамерны масіў а, колькасць элементаў n.

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

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

1. Увод зыходных даных. 
2. Знойдзем максімальны элемент масіву і яго індэкс (n_max). 
3. Знойдзем мінімальны элемент масіву і яго індэкс (n_min). 
4. Памяняем месцамі элементы, якія стаяць на месцах n_max и n_min. 
5. Вывад выніку.

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

Прыклад 14.3. Зададзены аднамерны масіў цэлых лікаў. Цыклічна зрушыць усе элементы масіву ўлева на 1, першы на апошняе месца. Напрыклад, масіў 1 2 3 4 5 будзе ператвораны ў 2 3 4 5 1.

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

I. Зыходныя даныя: аднамерны масіў а, колькасць элементаў n.

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

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

1. Увод зыходных даных.
2. У цыкле ажыццявім абмен суседніх элементаў.
3. Вывад выніку.

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

Рашэннем задачы 14.3 можа быць таксама наступны алгарытм (прыклад 14.4):

1. Захаваем значэнне першага элемента ў буфернай пераменнай.
2. У цыкле зрушым усе элементы на 1 улева.
3. Запішам значэнне буфера на апошняе месца ў масіве.

Калі ў масіў дабавіць яшчэ адзін элемент у канцы, то яго можна выкарыстоўваць у якасці буфернай пераменнай. У гэтым выпадку ў цыкле трэба будзе зрабіць на 1 зрух больш. Затым выдаліць апошні элемент. Выдаліць апошні элемент можна з дапамогай каманды pop_back().

Фрагменты праграм у прыкладзе 14.5 паказваюць, як можна цыклічна зрушыць элементы масіву на 1 управа (апошні на першае месца).

Ажыццявім абмен элементаў  наступным чынам:

a[i] = a[k]; a[k] = a[i];

Тады мы страцім значэнне элемента, які стаіць першапачаткова на месцы a[i], і атрымаем два элементы са значэннем, роўным a[k].

Прыклад 14.2.

 V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

  //пошук мінімальнага элемента

  int n_min = 0;

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

    if (a[i] < a[n_min])

      n_min=i;

  //пошук максімальнага элемента

  int n_max = 0;

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

    if (a[i] > a[n_max])

      n_max=i;

  swap (a[n_min], a[n_max]);

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

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

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

Прыклад 14.3.

V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

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

    swap (a[i], a[i + 1]);

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

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

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

Прыклад 14.4.

V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

  a.push_back(a[0]);

  //зрух улева

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

    a[i] = a[i + 1];

  a.pop_back();

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

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

Прыклад 14.5. Цыклічны зрух управа на 1. Фрагменты праграм:

for (int i = n - 1; i > 0; i--)

  swap (a[i], a[i - 1]);

  

a.push_back(a.back());

  //зрух управа

for (int i = n - 1; i > 0; i--)

  a[i] = a[i - 1];

a.front() = a.back();

a.pop_back();

14.4. Паняцце ітэратара

Ітэратар — абагульнены паказальнік [1], які дазваляе карыстальніку перабіраць без неабходнасці ведаць, як рэалізаваны сам кантэйнер.

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

Для вектара вызначаны стандартныя ітэратары begin() і end(). Итэратар begin() паказвае на першы элемент у вектары. Ітэратар end() — на месца пасля апошняга элемента вектара.

Для любога ітэратара (it) даступныя наступныя аперацыі (прыклад 14.6):

  • інкрэмент (it++) — для доступу да наступнага элемента;
  • разнайменне (*it) — для атрымання значэння элемента;
  • аператары роўнасці (it1 = = it2) і няроўнасці (it1 != it2) для вызначэння таго, ці супадаюць два ітэратары.

Для вектара ітэратар забяспечвае дадатковую функцыянальнасць:

  • дабаўленне канстанты (it += 20 зрушыцца на 20 элементаў наперад);
  • адлегласць паміж ітэратарамі 
    (int dist = it2 - it1).

Пачынаючы са стандарта C++11, абход вектара з дапамогай 

vector <int> a(n);

for (auto i: a)

  cout << i << " ";

Пераменная i, тып якой вызначаецца аўтаматычна, будзе па чарзе атрымліваць значэнні элементаў вектара. Такім чынам можна атрымаць значэнні элементаў вектара, але немагчыма атрымаць індэкс элемента. Такі цыкл называюць цыклам foreach, або цыклам, заснаваным на дыяпазоне.

[1] Паказальнік — пераменная, якая абазначае адрас памяці. Паказальнік  прызначаны для прамога звароту па адрасе памяці да аб’екта, які размешчаны па гэтым адрасе.

Для вектара вызначаны таксама рэверсіўныя (адваротныя) ітэратары, якія дазваляюць перабіраць элементы кантэйнера ў адваротным напрамку. Для атрымання рэверсіўнага ітэратара ўжываюцца функцыі rbegin() і rend(). Итэратар rbegin()паказвае на канец бягучага вектара, а ітэратар rend() — на пачатак вектара.

Прыклад 14.6. Аперацыі з ітэратарам

vector <int> a = {1, 2, 3, 5, 9};

vector <int> :: iterator it;

Разгледзім аперацыю:

int x;

it = a.begin();

x = *it;

cout << x << endl;

Ітэратар it паказвае на пачатак вектара. Значэнне пераменнай x — значэнне элемента вектара, на які паказвае ітэратар. Будзе выведзена значэнне 1.

it++;

cout << *it << endl;

Ітэратар зрушыўся на адзін элемент і цяпер паказвае на элемент з індэксам 1, будзе выведзена значэнне 2.

it = a.begin() + 3;

cout << *it << endl;

Ітэратар зрушыўся на 3 элементы ад пачатку і паказвае на элемент з індэксам 3, будзе выведзена значэнне 5.

if (it == a.begin())

  cout << boolalpha << true;

else

  cout << boolalpha << false;

Пасля папярэдняй аперацыі ітэратар паказвае на элемент з індэксам 3, таму будзе выведзена false.

int dist1 = it - a.begin();

int dist2 = a.end() - a.begin();

cout <<  dist1 << endl;

cout <<  dist2 << endl;

Будуць выведзены значэнні 3 і 5. Значэнне 5 — колькасць элементаў у вектары.

Цыклу foreach адпавядае наступны запіс цыкла for:

vector <int> :: iterator i;

for (i = a.begin();

     i != a.end();

     i++)

  cout << *i << " ";

або

  cout << "a % b = " << d << endl;

  cout << "a % b = " << d << endl;

for (auto i = a.begin();

  cout << "a % b = " << d << endl;

     i != a.end();

     i++)

  cout << *i << " ";

14.5. Выдаленне элемента з масіву

Для выдалення з масіву элемента, які стаіць на месцы k, трэба зрушыць на адну пазіцыю ўлева ўсе элементы, якія стаяць пасля яго. Колькасць элементаў пры гэтым памяншаецца на 1. Гэтыя дзеянні рэалізаваны ў функцыі erase, якая належыць класу vector. Даступныя два варыянты выкліку гэтай функцыі:

erase(pos)

Выдаляе адзін элемент

erase(first, last)

Выдаляе элементы ў дыяпазоне [first; last)

Параметрамі функцыі erase з’яўляюцца ітэратары. Калі трэба выдаліць, напрыклад, пяты элемент, то параметр функцыі можа быць запісаны так: a.begin() + 5.

Прыклад 14.7. Зададзены аднамерны масіў цэлых лікаў. Выдаліць з яго ўсе лікі, кратныя 5. Колькі лікаў выдалілі?

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

I. Зыходныя даныя: аднамерны масіў а, колькасць элементаў n.

II. Вынік: пераўтвораны масіў a і колькасць выдаленых лікаў k.

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

1. Увод зыходных даных. 
2. Будзем паслядоўна праглядаць элементы масіву. Калі знойдзем лік, кратны 5, то выдалім яго з масіву, выкарыстоўваючы функцыю erase. Паколькі колькасць выдаляемых элементаў загадзя невядомая, то выкарыстаем цыкл while. 
3. Пры выдаленні элемента лічыльнік k будзем павялічваць на 1. 
4. Вывад выніку.

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

Паколькі элементы пры выдаленні зрушваюцца ўлева, абыходзіць масіў можна з канца (прыклад 14.8).

Прыклад 14.7.

V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

  int i = 0, k = 0;

  while (i < a.size()){

    if (a[i] % 5 == 0){

      a.erase(a.begin() + i);

      k++;

    }

    else

      i++;

  }

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

    cout << a[i] << " ";

  cout << endl << "udalili ";

  cout << k << " elementov" << endl;

  return 0;

}

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

VII. Аналіз вынікаў. Элементы 5, 15, 35, 10 і 30 кратныя 5, таму іх выдалілі з масіву. Элементы 3 і 4 не кратныя 5, таму яны засталіся ў масіве і зрушыліся ў пачатак.

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

for (int i = n - 1; i >=0; i-- )

  if (a[i] % 5 == 0)

    a.erase(a.begin() + i);

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

  cout << a[i] << " ";

cout << endl << "udalili ";

cout << n - a.size();

cout << " elementov" << endl;

Лічыльнік k можна не выкарыстоўваць, колькасць выдаленых элементаў можна знайсці як рознасць паміж пачатковай колькасцю элементаў n і даўжынёй вектара пасля выдалення элементаў:

n – a.size().

14.6. Устаўка элемента ў масіў

Для ўстаўкі элемента на месца k неабходна вызваліць гэта месца ў масіве. Для гэтага трэба зрушыць на адну пазіцыю ўправа ўсе элементы масіву, якія стаяць пасля k - 1. Зрух пачынаем з апошняга элемента. Колькасць элементаў у масіве павялічыцца на 1. Гэтыя дзеянні рэалізаваны ў функцыі insert. Маюцца наступныя магчымасці выкліку функцыі insert:

insert(pos, value)

Устаўляе value перад элементам, на які паказвае pos

insert(pos, value, count)

Устаўляе count копій значэння value перад элементам, на які паказвае pos

insert(pos, first, last)

Устаўляе элементы з дыяпазону [first, last) перад элементам, на які паказвае pos

Параметры pos, first, last з’яўляюцца ітэратарамі.

Прыклад 14.9. Зададзены масіў цэлых лікаў. Уставіць лік x а k-е месца, калі  элемент a[k] кратны x.

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

I. Зыходныя даныя: аднамерны масіў а, колькасць элементаў n, лік, які трэба ўставіць у масіў x.

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

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

1. Увод зыходных даных.
2. У цыкле правяраем элементы масіву.
3. Калі бягучы элемент кратны x, то ўстаўляем лік x у масіў.
4. Вывад выніку.

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

Прыклад 14.9.

V. Праграма:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

  int x;

  cout << "x = ";

  cin >> x;

  for (int i = n - 1; i >= 0; i--)

    if (a[i] % x == 0)

      a.insert(a.begin() + i, x);

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

    cout << a[i] << " ";

  cout << endl;

  return 0;

}

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

VI. Аналіз вынікаў. Лік 5 устаўлены перад значэннямі 10, 15, 30, 20, 45.

У праграме выкарыстоўваецца абход масіву з канца. Калі ў праграме запісаць такі цыкл:

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

  if (a[i] % x == 0)

    a.insert(a.begin() + i, x);

то праграма можа зацыкліцца. Напрыклад, на нулявым месцы стаіць лік 10, які задавальняе ўмову задачы. На яго месца ўставілі лік 5. Лік 10 зрушыўся на пазіцыю 1 і будзе зноў правярацца на наступнай ітэрацыі цыкла, і зноў зрушыцца ўправа.

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

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

2. Як можна памяняць месцамі два элементы ў масіве?

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

4. Як уставіць элемент у масіў?

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

    

1. Ці можна ў прыкладзе 14.1 замяніць каманды пад № 1 камандамі пад № 2?

1.  if (a[i] > 0)

      a[i] = 2;

    if (a[i] < 0)

      a[i] += 5 ;

 

2.  if (a[i] < 0)

      a[i] += 5 ;

    if (a[i] > 0)

      a[i] = 2;

У якіх выпадках праграма будзе даваць няправільны вынік?

2. Зададзены аднамерны масіў. Пераўтварыце яго элементы па наступным правіле: з усіх дадатных элементаў адняць элемент з нумарам k, да ўсіх адмоўных дадаць уведзены лік x. Нулявыя элементы пакіньце без змянення.

3. Зададзены аднамерны масіў з цотнай колькасці элементаў. Памяняйце месцамі яго «паловы»: 1 2 3 4 5 6 → 4 5 6 1 2 3.

4. У масіве запісана інфармацыя пра навучэнцаў класа (прозвішча і імя). З класа выбылі два навучэнцы. Вядомыя нумары гэтых навучэнцаў. Выключыце іх даныя з масіву.

5. Перастаўце першы элемент масіву на апошняе месца, другі — на першае, трэці — на другое і г. д. 1 2 3 4 5 6 → 6 5 4 3 2 1.

6. Выканайце цыклічныя зрухі элементаў у масіве.

1. На два элементы ўправа 1 2 3 4 5 6 → 5 6 1 2 3 4.
2. На два элементы ўлева 1 2 3 4 5 6 → 3 4 5 6 1 2.
3. На k элементаў управа. Лік k уводзіцца.
4. На k элементаў улева. Лік k уводзіцца.

7. Разбіць элементы масіву на групы по 4. У кожнай чацвёрцы выканаць цыклічны зрух улева на 1. Першы на 4-е месца. Калі колькасць элементаў у масіве не кратная 4, то для апошняй групы зрух ажыццяўляецца для той колькасці элементаў, якая засталася.

8. Выдаліць з масіву ўсе адмоўныя элементы. Вывесці пераўтвораны масіў.

9. Выдаліць з масіву ўсе элементы, якія з’яўляюцца поўнымі квадратамі (напрыклад, 9, 25, 64).

10. Выдаліць з масіву ўсе элементы, якія з’яўляюцца ступенню 2.

11. Зададзены лінейны масіў, элементамі якога з’яўляюцца словы. Выдаліце з яго названыя словы.

1. Словы, якія пачынаюцца на зычную літару.
2. Словы, у якіх менш за 5 зычных.
3. Словы, якія з’яўляюцца паліндромамі.

12. Уставіць элемент x у пазіцыю x. Калі x ≤ 0 або x ≥ n, уставіць яго на першае або апошняе месца адпаведна.

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