Пошук в масиві елементів з деякою властивістюПлан конспект уроку з інформатики на тему УРОК 3 Тема уроку: Пошук в масиві елементів з деякою властивістю Навчальна мета: вивчити алгоритм пошуку елемента з певною властивістю на основі алгоритму пошуку максимального елемента та його номера (індекса) в одновимірному масиві та запис цього алгоритму мовою програмування Pascal. розглянути приклади застосування даного алгоритму при розв(зуванні задач Розвиваюча мета: розвивати в учнів кругозір, уважність, допитливість, зв»язне специфічне мовлення Виховна мета: виховувати в учнів допитливість, культуру мовлення Тип уроку: Лекційний з практичними прикладами Наочність: таблиці Девіз уроку: «Хто шукає, той завжди знайде!» Хід уроку Оголошую тему та мету уроку. На уроці ми розглянемо ще один базовий алгоритм (базову задачу) по опрацюванню масивів та його практичне застосування при розв(язуванні певних задач. А зараз повторимо, що ми знаємо про масиви. Актуалізацію опорних знань здійснюю фронтальним опитуванням. Запитання : Що таке масив? Що називається індексом масиву? Як ще називають елементи масиву? Які типи змінних називаються простими, а які структурованими? Чому? Які масиви ви знаєте? Що таке одновимірний та двовимірний масив? Опис цих масивів мовою Паскаль. Наведіть приклади одновимірних масивів. Наведіть приклади двовимірних масивів. Які методи заповнення одновимірного (двовимірного) масиву ви знаєте? Виведення одновимірного (двовимірного) масиву на екран. Який порядок роботи з масивом? Повідомлення нового матеріалу Сьогодні ми розглянемо алгоритм пошуку елемента з певною властивістю. За основу візьмемо алгоритм пошуку максимального елемента та його номера в одновимірному масиві 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 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] 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..N]. Середній рівень Скласти програму визначення найвищого учня свого класу. Достатній рівень Дано натуральне число n та послідовність дійсних чисел a1, a2, … an. Визначити в цій послідовності кількість сусідств двох чисел різного знаку. Високий рівень У даній дійсній матриці розмірністю 69 знайти суму елементів рядка, що містить найбільший елемент. Вважається, що такий елемент в матриці єдиний. Завдання до даної теми Дано одновимірний масив цілих чисел A[і], де і =1,2,…,n. Визначити, скільки разів максимальний елемент зустрічається у даному масиві та порядковий номер першого найбільшого елементу. Дано натуральне число n. Визначити кількість додатних та від.ємних елементів таблиці Аij, де i,j = 1,2,…,n, якщо: Aij = sin(i+j) Дано квадратну дійсну матрицю порядку n. Усі максимальні елементи матриці замінити нулями. Дано квадратну дійсну таблицю розмірності n. Обчислити кількість входжень даного елемента. Дано цілочислову прямокутну таблицю порядку NM. Усі елементи таблиці, менші за середнє арифметичне її значень, замінити на |-1|, а більші - на |1|. У даній дійсній матриці розмірністю NM знайти добуток не нульових елементів рядка, що містить найменший елемент. Вважається, що такий елемент в матриці єдиний.
