Пошук в масиві елементів з деякою властивістю

Матеріал з Фізмат Вікіпедії
Перейти до: навігація, пошук

Тема уроку: Пошук в масиві елементів з деякою властивістю

Мета уроку: вивчити алгоритм пошуку елемента з певною властивістю на основі алгоритму пошуку максимального елемента та його номера (індексу) в одновимірному масиві та запис цього алгоритму мовою програмування Pascal; розглянути приклади застосування даного алгоритму при розв'язуванні задач; розвивати в учнів кругозір, уважність, допитливість, зв’язне специфічне мовлення; виховувати в учнів допитливість, культуру мовлення

Тип уроку: виховувати в учнів допитливість, культуру мовлення

Наочність: таблиці

Девіз уроку: «Хто шукає, той завжди знайде!»

План уроку

  1. Організаційна частина [2 хв.].
  2. Актуалізація опорних знань учнів [5 хв.].
  3. Повідомлення нової теми [30 хв.].
  4. Підсумок уроку [4 хв.].
  5. Домашнє завдання [2 хв.].

Хід уроку

Оголошую тему та мету уроку.

На уроці ми розглянемо ще один базовий алгоритм (базову задачу) по опрацюванню масивів та його практичне застосування при розв'язуванні певних задач. А зараз повторимо, що ми знаємо про масиви.

Актуалізацію опорних знань здійснюю фронтальним опитуванням.

Запитання :

  1. Що таке масив?
  2. Що називається індексом масиву?
  3. Як ще називають елементи масиву?
  4. Які типи змінних називаються простими, а які структурованими? Чому?
  5. Які масиви ви знаєте?
  6. Що таке одновимірний та двовимірний масив? Опис цих масивів мовою Паскаль.
  7. Наведіть приклади одновимірних масивів.
  8. Наведіть приклади двовимірних масивів.
  9. Які методи заповнення одновимірного (двовимірного) масиву ви знаєте?
  10. Виведення одновимірного (двовимірного) масиву на екран.
  11. Який порядок роботи з масивом?

Повідомлення нового матеріалу

Сьогодні ми розглянемо алгоритм пошуку елемента з певною властивістю. За основу візьмемо алгоритм пошуку максимального елемента та його номера в одновимірному масиві A[1..n].

По таблицях розглядаємо дану задачу.

Масив A[1..n]. n=5.

1 2 3 4 5
-5.2 6 1.6 6 -2

Для організації пошуку в таблиці елементів із заданими властивостями необхідно організувати циклічний перегляд всіх елементів, кожний з яких командою розгалуження порівняти із заданим еталоном або перевірити на деяку властивість. Якщо масив одновимірний, цикл для організації перегляду всіх елементів буде один, якщо ж масив двовимірний - циклів буде два.


Приклад 1

Знайти значення та номер (індекс) максимального елемента одновимірного масиву A[1..N].


Основна ідея алгоритму розв’язання цієї задачі: вважаємо, що найбільший елемент є А[1]. Запам’ятовуємо це значення в змінній МАХ, а індекс елемента - в змінній К, тобто МАХ=А[1], К=1. Далі порівнюємо значення МАХ з наступними значеннями елементів, якщо значення МАХ менше за значення елемента, то МАХ присвоюють значення цього елемента, а К - значення індекса цього елемента.

Program Max_Element;

Uses Crt;

Var i, k: word; {k – індекс найбільшого елемента}

max: real; {mas – значення найбільшого елемента}

a: array[1..100] of real;

Begin

Clrscr;

Write('Введіть кількість елементів масиву (<=100): ');

Readln(N);

For i:=1 to N do

Begin

Write(‘A[‘;i;’]=’);

Readln(A[i]); {Заповнення масиву }

End;

max:=a[1]; k:=1;

For i:=2 to N do

Begin

If max<a[i] then

Begin

max:=a[i]; {запам’ятовування значення найбільшого елемента}

k:=і {запам’ятовування індекса найбільшого елемента}

End;

End;

Writeln(‘MAX=’,max); {вивід значення найбільшого елемента}

Writeln(‘Номер найбільшого елемента - ’,k); {вивід індекса найбільшого елемента}

Readkey; {Затримка зображення на екрані}

End.

Далі учні завантажують програму MAX.РAS; запускають дану програму на виконання. За допомогою учнів виясняю, які зміни необхідно зробити в даній програмі, щоб знайти мінімальний елемент та його номер.

Даю учням запитання: “Як ви думаєте, при розв'язуванні яких задач можна використати даний алгоритм ?” Учні наводять свої приклади. Наводжу свої приклади застосування даного алгоритму при розв'язуванні задач: визначення найвищої та найнижчої температури протягом дня, місяця, року; визначення найвищого учня в класі; визначення переможця змагань; визначення найвищої вершини; найбільш населене місто, країну та інше.


Приклад 2

Дано масив В[1..М]. Вивести на екран індекс першого елемента, значення якого менше заданого числа К.


Для спрощення відлагодження програми доречно використовувати автоматичне заповнення масиву за допомогою генератора випадкових чисел, а з метою перевірки правильності роботи програми після заповнення масив виводиться на екран.

Слід наголосити учням, що таких елементів в масиві може бути багато, може бути один, або взагалі не бути. Тому для перегляду всіх елементів масиву доцільно використати цикл WHILE, для того, щоб завчасно вийти з циклу, якщо такий елемент знайдено. Для виходу з циклу можна використати змінну Х значення якої потрібно змінити при знаходженні елемента, що задовільняє дану умову (нехай Х:=0, якщо елемента не знайдено і Х:=1, якщо його знайшли).

Програма, що реалізує розв'язок цієї задачі, має наступний вигляд:

Program Element_К;

Uses Crt;

Const m=20; {m – розмірність масиву}

Var i, n: word; {n – номер шуканого елемента}

x: byte; {x – прапорець, що вказує чи знайшли заданий елемент, чи ні, (0 – не знайдено, 1 - знайдено)}

k: real; {k – задане число}

b: array[1..m] of real;

Begin

Clrscr;

Write(‘Введіть значення К - ’);

Readln(k);

For i:=1 to m do

Begin

b[i]:=random(100); {Заповнення масиву випадковими числами}

Write(b[i]:5); {Виведення масиву на екран для контролю правильності роботи програми}

End;

Writeln; {перехід на новий рядок}

x:=0; {прапорцю надаємо значення 0 – елемента не знайдено}

i:=1;

While (i<=m) and (x=0) do

Begin

If b[i]<k then

Begin

n:=i; {запам’ятовування номера знайденого елемента}

x:=1 {прапорцю надаємо значення 1 – елемент знайдено}

End;

inc(i) {збільшення номера елемента, що переглядається на 1}

End;

If x=1 then writeln(‘Номер першого елемена меншого ’,k,’ рівний ’,n) else writeln(‘Такого елемента не існує’); {вивід результату на екран}

Readkey; {Затримка зображення на екрані}

End.

На закріплення розглядаю задачу з обласної олімпіади:


Приклад 3

Задана послідовність будинків проспекту Знань. Кожен будинок характеризується номером та висотою. Знайти номери найвищого та найнижчого будинків на проспекті.


На перший погляд задача досить проста, але в цій задачі необхідно передбачити всі можливі варіанти: всі будинки можуть бути рівними між собою, є один або декілька найвищих та найнижчих будинків.

Нехай будинків є N. Запам’ятовуємо висоти цих будинків в масиві А розмірності N. Вважаємо, що найвищий і найнижчий будинок є перший і запам’ятовуємо відповідно висоти і номери цих будинків. Далі, аналогічно як і в першій задачі шукаємо значення і номери останніх найвищого та найнижчого будинків. Оскільки найвищих та найнижчих будинків може бути декілька, то окремо виводимо номери всіх найвищих та найнижчих будинків, для цього використовуємо окремо два цикли з параметром. Для виводу номерів найвищих будинків переглядаємо всі елементи з першого до останнього найвищого, а для найнижчих – з першого до останнього найнижчого.

Програма, що реалізує розв'язок цієї задачі, має наступний вигляд:

Program Znanj;

Uses Crt;

Var i, k_max, k_min, n:word; {k_max – номер найвищого будинку; k_min – номер найнижчого будинку; n – кількість будинків}

max, min:real; {max – висота найвищого будинку, min – висота найнижчого будинку}

a: array[1..100] of real;

Begin

Clrscr;

Write('Введіть кількість будинків (<=100): ');

Readln(N);

For i:=1 to N do

Begin

Write(‘Висота ‘;i;’-го будинку рівна ’);

Readln(A[i]); {Заповнення масиву }

End;

max:=a[1]; k_max:=1; {вважаємо, що перший будинок є найвищим і запам’ятовуємо його номер}

min:=a[1]; k_min:=1; {вважаємо, що перший будинок є найнижчим і запам’ятовуємо його номер}

For i:=2 to N do

Begin

If max<=a[i] then

Begin

max:=a[i]; {запа’ятовування висоти найвищого будинку}

k_max:=і { запа’ятовування номера найвищого будинку }

End;

If min>=a[i] then

Begin

min:=a[i]; {запа’ятовування висоти найнижчого будинку}

k_min:=і {запа’ятовування номера найнижчого будинку}

End;

End;

{Перевіряємо чи всі будинки не є рівними по висоті}

If max=min then writeln(‘Всі будинки рівні’) else

Begin

Write(‘Номери найвищих будинків рівні ’);

For i:=1 to k_max do if max=a[i] then write(i,’, ‘); {Вивід номерів найвищих будинків (їх може бути декілька)}

Writeln; {перехід на новий рядок}

Write(‘Номери найнижчих будинків рівні ’);

For i:=1 to k_min do if min=a[i] then write(i,’, ‘); {Вивід номерів найнижчих будинків (їх може бути декілька)}

Writeln; {перехід на новий рядок}

End;

Readkey; {Затримка зображення на екрані}

End.

Реалізовуємо дану задачу на комп'ютері.


Підсумок уроку

На уроці ми розглянули ще один базовий алгоритм опрацювання табличних величин; розглянули його практичне застосування при розв'язуванні задач. На наступному уроці ми використаємо цей алгоритм при вивченні ще одного базового алгоритму - впорядкування масиву по зростанню та спаданню.


Домашнє завдання

1) Вивчити алгоритм пошуку максимального елемента та його номера.

2) Початковий рівень

Скласти програму знаходження мінімального елемента та його номера в масиві А[1..N].

Середній рівень

Скласти програму визначення найвищого учня свого класу.

Достатній рівень

Дано натуральне число n та послідовність дійсних чисел a1, a2, … an. Визначити в цій послідовності кількість сусідств двох чисел різного знаку.

Високий рівень

У даній дійсній матриці розмірністю 6x9 знайти суму елементів рядка, що містить найбільший елемент. Вважається, що такий елемент в матриці єдиний.


Завдання до даної теми

1. Дано одновимірний масив цілих чисел A[і], де і =1,2,…,n. Визначити, скільки разів максимальний елемент зустрічається у даному масиві та порядковий номер першого найбільшого елементу.

2. Дано натуральне число n. Визначити кількість додатних та від'ємних елементів таблиці Аij, де i,j = 1,2,…,n, якщо: Aij = sin(i+j) 3. Дано квадратну дійсну матрицю порядку n. Усі максимальні елементи матриці замінити нулями.

4. Дано квадратну дійсну таблицю розмірності n. Обчислити кількість входжень даного елемента.

5. Дано цілочислову прямокутну таблицю порядку N M. Усі елементи таблиці, менші за середнє арифметичне її значень, замінити на "-1", а більші - на "1".

6. У даній дійсній матриці розмірністю N M знайти добуток не нульових елементів рядка, що містить найменший елемент. Вважається, що такий елемент в матриці єдиний.