Як описати програму пошуку заданого елемента?
При опрацюванні табличних величин часто розв’язують завдання пошуку елемента, який відповідає деякій умові. Для розв’язування цього завдання можна, як у прикладах, розглянутих на попередніх уроках, пе-реглядати кожний елемент масиву та підраховувати кількість входжень. Якщо така кількість дорівнює 0, то зазначеного елемента таблична величина не містить, якщо більше 0, то містить. Але такий підхід є нераціональним, особливо якщо кількість елементів дуже велика, наприклад, понад 1000, а збіг є вже серед перших елементів. У цьому разі використовують цикл while та виконують такі дії:
1. Уводять спеціальну логічну величину — прапорець, призначення якої полягатиме в тому, що її значення зберігатиме результат наявності чи відсутності такої величини в таблиці. Початкове значення цієї величини — false, яке означає, що шукане значення поки що не траплялось у масиві.
2. Переглядають усі елементи табличної величини, починаючи з першого, доти, доки не буде переглянуто всі елементи або знайдено елемент із потрібним значенням.
3. Якщо елемент знайдено, то змінюють значення прапорця на true та переривають виконання циклу. Нагадаємо, що для переривання виконання циклу використовують команду break.
4. Здійснюють виведення результату залежно від значення прапорця.
Якщо потрібно не просто визначити наявність елемента, а його номер у масиві чи списку даних, то вводять змінну, наприклад flag, для фіксування такого номера. Початкове значення змінній flag можна присвоїти 0 (у Free Pascal передбачено нумерацію елементів масиву з 1) або –1 (у Python передбачено нумерацію елементів масиву з 0). Якщо елемент буде знайдено, тоді змінній flag присвоюють його номер. Тоді ця змінна може слугувати прапорцем завершення перегляду елементів: якщо flag>0 (Free Pascal) flag>–1 (Python), тоді виконання циклу зупиняють.
Як описати програму пошуку елемента з найбільшим або найменшим значенням?
Для того щоб зрозуміти, як відбувається пошук найбільшого елемента деякої табличної величини, уявімо себе на місці виконавця алгоритму. Елементи табличної величини записані в пам’яті, доступ до комірок якої здійснюється за номерами елементів. Виконавець може одночасно відкривати доступ до однієї комірки. Нехай задано лінійну таблицю з n цілих чисел.
Виконаємо такий алгоритм:
1) прочитаємо з пам’яті перший елемент таблиці. Його значення дорівнює 5. Запам’ятаємо його як максимальне — надамо його значення величині max;
2) прочитаємо другий елемент таблиці. Його значення більше за max, тому «забудемо» про попереднє значення й запам’ятаємо значення max=6;
3) прочитаємо третій елемент таблиці. Його значення менше за max, тому можна приступати до наступного кроку без зміни значення max.
Продовжимо таким чином кроки алгоритму, поки не будуть переглянуті всі елементи лінійної таблиці до n включно. На кожній ітерації циклу в змінній max міститиметься найбільше значення з пройденої частини лінійної таблиці, а по завершенні циклу змінна max зберігатиме максимальне значення в усьому масиві.
Пошук найменшого елемента масиву здійснюють за аналогічним алгоритмом, знаходячи відповідно елемент (min), який є меншим від усіх переглянутих елементів.
Вправа 1. Різниця між найбільшим і найменшим.
Завдання. Створіть проект Випробування, у якому знаходять різницю між найбільшим і найменшим елементом лінійної таблиці з 10 дійсних чисел, які набувають значень від 5 до 10 випадково.
Розробка проекту в середовищі програмування Lazarus
1. У папці Навчальні проекти своєї структури папок створіть папку Випробування.
2. Відкрийте середовище Lazarus і створіть новий проект. Розмістіть на екранній формі об’єкти, самостійно надайте значення їхнім властивостям.
3. Створіть процедуру опрацювання події натиснення кнопки Знайти. У вікні редактора коду опишіть змінні, які будуть використовуватись у проекті: а — масив дійсних чисел; i — номер (індекс) елемента масиву; max — найбільше значення серед елементів; min — найменше значення серед елементів.
var i : integer;
max, min : real;
а : array [1..10] of real;
4. У вікні редактора коду запишіть команди випадкового генерування елементів масиву та виведення їх у таблицю, пошуку найбільшого й найменшого елементів масиву, виведення різниці значень max і min. Зауважте, для того щоб отримати випадкове дійсне число, яке відповідає умові 5<x<10, використано вираз: 10.0 – random*5.0.
5. Запустіть проект на виконання. Перевірте, чи відповідають умові завдання дії, пов’язані з об’єктами управління екранної форми. Якщо є помилки — виправте їх.
6. Знайдіть на екранній формі найбільше та найменше значення елементів згенерованої таблиці. Обчисліть їхню різницю. Перевірте програму на наявність логічних помилок. Завершіть роботу з проектом і середовищем програмування, зберігши всі зміни.
Комментариев нет:
Отправить комментарий