 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Завдання 7. Знаходження min, max у масиві
Розв’язуючи завдання, часто доводиться здійснювати пошук мінімального і максимального значень.
Класичний варіант знаходження min та max полягає в тому, щоб знайти мінімальний і максимальний елементи масиву і запам’ятати їхні порядкові номери.
Шуканих елементів може бути кілька, але запам’ятовуватися будуть порядкові номери тільки першого або останнього мінімального (максимального) елементів, залежно від того, строга або нестрога нерівність зазначена в умові.
Опишемо алгоритм пошуку:
1. Спочатку передбачається, що деякий елемент масиву є мінімальним і максимальним. Висловлюється припущення, що це перший елемент таблиці, і його вміщують, відповідно, у комірки min і max, а в комірках imin, imax ( jmin, jmax ) запам’ятовується порядковий номер ( а );
2. У циклі (ах) елементи масиву порівнюються із вмістом комірок min і max, і більші з них заносяться в max, а менші – в min, з одночасним запам’ятовуванням порядкових номерів.
3. Видається результат пошуку.
ПРОГРАМІСТИ-ПОЧАТКІВЦІ ПРИПУСКАЮТЬСЯ ПОМИЛОК У ЦЬОМУ АЛГОРИТМІ, ВСТАНОВЛЮЮЧИ ПОЧАТКОВЕ ЗНАЧЕННЯ min АБО max РІВНИМ 0, А ЦЕ НЕ ЗАВЖДИ ПРАВИЛЬНО. НАПРИКЛАД, ЯКЩО У МАСИВІ ВСІ ЕЛЕМЕНТИ ВІД’ЄМНІ, А ВИ ХОЧЕТЕ ЗНАЙТИ МАКСИМАЛЬНИЙ ЕЛЕМЕНТ, ТО ВСТАНОВЛЕНЕ ПОЧАТКОВЕ ЗНАЧЕННЯ max, ЩО ДОРІВНЮЄ 0, БУДЕ МАКСИМАЛЬНИМ, А ЦЕ НЕПРАВИЛЬНО, ОСКІЛЬКИ НУЛЬОВОГО ЕЛЕМЕНТА В МАСИВІ НЕМАЄ!
Класичний варіант алгоритму знаходження мінімального і максимального елементів масиву можна подати алгоритмом:
| АЛГ m1 (ціл n, дійсн Таб A[1:n], min, max, ціл imax, imin) АРГ n, A РЕЗ max, imax, min, imin ПОЧ ціл і max:=A[1]; imax:=1 min:=A[1]; imin:=1 для і від2 до n пц якщо A[i]>max то max:=A[i]; imax:=i інакше якщо A[i]<min то min:=A[i]; imin:=i все все кц ДРУКУВАТИ max, imax, min, imin КІН | АЛГ m2 (ціл m, n, дійсн Таб A[1:m, 1:n], min, max, ціл imax, jmax, imin, jmin) АРГ m, n, A РЕЗ max, imax, jmax, min, imin, jmin ПОЧ ціл і, j max:=A[1, 1]; imax:=1; jmax:=1 min:=A[1, 1]; imin:=1; jmin:=1 для і від 1 до m пц для j від 1 до n пц якщо A[і, j]> max то max:=A[і, j]; imax:=і; jmax:=j інакше якщо A[і, j]<min то min:=A[і, j] imin:=і; jmin:=j все все кц кц ДРУКУВАТИ max, imax, jmax, min, imin, jmin КІН |
МОЖНА ЗМЕНШИТИ КІЛЬКІСТЬ ЗМІННИХ ТА КІЛЬКІСТЬ ОПЕРАЦІЙ (А ЦЕ ПРИСКОРИТЬ ВИКОНАННЯ АЛГОРИТМУ), ЯКЩО ЗАПАМ’ЯТОВУВАТИ ТІЛЬКИ ПОЛОЖЕННЯ ШУКАНОГО ЕЛЕМЕНТА (min АБО max) В МАСИВІ!
У цьому випадку ми користуємося тільки змінними imin (jmin) та imax (jmax) та отримуємо алгоритм мовою Паскаль:
| Program min_max1; Const n=100; varA:array[1..n] of real; i, imin, imax:word; begin imin:=1; imax:=1; for i:=2 to n do if A[i]>=A[imin] thenimin:=1; else if A[i]>A[imax] then imax:=I; writeln (‘ Мінімум= ‘, A[imin], ‘ знаходиться на місці ‘, imin); writeln(‘ Максимум= ‘, A[imax], ‘ знаходиться, imax, ‘ місці‘); end. | Program min_max2; Const n=15; k=8; var A:array[1..n, 1..k] of real; і, j, imin, jmin, imax, jmax:word; begin imin:=1; jmin:=1; imax:=1; jmax:=1; for i:=1 to n do for j:=1 to k do if A[і, j]<A[imin, jmin] then begin imin:=і; jmin:=j; end else if A[і, j]>A[imax, jmax] then begin imax:=i; jmax:=j; end; writeln(‘min=’, A[min, jmin], ‘ знаходиться у ‘, imin, ‘ рядочку та ‘, jmin, ‘ стовпчику ‘); writeln(‘max=’, A[imax, jmax], ‘ знаходиться у ‘, imax, ‘ рядочку та ‘, max, ‘ стовпчику ‘); end. |
Поиск по сайту: