Практична робота 7 Складання і виконання алгоритму пошуку значень у таблиці в навчальному середовищі програмування

За новою програмою

Урок 32

9

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

Розділ 6 § 19

структуру папок:

E:\9-А(Б) клас\Власне прізвище\Урок 32

Під час виконання практичних завдань пам’ятай про правила безпеки життєдіяльності при роботі з комп’ютером!

Пригадайте

Створіть

Пам’ятайте

• Як вводити та виводити значення табличних величин у програмах;
• які алгоритми є базовими для опрацювання табличних величин;
• як описати алгоритми пошуку елемента табличної величини за даною властивістю мовами програмування.

9

Повторення

Розділ 6 § 18

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

дорівнює 0

більше 0

то заданого числа серед значень елементів табличної величини

то задане число серед значень елементів табличної величини

немає

є

9

Як описати програму пошуку елемента з найбільшим або найменшим значенням?

Розділ 6 § 18

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

Елементи табличної величини записані в пам'яті, доступ до комірок якої здійснюється за номерами елементів. Виконавець може одночасно відкривати доступ до однієї комірки.

9

Як описати програму пошуку елемента з найбільшим або найменшим значенням?

Розділ 6 § 18

Нехай задано лінійну таблицю з n цілих чисел.

9

Як описати програму пошуку елемента з найбільшим або найменшим значенням?

Розділ 6 § 18

Виконаємо такий алгоритм:

1. прочитаємо з пам'яті перший елемент таблиці. Його значення дорівнює 5. Запам'ятаємо його як максимальне — надамо його значення величині max;

2. прочитаємо другий елемент таблиці. Його значення більше за max, тому «забудемо» про попереднє значення й запам'ятаємо значення max=6;

3. прочитаємо третій елемент таблиці. Його значення менше за max, тому можна приступати до наступного кроку без зміни значення max...

9

Як описати програму пошуку елемента з найбільшим або найменшим значенням?

Розділ 6 § 18

Продовжимо таким чином кроки алгоритму поки не будуть переглянуті всі елементи лінійної таблиці до n включно.

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

9

Як упорядковувати�дані в лінійній таблиці?

Розділ 6 § 18

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

Зростанням

Неспаданням

Спаданням

Зростанням

якщо значення елементів не повторюються

якщо значення елементів можуть повторюватись

9

Як упорядковувати�дані в лінійній таблиці?

Розділ 6 § 18

Для прикладу таблиці з 5 елементів, яка містить значення довжини п'яти олівців, послідовно розглядають чотири різні набори олівців (чотири таблиці, що мають різну довжину):

9

Як прискорити пошук елемента�в лінійній таблиці?

Розділ 6 § 18

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

9

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

Проаналізувати

§ 19, ст. 148

Розділ 6 § 19

9

Працюємо за комп’ютером

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

Складання і виконання алгоритму пошуку значень у таблиці в навчальному середовищі програмування.

Розділ 6 § 19

9

Працюємо за комп’ютером

Розділ 6 § 19

Сторінка

148

9

Дякую за увагу!

За новою програмою

Урок 32

9