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

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

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

Оглавление

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;

13.2. Рашэнне задач з выкарыстаннем алгарытму пошуку максімальнага (мінімальнага) элемента

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

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

I. Зыходныя даныя: масіў a — лікі, якія з’яўляюцца часам праходжання трасы, лік спартсменаў — n.

II. Вынік: a[n_min] — мінімальны час, n_min — нумар пераможца.

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

1. Увод зыходных даных.
2. Для рашэння задання выкарыстаем алгарытм пошуку мінімальнага элемента ў масіве і яго нумара (прыклад 13.4).
3. Вывад выніку. Нумар лыжніка на 1 большы за нумар элемента ў масіве, бо элементы нумаруюцца з нуля.

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

Прыклад 13.6. Вызначыць, колькі разоў у лінейным масіве сустракаецца элемент, роўны мінімальнаму.

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

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

II. Вынік: a[n_min] — мінімальны элемент, k — колькасць мінімальных.

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

1. Увод зыходных даных.
2. Пошук мінімальнага элемента.
3. Лінейны пошук элементаў, роўных мінімальнаму.
4. Вывад выніку.

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

Прыклад 13.7. Зададзены масіў са слоў. Знайсці ў ім самае доўгае і самае кароткае слова.

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

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

II. Вынік: a[n_min] — кароткае слова, a[n_max] — доўгае слова длинное слово.

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

1. Увод зыходных даных.
2. Пошук самага кароткага слова. Самае кароткае слова — слова, у якім мінімальная колькасць сімвалаў. Для яго пошуку можна выкарыстаць алгарытм пошуку мінімальнага элемента ў масіве. Аднак, калі параўноўваць самі элементы масіву, то параўнанне будзе адбывацца не па даўжыні [1]. Для параўнання радкоў па даўжыні трэба выкарыстаць функцыю вылічэння даўжыні радка length.
3. Для пошуку самага доўгага слова можна выкарыстоўваць алгарытм пошуку максімальнага элемента і параўноўваць элементы з выкарыстаннем функцыі, якая вылічвае даўжыню радка length.
4. Вывад выніку.

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

[1] Параўнанне радкоў ажыццяўляецца лексікаграфічна: s1 < s2, калі для першага несупадаючага сімвала з нумарам i правільна, што s1[i] < s2[i], або ўсе сімвалы радкоў супадаюць, але s1 карацейшая s2.

Прыклад 13.5.

V. Праграма:

#include <iostream>

#include <fstream>

#include <vector>

 

using namespace std;

 

int main()

{

  setlocale(0,"");

  ifstream fin("input.txt");

  int n;

  fin >> n;

  vector <double> a(n);

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

    fin >> a[i];

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

  int n_min = 0;

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

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

      n_min = i;

  cout << "пераможца — лыжнік №";

  cout << n_min + 1 << endl;

  cout << "яго час - "<< a[n_min];

  cout << endl;

  return 0;

}

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

Прыклад 13.6.

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 k = 0;

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

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

      k++;

  cout << "min = "<< a[n_min];

  cout << endl << "vstretilsja ";

  cout << k << " raz" << endl;

  return 0;

}

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

Прыклад 13.7.

V. Праграма:

#include <iostream>

#include <vector>

#include <string>

 

using namespace std;

using namespace std::__cxx11;

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <string> 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].length() < a[n_min].length())

      n_min = i;

  //пошук максімальнага слова

  int n_max = 0;

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

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

      n_max = i;

  cout << "min - "<< a[n_min];

  cout << ", max - "<< a[n_max];

  cout << endl;

  return 0;

}

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

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

1. Які элемент масіву з’яўляецца максімальным? Які мінімальным

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

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

4. Якім чынам вызначыць нумар першага элемента, роўнага максімальнаму?

5. Як вызначыць нумар апошняга элемента, роўнага мінімальнаму?

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

    

1. Змяніце праграмы з прыкладаў 13.1 і 13.2 так, каб знаходзіўся мінімальны элемент у масіве.

2. Для прыкладу 13.5 выканайце пералічаныя заданні.

1. Знайдзіце нумар спартсмена, які прыйшоў на фініш апошнім.
2. Вызначыце, ці быў пераможца адзіным або ёсць яшчэ лыжнік, які прайшоў трасу з такім жа вынікам (гл. прыклад 13.6).
3. Дабаўце яшчэ адзін масіў і ўвядзіце ў яго прозвішчы спартсменаў. Рэалізуйце пункты 1 і 2 так, каб выводзілася прозвішча, а не нумар (гл. прыклад 12.9).

3. Напішыце праграму, якая заменіць у масіве нулямі ўсе элементы, роўныя мінімальнаму.

4. Напішыце праграму, якая заменіць у масіве нулямі ўсе элементы, якія стаяць перад максімальным. Мяркуецца, што ў масіве адзіны максімальны элемент.

5. Напішыце праграму, якая заменіць нулямі ўсе элементы ў масіве, што стаяць пасля мінімальнага. Калі мінімальных элементаў некалькі, то замяняць трэба элементы, што стаяць пасля апошняга мінімальнага.

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

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

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

9. У масіве захоўваецца інфармацыя пра кошт аўтамабіляў. Вызначыце кошт самага дарагога аўтамабіля і яго нумар у масіве. Калі ёсць некалькі такіх аўтамабіляў, то выведзіце ўсе нумары.

10. У масіве захоўваецца інфармацыя пра сярэднясутачную тэмпературу снежня. Вызначыце, колькі ў снежні было дзён з самай нізкай і з самай высокай тэмпературай.

11. Памеры n прамавугольнікаў захоўваюцца ў двух масівах (даўжыня і шырыня). Знайдзіце прамавугольнік з мінімальным перыметрам. (Вывесці нумар прамавугольніка і значэнне перыметра.)

12. Вядомы даныя пра масу (у кг) і аб’ём (у см3) n прадметаў, вырабленых з розных матэрыялаў. Знайдзіце прадметы з мінімальнай і максімальнай шчыльнасцямі. Выведзіце нумар прадмета і значэнне шчыльнасці.

13. Зададзены масіў са слоў. Знайдзіце ў ім самае доўгае слова, якое заканчваецца літарай «а».

14. Зададзены масіў са слоў. Знайдзіце ў ім самае кароткае слова, якое пачынаецца з вялікай літары.

15. Зададзены масіў са слоў. Знайдзіце ў ім слова, у якім максімальная колькасць галосных літар. Калі такіх слоў некалькі, выведзіце ўсе.

16. Зададзены масіў са слоў. Знайдзіце ў ім слова, у якім мінімальная колькасць зычных літар. Калі такіх слоў некалькі, то выведзіце самае доўгае з іх.