Тема: cкладання і виконання алгоритмів упорядкування табличної величини й пошуку її елементів у навчальному середовищі програмування.

Мета: навчити складати і виконувати алгоритми впорядкування табличних величин, пошуку елементів табличних величин у середовищі програмування Free Pascal.

Після вивчення матеріалу учень

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

Обладнання: комп'ютери зі встановленими ОС і середовищем програмування FreePascal.

Структура уроку

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

Хід уроку

1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку. Перевірка виконання домашнього завдання.

2. Актуалізація опорних знань
Дайте відповіді на питання і порівняйте з поданими зразками відповіді.

1. Що таке масив?
   Впорядкований скінченний набір елеменлів одного типу.

2. До якого типу даних відносяться масиви?
   Масив є прикладом структурованого типу: він складається з елементів іншого типу.

3. Які властивості мають масиви?
   Тип елементів, назва, розмірність, діапазон зміни індексів.

4. Як описують масив в навчальому середовищі програмування Free Pascal?
   var назва масиву: array[розмірність] of тип елементів

5. У чому суть впорядкування елементів масиву вибором найменшого елемента?
   Для лінійного масиву з діапазоном індексу 1..n, змінюючи j від 1 — найменшого значення індексу — до (n – 1) — найбільшого значення індексу, зменшеного на 1, — робимо таке:

   • визначаємо номер l найменшого елемента для індексів у межах від j до n включно;
   • міняємо місцями значення елементів з індексами j та l. У результаті такої заміни на місце з номером (індексом) j стане те значення, що потрібно.

6. У чому суть методу швидкого сортування?
   Для впорядкування за неспаданням масиву зі значеннями індексів від l до r включно потрібно зробити таке.

   1. Вибирати (бажано випадковим чином) значення елемента масиву.
   2. Значення елементів масиву, що не менші за вибране, розташувати на місцях з номерами (індексами) більшими від індексу обраного значення, а ті, що не перевищують — на місцях з номерами меншими від індексу обраного значення. У результаті вибране значення матиме той номер j у масиві, що потрібно. Тому надалі відповідний елемент масиву буде незмінним.
   3. Якщо l < (j – 1), виконати алгоритм для індексів від l до (j – 1) включно.
   4. Якщо (j + 1) < r, виконати алгоритм для індексів від (j + 1) до r включно.

7. У чому суть методу обліку?
   Метод обліку передбачає використання окремого масиву з нульовими початковими значеннями, який після проглядання масиву, що підлягає впорядкуванню, містить інформацію про те, скільки разів те чи інше значення зустрілося серед значень елементів масиву.

8. Якою вказівкою мови Pascal можна зв'язати файлову змінну f з файлом input.txt з поточної теки?
   assign(f,'input.txt');

9. Якою вказівкою мови Pascal можна відкрити файл f на:

   • зчитування (з першої позиції);
   • запис (з першої позиції);
   • дописування (після останньої позиції)?
   
   
   • reset(f);
   • rewrite(f);
   • append(f).

10. Якою вказівкою мови Pascal завершують роботу з файлом f?
    close(f);

11. Якою вказівкою мови Pascal зчитують чи записують число x у файл f?
    read (f,x);
    write(f,x);

3. Інструктаж з ТБ
4. Вироблення практичних навичок

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

Задача 1. Дано (записано у файлі task1.in) натуральне число n та послідовність цілих a₁, a₂, ..., a_n. Після впорядкування цієї послідовності за спаданням визначити, скільки членів послідовності залишилось стояти на своїх місцях.

Вхідні дані
Перший рядок містить натуральне число n — кількість членів послідов­ності, 2 ≤ n ≤ 100 000.
Другий рядок містить n дійсних чисел а₁, а₂, … , а_N.

Вихідні дані
Вихідний файл має містити одне число — шукану кількість нерухомих членів послідовності.

Протестувати розв'язання на таких прикладах.

Записати програму з назвою task1.* у теку, вказану вчителем.

Вказівка до розв'язання: зберігати у масивах і початкову послідовність, і впорядковану.

Задача 2. Дано (записано у файлі task2.in) натуральні числа n і x, послідовність цілих чисел a₁, a₂, …, a_n, що зростає (a₁ < a₂ < … < a_n, a₁ < x < a_n). Визначити індекси членів послідовності, між якими треба розташувати число x таким чином, щоб не порушити її неспадання.

Вхідні дані
Єдиний рядок містить у вказаному порядку натуральні числа n, x, a₁, a₂, …, a_n, які менші ніж 10⁴.

Вихідні дані
Вихідний файл має містити два цілих числа — шукані індекси двох сусідніх членів послідовності, між якими треба поставити число x.

Протестувати розв'язання на такому прикладі.

Записати програму з назвою task2.* у теку, вказану вчителем.

Задача 3 («Кур’єри», автор Андрій Гриненко, ІІІ етап Всеукраїнської учнівської олімпіади з інформатики, місто Київ, 2006 рік).

Вхідний файл: courier.in
Вихідний файл: courier.out

У місті Х є пряма вулиця Товстунів. Всі її мешканці, за дивним збігом обставин, дуже люблять добряче попоїсти. Компанія «Нагодуємо навіть слона» вирішила заробити на цьому гроші. Вона розгорнула широку мережу доставки їжі замовникам. На вулиці одночасно й постійно перебувають N кур'єрів. Після отримання замовлення компанією продукти доставляє кур’єр, що перебував у момент отримання замовлення найближче до будинку замовника. Вважати, що такий кур'єр завжди єдиний і доставка ним замовлення відбувається миттєво. Надалі кур'єр залишається чекати наступного замовлення вже на цьому новому місці.

Завдання
Визначити сумарну відстань, яку пройдуть усі кур'єри при виконанні всіх замовлень.

Вхідні дані
Перший рядок містить два цілих числа:
N (2 ≤ N ≤ 100 000) — кількість кур'єрів;
M (0 ≤ M ≤ 100 000) — кількість замовлень.

Другий рядок містить N натуральних чисел X₁, X₂, … , X_N. Тут X_i — координата почат­кового положення i-го кур'єра на вулиці Товстунів, 1 ≤ X_i ≤ 1 000 000 000.

Третій рядок містить M натуральних чисел Y₁, Y₂, … , Y_M. Тут Y_j — координата будинку j-го замовника з вулиці Товстунів, 1 ≤ Y_j ≤ 1 000 000 000.

Вихідні дані
Вихідний файл має містити лише одне ціле число — шукану сумарну відстань, яку подолають кур'єри.

Приклади

Вказівка. Порядок розташування кур'єрів незмінний.

Записати програму з назвою courier.* у теку, вказану вчителем.

5. Підбиття підсумків уроку
Перевірка виконання поставленого завдання. Виставлення оцінок.

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

Задача 4. Дано (записано у файлі task4.in) натуральні числа k й n та послідовність цілих чисел a₁, a₂, … , a_n, k ≤ n. Після впорядкуватиння послідовності знайти номер елемента, який дорівнює k.

Вхідні дані
Єдиний рядок містить у вказаному порядку k, n, a₁, a₂, …, a_n, кожне з яких менше ніж 10⁴.

Вихідні дані
Вихідний файл має містити шуканий номер елемента. Якщо такого немає, то має містити нуль.

Задача 5. Дано (записано у файлі task5.in у вказаному порядку) натуральні числа n, k та дві невпорядковані послідовності цілих чисел a₁, a₂, …, a_n, b₁, b₂, …, b_n, які менші ніж 10⁴. Знайти номери елементів, що дорівнюють k у впорядкованих послідовностях та вивести більший з цих номерів у файл task5.out.

Текст упорядкувала Катерина Григорівна Василенко, вчитель cпеціалізованої школи № 76 імені Олеся Гончара Святошинського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 6 жовтня по 24 жовтня 2014 року.