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

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();