Урок 22. Пошук у масиві (списку) за певними критеріями

Шановні учні 9-го класу, сьогодні наш урок буде присвячений захоплюючій і важливій темі в інформатиці - "Пошук у масиві (списку) за певними критеріями". Пошук є однією з ключових операцій при роботі з даними, і ця тема дозволить вам вдосконалити свої навички та зрозуміти, як важливо ефективно знаходити і обробляти інформацію.

Основні теоретичні відомості.

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

Масив (список) - структура даних, яка зберігає елементи одного типу у впорядкованому порядку. Кожен елемент можна ідентифікувати за допомогою індексу чи ключа. Пошук у масиві дозволяє знаходити елементи за їхніми значеннями, використовуючи різноманітні критерії.

Основні алгоритми пошуку:

• Лінійний пошук:

  • Простий метод, при якому кожен елемент послідовно порівнюється з шуканим значенням.

  • Використовується, коли дані не впорядковані.

• Бінарний пошук:

  • Ефективний алгоритм для впорядкованих масивів.

  • Розділяє масив пополам і порівнює середній елемент з шуканим, далі обирає половину для пошуку.

• Пошук за допомогою хеш-функцій:

  • Використовується в хеш-таблицях для швидкого доступу до даних.

  • Перетворює ключ у хеш-код та використовує його для швидкого визначення місцезнаходження даних.

Приклад використання алгоритму:

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

for i := 1 to n do

  if students[i].averageGrade > 90 then

    ShowMessage('Студент ' + students[i].name + ' має високий середній бал: ' + students[i].averageGrade);

Цей код пройде по всьому масиву студентів і виведе інформацію про тих, чий середній бал вище 90.

Заключення:

Розуміння алгоритмів пошуку є ключовим для розвитку навичок програмування та роботи з даними. Ця тема допоможе вам виявити важливість оптимізації та вибору правильного методу пошуку в залежності від ваших потреб. Бажаю успіху на уроці та глибокого розуміння матеріалу!

python

class Student:

    def __init__(self, name, average_grade):

        self.name = name

        self.average_grade = average_grade

def linear_search(students, threshold):

    for student in students:

        if student.average_grade > threshold:

            print(f'Студент {student.name} має високий середній бал: {student.average_grade}')

# Ініціалізація масиву студентів (для прикладу)

students_list = [

    Student('Анна', 92.5),

    Student('Олексій', 88.0),

    Student('Катерина', 95.3),

    Student('Іван', 89.7),

    Student('Ольга', 91.8)

]

# Пошук студентів з високим середнім балом (більше 90) за допомогою лінійного пошуку

linear_search(students_list, 90)

• Створення форми:

  • В Lazarus обираєте File -> New Project -> Application - Form Application.

• Додавання компонентів на форму:

  • Додаємо TEdit для введення порогового балу.

  • Додаємо TMemo для виведення результатів.

• Код проекту:

unit Main;

{$mode objfpc}{$H+}

interface

uses

  Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, StdCtrls;

type

  { TForm1 }

  TForm1 = class(TForm)

    EditThreshold: TEdit;

    MemoResults: TMemo;

    ButtonSearch: TButton;

    procedure ButtonSearchClick(Sender: TObject);

  private

    { private declarations }

  public

    { public declarations }

  end;

var

  Form1: TForm1;

implementation

{$R *.lfm}

type

  Student = class

  public

    name: string;

    averageGrade: real;

    constructor Create(n: string; g: real);

  end;

constructor Student.Create(n: string; g: real);

begin

  name := n;

  averageGrade := g;

end;

var

  students: array of Student;

  i: integer;

{ TForm1 }

procedure TForm1.ButtonSearchClick(Sender: TObject);

var

  threshold: real;

begin

  MemoResults.Clear;

  // Ініціалізація масиву об'єктів студентів (для прикладу)

  SetLength(students, 5);

  students[0] := Student.Create('Анна', 92.5);

  students[1] := Student.Create('Олексій', 88.0);

  students[2] := Student.Create('Катерина', 95.3);

  students[3] := Student.Create('Іван', 89.7);

  students[4] := Student.Create('Ольга', 91.8);

  // Обробка введеного порогового балу

  if TryStrToFloat(EditThreshold.Text, threshold) then

  begin

    for i := 0 to High(students) do

      if students[i].averageGrade > threshold then

        MemoResults.Lines.Add('Студент ' + students[i].name + ' має високий середній бал: ' +

          FloatToStr(students[i].averageGrade));

  end

  else

    ShowMessage('Введіть коректний пороговий бал!');

end;

end.

• Пояснення:

  • TEdit використовується для введення порогового балу.

  • TMemo використовується для виведення результатів.

Такий код дозволяє користувачеві вводити пороговий бал у TEdit, а потім натискати ButtonSearch, щоб вивести студентів, які мають бал вище введеного порогу, у TMemo.

За підручником Інформатика 9 клас Морзе 2017  § 18.2 ст. 132-133 опрацювати усно.

Пройти тестування

https://sites.google.com/view/nam-kapec/%D1%96%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0/9-%D0%BA%D0%BB%D0%B0%D1%81/%D1%83%D1%80%D0%BE%D0%BA-53-9 

Тест на тему "Пошук у масиві (списку) за певними критеріями"

Питання 1: Що включає в себе алгоритм пошуку у масиві за певним критерієм?

a) Записи у масиві

b) Умову пошуку

c) Виведення результатів

Правильна відповідь: b) Умову пошуку

Питання 2: Які компоненти можуть бути використані для введення даних в Lazarus?

a) TMemo

b) TLabel

c) TEdit

Правильна відповідь: c) TEdit

Питання 3: Що відбувається при натисканні кнопки пошуку на формі?

a) Виводяться всі записи

b) Вводиться пороговий бал

c) Виводяться результати пошуку

Правильна відповідь: c) Виводяться результати пошуку

Питання 4: До якого типу даних можна вводити пороговий бал?

a) String

b) Integer

c) Real

Правильна відповідь: c) Real

Питання 5: Які дії виконуються в обробнику подій кнопки пошуку?

a) Записи у масиві ініціалізуються

b) Обчислюється середній бал

c) Перевіряється, чи введено коректний пороговий бал і виводяться результати пошуку

Правильна відповідь: c) Перевіряється, чи введено коректний пороговий бал і виводяться результати пошуку

Питання 6: Які класи використовуються для представлення об'єктів студентів у коді?

a) TObject

b) TStudent

c) TComponent

Правильна відповідь: b) TStudent

Питання 7: Що представляє собою масив об'єктів студентів?

a) Рядок

b) Список

c) Таблиця

Правильна відповідь: b) Список

Питання 8: Які інструменти використовуються для ініціалізації масиву студентів у коді?

a) SetLength

b) Initialize

c) Create

Правильна відповідь: c) Create

Питання 9: Що робить функція TryStrToFloat?

a) Конвертує рядок в дійсне число

b) Записує у рядок дійсне число

c) Перевіряє, чи рядок має дійсне число

Правильна відповідь: a) Конвертує рядок в дійсне число

Питання 10: Що відбувається, якщо введено некоректний пороговий бал?

a) Виводиться повідомлення про помилку

b) Виконуються всі інструкції

c) Нічого не відбувається

Правильна відповідь: a) Виводиться повідомлення про помилку

Практична робота 

Давайте розглянемо тему "Пошук у масиві (списку) за певними критеріями". Я підготую три задачі з розв'язком на Python, а також приклади реалізації в Lazarus (Pascal).

Задача 1: Пошук числа у списку

Умова: Знайти задане число в списку та повернути його індекс. Якщо число не знайдено, повернути -1.

Python

python

def find_number(arr, target):  

    for index, number in enumerate(arr):  

        if number == target:  

            return index  

    return -1  

# Приклад використання  

numbers = [1, 2, 3, 4, 5]  

result = find_number(numbers, 3)  

print("Індекс:", result)  # Виведе: Індекс: 2  

Lazarus (Pascal)

1. Створіть новий проект:

   • Виберіть "File" -> "New" -> "Application".

2. Додайте елементи на форму:

   • TEdit для введення шуканого числа.

   • TButton для запуска пошуку.

   • TLabel для відображення результату.

3. Код для обробника події:

pascal

procedure TForm1.Button1Click(Sender: TObject);  

var  

  numbers: array[0..4] of Integer = (1, 2, 3, 4, 5);  

  target, i: Integer;  

  found: Boolean;  

begin  

  target := StrToInt(Edit1.Text);  

  found := False;  

  for i := 0 to High(numbers) do  

  begin  

    if numbers[i] = target then  

    begin  

      Label1.Caption := 'Індекс: ' + IntToStr(i);  

      found := True;  

      Break;  

    end;  

  end;  

  if not found then  

    Label1.Caption := 'Не знайдено';  

end;  

Задача 2: Пошук багатократних чисел у списку

Умова: Знайти всі індекси заданого числа в списку.

Python

python

def find_all_occurrences(arr, target):  

    indices = []  

    for index, number in enumerate(arr):  

        if number == target:  

            indices.append(index)  

    return indices  

# Приклад використання  

numbers = [1, 2, 3, 2, 5]  

result = find_all_occurrences(numbers, 2)  

print("Індекси:", result)  # Виведе: Індекси: [1, 3]  

Lazarus (Pascal)

1. Елементи на формі:

   • Використайте ті ж елементи, що й у попередньому проекті.

2. Обробник події для натискання кнопки:

pascal

procedure TForm1.Button1Click(Sender: TObject);  

var  

  numbers: array[0..4] of Integer = (1, 2, 3, 2, 5);  

  target, i: Integer;  

  indices: String;  

begin  

  target := StrToInt(Edit1.Text);  

  indices := '';  

  for i := 0 to High(numbers) do  

  begin  

    if numbers[i] = target then  

    begin  

      indices := indices + IntToStr(i) + ' ';  

    end;  

  end;  

  if indices <> '' then  

    Label1.Caption := 'Індекси: ' + Trim(indices)  

  else  

    Label1.Caption := 'Не знайдено';  

end;  

Задача 3: Пошук за діапазоном значень

Умова: Знайти всі числа в масиві, що знаходяться в заданому діапазоні.

Python

python

def find_in_range(arr, low, high):  

    result = []  

    for number in arr:  

        if low <= number <= high:  

            result.append(number)  

    return result  

# Приклад використання  

numbers = [1, 2, 3, 4, 5]  

result = find_in_range(numbers, 2, 4)  

print("Числа в діапазоні:", result)  # Виведе: Числа в діапазоні: [2, 3, 4]  

Lazarus (Pascal)

1. Елементи на формі:

   • Додайте два TEdit для введення меж діапазону.

   • Той же TButton та TLabel для відображення результату.

2. Обробник події для натискання кнопки:

pascal

procedure TForm1.Button1Click(Sender: TObject);  

var  

  numbers: array[0..4] of Integer = (1, 2, 3, 4, 5);  

  low, high, i: Integer;  

  resultString: String;  

begin  

  low := StrToInt(Edit1.Text);  

  high := StrToInt(Edit2.Text);  

  resultString := '';  

  for i := 0 to High(numbers) do  

  begin  

    if (numbers[i] >= low) and (numbers[i] <= high) then  

    begin  

      resultString := resultString + IntToStr(numbers[i]) + ' ';  

    end;  

  end;  

  if resultString <> '' then  

    Label1.Caption := 'Числа в діапазоні: ' + Trim(resultString)  

  else  

    Label1.Caption := 'Не знайдено чисел у діапазоні';  

end;