Розробка уроку

Тема: табличні величини.

Мета:

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

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

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

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

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

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

Алгоритмце запис скінченої послідовності вказівок, виконання яких призводить до розв'язання певної задачі.

Вказівка (алгоритму) — це спонукальне речення, що вказує, яку дію має виконати виконавець алгоритму.

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

Система вказівок виконавцяце множина (сукупність) всіх вказівок, які може виконувати даний виконавець.

Середовище виконання алгоритму — об'єкти, з якими працює виконавець у процесі виконання алгоритму.

Властивості алгоритму: дискретність, визначеність, виконуваність, скінченність, результативність, масовість, ефективність.

Дискретність (латинською discretus — розділений, розривний) алгоритму означає, що виконання алгоритму зводиться до виконання окремих дій (кроків) у певній послідовності. Причому, кожну вказівку алгоритму виконують за скінченний проміжок часу.

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

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

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

Результативність алгоритму означає, що після закінчення виконання алгоритму обов’язково:

  • або одержують розв'язок-результат відповідно до поставленої мети;
  • або встановлюють відсутність таких розв'язків (множина розв'язків порожня);
  • або встановлюють неможливість розв'язання задачі.

Масовість алгоритму означає, що алгоритм можна застосувати до цілого класу однотипних задач, для яких спільними є умова та хід розв’язування та які відрізняються лише початковими (вхідними) даними. Наприклад, алгоритмом дій, складеним для одного касира, можуть успішно скористатися всі касири супермаркету. А програмою пошуку коду і підрахунку суми вартостей товарів, придбаних покупцем, — усі комп'ютери супермаркету

Ефективність алгоритму описує час виконання і об'єм ресурсів, необхідних для виконання алгоритму: чим менше часу (часова ефективність) і ресурсів (просторова ефективність), тим ефективність вища.


Дати відповіді на запитання:

  1. Яким словом починають оголошення:
    • використаних модулів;
    • типів;
    • сталих;
    • змінних;
    • міток?
  2. Яким символом розмежовують вказівки у коді програми?
  3. Які типи простих даних ви знаєте?

3. Інструктаж з ТБ
4. Вивчення нового матеріалу


Потреба запровадження табличних величин випливає з необхідності запам'ятовувати й опрацьовувати великий набір однотипних даних. Наприклад, при знаходженні середнього балу кожного учня класу з інформатики за чверть потрібно знаходити суму великої кількості оцінок. Як зберігати всі ці оцінки? Зарезервувати для цього 40 чи більше змінних? Це дуже незручно. Ось тут і приходить на допомогу такий структурований тип даних, як таблиця або масив (дві назви одного й того самого об'єкта).

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

Елемент масивуодна з величин, що утворюють масив. Це поняття програмування відповідає математичному поняттю елемента послідовності чи матриці.

Індекс масивувеличина перелічуваного (зазвичай цілого) типу, яка (сукупність яких) вказує на конкретний елемент масиву. Це поняття програмування відповідає математичному поняттю номера елемента послідовності чи номеру рядка/стовпчика таблиці (матриці).

Масив має такі властивості:

Cукупність розмірності й діапазонів називають формою масиву.

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

Наприклад, а[3] — 3-тій елемент масиву а, с[j]j-ий елемент масиву с.

Елемент масиву може мати і тип простої (неструктурованої) величини і складений тип (масиву, рядка тощо), тобто може існувати масив масивів, масив рядків тощо. Глибину вкладеності (а значить, і кількість індексів) необмежено, але загальну довжину структури обмежено. У пам'яті ПК всі елементи масиву зберігають послідовно: при переході від молодших до старших адрес першим змінюється індекс, записаний останнім (праворуч).

Порядок роботи з масивом

  1. У розділі описів вказати назву, розмір і тип елементів масиву. Це забезпечить (на етапі завантаження програми) виділення потрібного об'єму оперативної пам'яті для зберігання значень елементів .
  2. Заповнити комірки пам'яті, виділені для елементів масиву, потрібними значеннями.
  3. При потребі вивести масив (на екран, у файл) для наочної перевірки роботи коректності заповнення.
  4. Опрацювати масив.
  5. Вивести отримані результати.

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

Одновимірний масив інакше ще називають лінійним масивом або вектором. Кожному його елементу ставлять у відповідність один індекс. У математиці лінійному масиву відповідає поняття послідовності, а номеру члена послідовності — індекс масиву.

Примітка. Використання масивів розмірності 2 і більше зумовлено лише міркуваннями зручності для програмістів. Наприклад, існує взаємно однозначна відповідність j = kn + l між індексом j — у межах від 0 до (mn – 1) і парою індексів (k, l) при k — у межах від 0 до (m – 1), l — у межах від 0 до (n – 1). А саме: при діленні j на n маємо: k — частка, l — лишок. Аналогічні формули можна вивести і для «зсунутої» (не з нуля) нумерації, і для більших розмірностей.

Форма опису масиву
Var назва масиву : array [розмірність] of тип елементів;

Тут розмірність — перелік діапазонів зміни індексів, розділених комами. Кожен діапазон вказують таким чином:
найменше значення..найбільше значення

Граничні значення індексів вказують явно або як вирази з попередньо визначених сталих.

Опис властивостей масиву (частину коду між сусідніми : і ;) можна використати для опису типу. Наприклад, у такому коді:

const n=3;
type ac=array[1..9] of string;
var  a: array[0..4] of integer;
     b: array[-9..9, 0..(n div 2)] of real;
     c: ac;

у другому рядку описано тип ac, який використано в описі лінійного масиву с.

Мова Pascal не передбачає стандартних засобів введення-виведення усіх елементів масиву однією вказівкою. Тому введення і виведення значень роблять послідовно, окремо для кожного елемента в циклі (див. далі).

Способи заповнення масиву (подано на прикладі одновимірного масиву a):

Виведення на екран аналогічне введенню з клавіатури з урахованням заміни операторів read i readln відповідно на write i writeln. Таку саму заміну потрібно здійснити і при виведенні у файл. Але відкривати файл потрібно на запис з першої позиції оператором rewrite(...) або на дописування оператором append(...).

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

Обчислення суми елементів масиву
(приклад подано для лінійного масиву a, заповненого випадковими числами).

const n=9;  amax=99;
var a: array [0..n] of integer;
                  s,j: integer;
BEGIN
               {Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)      end;
writeln;
write('Сума цих чисел дорівнює ');

{Обчислення суми елементів масиву}  
s:=0;
for j:=1 to n do s:=s+a[j];
writeln(s)
END.
Тут змінній s надано початкового нульового значення, яке змінюють послідовним додаванням всіх елементів масиву.

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

const n=9;  amax=99;
var a: array [0..n] of integer;
                  s,j: integer;
BEGIN
               {Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)      end;
writeln;
write('Сума парних чисел з поданих дорівнює ');

{Обчислення суми елементів масиву}  
s:=0;
for j:=1 to n do if (a[j] mod 2) = 0 then s:=s+a[j];
writeln(s)
END.

Визначення найменшого елемента масиву
Ідея пошуку така: змінній min — найменшому значенню з проглянутих — спочатку надають значення елемента масиву з найменшим номером. Послідовно переглядаючи значення наступних елементів масиву при виявленні значення, меншого від min, надаємо змінній min цього значення.

const n=9;  amax=99;
var a: array [0..n] of integer;
                min,j: integer;
BEGIN
                      {Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)      end;
writeln;
write('Найменше з поданих чисел дорівнює ');

     {Визначення найменшого елемента масиву}  
min:=a[1];
for j:=2 to n do if a[j]<min then min:=a[j];
writeln(min)
END.

Впорядкування елементів масиву вибором найменшого елемента
(опис подано для лінійного масиву з діапазоном індексу 1..n)

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

Подамо для наочності ілюстрацію такого впорядкування 10-елементного масиву, запози­чену зі сторінки Вікіпедії.

Тут червоним тлом виділено те значення, яке серед елементів з номером від j до n вважають найменшим у поточний момент виконання алгоритму, блакитним — значення поточного елемента масиву, яке порівнюють з тим, що наразі вважають найменшим, жовтим — ті значення, які вже стоять на потрібному місці.

Код програми мовою Pascal має такий вигляд.

const n=9;  amax=99;
var a: array [1..n] of integer;
            min,j,k,l: integer;
BEGIN
                      {Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)   end;
writeln;
writeln('Результат впорядкування цього масиву такий');

                      {Впорядкування масиву}  
for j:=1 to n-1 do
begin
  l:=j;
  for k:=j+1 to n do if a[l]>a[k] then l:=k;
  min:=a[l];
       a[l]:=a[j];
             a[j]:=min
end;
for j:=1 to n do begin
  write(a[j]:4)   end;
writeln;
END.

Метод швидкого сортування
Основу цього алгоритму розробив у 1962 році британський учений Чарлз Ентоні Річард Гоар (Charles Antony Richard Hoare).

Рекурсивний алгоритм для впоряд­кування за неспаданням масиву зі значеннями індексів від l до r включно має такий вигляд:

  1. Вибирати значення елемента масиву.

  2. Значення елементів масиву, що не менші за вибране, розташувати на місцях з номерами (індексами) більшими від індексу обраного значення, а ті, що не перевищують — на місцях з номерами меншими від індексу обраного значення. У результаті вибране значення матиме той номер j у масиві, що потрібно. Тому надалі відповідний елемент масиву буде незмінним.

  3. Якщо l < (j – 1), виконати алгоритм для індексів від l до (j – 1) включно.

  4. Якщо (j + 1) < r, виконати алгоритм для індексів від (j + 1) до r включно.

Пункт 2 цього алгоритму можна деталізувати:

Рекурсивність алгоритму означає виклик цього алгоритму в ньому самому — див. кроки 3–4. На малюнку нижче подано частину схеми впорядкування.

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

Примітка. Поданий вище запис стане алгоритмом лише після того, як буде деталізовано вибір значення. У багатьох описах алгоритму можна зустріти вибір елемента з найменшим чи з найбільшим номером. Розглянемо спробу впорядкувати вже впорядкований масив при такому виборі. Глибина занурення — кількість послідовних викликів рекурсивного алгоритму без виходу з нього — буде майже збігатися з довжиною масиву. Останнє може призвести до переповнення стеку частини оперативної пам'яті, куди програма заносить дані про виклик програмі та функцій, їхні аргументи, точку повернення тощо. А переповнення стеку означає аварійне завершення роботи. Який би не був детерміністичний (без випадковостей) вибір значення (наприклад, із середини масиву), завжди можна вказати вхідні дані, для яких глибина занурення для цих вхідних даних лише на 1 відрізнятиметься від довжини масиву. Тому вибір потрібно робити з використанням генератора випадкових чисел. І в цьому випадку можливе переповнення стеку, але ймовірність цієї події настільки мала, що аварійне припинення роботи зазвичай не відбувається.

Проаналізуйте на відповідність опису ілюстрацію для вибору правого краю (елемента з найбільшим номером), запозичену із сайту http://uk.wikipedia.org/wiki

і код програми.

const n=9;  amax=99;
var a: array [1..n] of integer;
    j: integer;
procedure QSort(l,r: integer); 
        var x,y,i,j: integer; 
BEGIN 
x:=a[l+random(r-l+1)]; {Випадковий вибір значення}
i:=l; j:=r; 
while i<=j do   begin{1} 
  while a[i]<x do i:=i+1; 
  while a[j]>x do j:=j-1; 
  if i<=j then  begin{2} 
    y:=a[i];  {Заміна значень елементів}
       a[i]:=a[j];     {з номерами i, j}
             a[j]:=y;
    i:=i+1;
    j:=j-1        end{2}
                  end{1};
if l<j then qsort(l,j); 
if i<r then qsort(i,r); 
END; 
BEGIN 
{Заповнення масиву}
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)   end;
writeln;
writeln('Результат впорядкування цього масиву такий');
qsort(1,n);
for j:=1 to n do begin {Виведення результату}
  write(a[j]:4)   end;
writeln;
END.

При прямуванні n — довжини лінійного масиву — до нескінченності кількість виконуваних операцій при впорядкуванні (майже) пропорційна:

Іншими словами про це кажуть так: часові складності алгоритмів дорівнюють відповідно O(n2), O(n log2n) і O(n + m). У більшості випадків доречно використати саме швидкий метод Хоара, хоча бувають випадки, коли для розв'язування поставленої задачі (не лише впорядкування) потрібно використати, наприклад, метод злиття, або використати метод обліку, щоб задовольнити обмеження на час виконання програми. Обидва випадки зустрічалися на ІІІ (міському) етапі Всеукраїнської учнівської олімпіади з інформатики у місті Києві.

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

const n=9;  amax=99;
var a: array [1..n] of integer;
    b: array [1..amax] of integer;
                   j,k,l: integer;
BEGIN
randomize;
for j:=1 to n do begin
  a[j]:=random(amax);
  write(a[j]:4)   end;
writeln;
writeln('Результат впорядкування цього масиву такий');

for j:=0 to amax do b[j]:=0;
for j:=1 to n do inc(b[a[j]]);
l:=0;
for j:=0 to amax do 
for k:=1 to b[j] do begin
      inc(l); a[l]:=j end;

for j:=1 to n do begin
  write(a[j]:4)   end;
writeln;
END.

Щодо інших методів упорядкування та унаочннення упорядкування масиву див. презентацію, люб'язно надану Іриною Скляр на курсах підвищення кваліфікації 5-7 червня 2024 року.

Бінарний (двійковий) пошук
Розглянемо задачу пошуку номера елемента упорядкованої за зростанням послідовності {an}, який (елемент) має значення b. Зазвичай для цього викорис­товують двійковий (бінарний) пошук. Він полягає у послідовному поділі (приблизно) навпіл діапазону номерів, у якому проводять пошук. На початку виконання цього алгоритму:

j — менша межа діапазону номерів, на якому шукають потрібний номер, дорівнює меншій межі діапазону номерів масиву;

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

Алгоритм бінарного пошуку має такий вигляд:

  1. Поки справджується нерівність jk, робити таке:

    • надати значення змінній l = [(j + k)/2] — знайти індекс l, що поділяє досліджуваний діапазон навпіл;

    • якщо al = b, завершити пошук зі знайденим номером l;

    • якщо al < b, надати значення змінній j = (l + 1), тобто вибрати для подальшого пошуку діапазон, розташований правіше від l;

    • якщо al > b, надати значення змінній k = (l – 1), тобто вибрати для подальшого пошуку діапазон, розташований лівіше від l.

  2. Завершити пошук, вважаючи його неуспішним.

Тут квадратні дужки (у першій дії всередині циклу) позначають операцію визначення цілої частини.

У поданій далі програмі крім описаних вже змінних використано булеву змінну s (англійською search — шукати): s справджується, якщо шуканого номеру немає або пошук ще не завершено.

const n=9;  amax=3;
var       b,j,k,l: integer;  s: boolean;
a: array [0..n] of integer;

BEGIN              {Заповнення масиву}
randomize;
a[0]:=0;
for j:=1 to n do begin
  a[j]:=a[j-1]+1+random(amax);
  write(a[j]:4)   end;
writeln;
b:=1+random(a[n]);

write('Серед елементів цього масиву значення ',b);
s:=true;
j:=1;                {Бінарний пошук}
k:=n;
while (j<=k) and s do    begin
  l:=(j+k) div 2;
  if a[l]=b then s:=false else
  if a[l]<b then j:=l+1   else
  if a[l]>b then k:=l-1    end;
if not s then writeln (' має елемент з номером ',l)
         else writeln (' не має жоден елемент');
END.

5. Закріплення вивченого матеріалу

  1. Що таке масив?
  2. Які властивості має масив?
  3. Що таке форма масиву?
  4. Як описують масив?
  5. Які методи впорядкування лінійних масивів Ви знаєте?
  6. У чому полягає впорядкування масиву швидким методом Хоара?
  7. У чому полягає бінарний пошук?

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

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

  1. Вивчити матеріал уроку.
  2. Написати програму розв'язання такої задачі: заповнити лінійний масив випадковим чином і визначити, скільки разів досягається найбільше значення у даному масиві та найменший порядковий номер (індекс) для такого найбільшого значення.

Текст упорядкував Вовк Олександр Валерійович, вчитель ліцею «Наукова зміна» Дарницького району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 15.09.2014 по 03.10.2014.