§ 13. Максімальны і мінімальны элементы масіву

13.1. Пошук максімальнага (мінімальнага) элемента ў масіве

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

Разгледзім задачу знаходжання максімальнага элемента. Калі ў масіве толькі адзін адзінюткі элемент, то ён і ёсць максімальны. Калі элементаў больш за адзін, то максімальным у масіве з i элементаў з’яўляецца максімум з a[i] і максімальнага сярод першых i - 1 элементаў. Знаходзіць максімум будзем паслядоўна, параўноўваючы бягучы элемент з максімумам, знойдзеным на папярэднім кроку. Калі бягучы элемент большы, то значэнне максімуму, знойдзенае на папярэднім кроку, патрэбна абнавіць (прыклад 13.1).

Дадзены алгарытм знаходзіць значэнне максімальнага элемента, але не дазваляе вызначыць, на якім месцы ў масіве змешчаны гэты максімальны элемент.

Будзем выкарыстоўваць пераменную n_max для захоўвання індэкса максімальнага элемента. Значэнне пераменнай n_max будзе змяняцца тады, калі змяняецца значэнне максімальнага элемента (прыклад 13.2).

Калі ў масіве некалькі элементаў маюць максімальнае значэнне, то значэннем пераменнай n_max будзе індэкс першага з іх. Калі выкарыстоўваць умову a[i] >= max, то пераменная n_max будзе захоўваць індэкс апошняга з максімальных элементаў.

Калі вядомы індэкс i-га элемента масіву, то значэнне гэтага элемента можна атрымаць, звярнуўшыся да элемента па індэксе: a[i]. Таму пры пошуку максімальнага элемента дастаткова захоўваць толькі яго індэкс n_max. Значэнне максімальнага элемента — a[n_max] (прыклад 13.3).

Пошук мінімальнага элемента ажыццяўляецца аналагічна. У праграме дастаткова замяніць знак > ва ўмове аператара галінавання на знак < (прыклад 13.4). Імя пераменнай для захоўвання нумара мінімальнага элемента — n_min.

Прыклад 13.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];

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

  int Max = a[0];

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

    if (a[i] > Max)

      Max = a[i];

  cout << "max = " << Max;

  cout << endl;

  return 0;

}

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

Прыклад 13.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 Max = a[0], n_max = 0;

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

    if (a[i] > Max){

      Max = a[i];

      n_max = i;

    }

  cout << "max = " << Max;

  cout << " ego mesto " << n_max;

  cout << endl;

  return 0;

}

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

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

int n_max = 0;

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

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

    n_max = i;

cout << "max = " << a[n_max];

cout << " ego mesto " << n_max;

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

int n_min = 0;

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

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

    n_min = i;