• запровадити поняття табличних величин;
• познайомити з описом їх мовою PHP;
• описати введення елементів таблиць та виведення їх;
• ознайомити з найпростішими алгоритмами опрацювання таблич­них величин.

Обладнання: комп'ютери зі встановленими ОС та стійким сполу­ченням з мережею для використання інтерпретаторів PHP online.

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

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

1. Що таке змінна в PHP?
   Змінною називають названу область пам’яті, відведену для збереження даних, які використовують при виконанні програми.

2. Як записують назву змінної?
   Запис назви змінної в PHP починається зі знаку долара $ і містить літери, цифри і знак підкреслення.

3. Назвіть типи даних.
   Дійсні числа (real), цілі числа (integer), рядки (string), логічні величини (boolean).

4. Назвіть конструкції мови програмування PHP для опису повторень.
   while, for, do … while.

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

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

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

Елемент масиву — одна з величин, що утворюють масив.

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

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

• тип елементів (масиву) для типізованих мов;
• назва (ідентифікатор) — одна й та сама для всіх елементів масиву;
• розмірність — кількість номерів (індексів), необхідних для визначення розташу­вання елемента у масиві;
• діапазони зміни номерів (індексів).

Мова PHP є динамічно типізованою. Для масивів це означає: типи елементів масиву можна змінювати протягом виконання коду і для різних елементів по різному.

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

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

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

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

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

Способи створення масивів:

• Оператор надання значення. Наприклад, код:

  <?php
  $m[0] = "значення";
  $m[1] = 1;
  echo $m[0];
  echo $m[1];
  ?>

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

  <?php
  $m[] = "значення";
  $m[] = 1;
  echo $m[0];
  echo $m[1];
  ?>

• Використання службового слова array() для створення:
  • порожнього масиву:

    <?php
    $m = array();
    ?>

  • масиву з вказаними елементами:

    <?php
    $m = array ("a", 2);
    ?>

Визначення довжини масиву здійснюють за допомогою функції count().

Асоціативні масиви передбачають використання рядків тексту довільної довжини в якості індексів. Наприклад,

<?php
// Асоціативний масив
$m["Іванчук"] = "Тарас";
$m["Сич"]     = "Микола";
$m["Петраш"]  = "Сидір";
?>

У поданому прикладі прізвища — ключі асоціативного масиву, а імена — значення елементів масиву $m. Доступ до елементів одновимірних асоціативних масивів здійснюють так само, як і до елементів звичайних масивів — доступом за ключем:

echo $m["Іванов"];

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

• зчитування значень елементів з файлу:

  <?php
  $fp = fopen('1.txt','r');
  $i = 0;
  while(!feof($fp)) {$m[$i] = fgets($fp); $i++;}
  $q = $i-1;
  fclose($fp);
  for ($i = 0; $i<$q; $i++) echo $m[$i].' ';
  ?>

• використання генератора випадкових чисел:

  <?php
  for ($i = 0; $i < 9; $i++) {$m[] = rand(0, 99);}
  for ($i = 0; $i < 9; $i++) {echo $m[$i].' ';}
  ?>

• згідно з формулою:

  <?php
  for ($i = 0; $i < 9; $i++) {$m[] = $i*($i+1)/2;}
  for ($i = 0; $i < 9; $i++) {echo $m[$i].' ';}
  ?>

Виведення масиву можна здійснювати на екран:

• на екран — за допомогою оператора echo (див. приклади вище);
• у файл — див. приклад нижче;

  <?php
  for ($i = 0; $i < 9; $i++) {$m[] = $i*($i+1)/2;}
  $f = fopen("new.txt","w+");
  for ($i = 0; $i < count($m); $i++)
    {$record = fwrite($f,$m[$i],' ');}
  fclose($f);
  ?>

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

<?php
define("n",5);
define("k",9);
for ($i = 0; $i < n; $i++) {$m[$i] = rand(1, k);};
$s = 0;
for ($i = 0; $i < n; $i++) {$s=$s+$m[$i];};
for ($i = 0; $i < n; $i++) {echo $m[$i]." ";};
echo 's = '.$s
?>

Тут змінній $s надано початкового нульового значення, яке змінюють послідовним додаванням всіх елементів масиву.

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

<?php
define("n",10);
define("k",25);
for ($i = 0; $i < n; $i++) {$m[$i]= rand(5,k);};
$s = 0;
for ($i = 0; $i < n; $i++) {if ($m[$i]%2==0) $s=$s+$m[$i];};
for ($i = 0; $i < n; $i++) {echo $m[$i].' ';};
echo 's = '.$s
?>

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

<?php
define("n",10);
define("k",25);
for ($i = 0; $i < n; $i++) {$m[$i] = rand(1, k);};
for ($i = 0; $i < n; $i++) {echo $m[$i].' ';};
$min=$m[0];
for ($i = 1; $i < n; $i++) {if ($m[$i]<$min) $min=$m[$i];}
echo 'Найменший елемент = '.$min
?>

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

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

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

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

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

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

<?php
define("n",10);
for ($i = 0; $i <? n; $i++) {$m[] = rand(10, 20);}
echo 'Початковий масив: ';
for ($i = 0; $i <? n; $i++) {echo $m[$i].' ';}
for ($j = 0; $j <? n-1; $j++)
{ $l = $j;
  for($k = $j+1; $k <? n; $k++) {if($m[$k] <? $m[$l]) $l = $k;}
  $min = $m[$l];
         $m[$l] = $m[$j];
                  $m[$j] = $min;
}
echo '<br> Упорядкований масив: ';
for ($i = 0; $i <? n; $i++) {echo $m[$i].' ';}
?>

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

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

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

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

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

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

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

Код:

<?php 
$a = array(1,14,3,12,5,10,7,8,9,6,11,4,13,2,15);
function f($x,$y) {return $x - $y;}
function qsort(&$a,$l,$r)
{ $i = $l;
  $j = $r;
  $x = $a[rand($l,$r)];
  do { while(f($a[$i], $x)>0) ++$i;
       while(f($a[$j], $x)<0) --$j;
       if($i<=$j){$y = $a[$i];
                       $a[$i] = $a[$j];
                                $a[$j] = $y; 
                   $i++;
                   $j--;
                 }
     }
  while($i<=$j);
  if($l<$j) qsort($a, $l, $j);
  if($i<$r) qsort($a, $i, $r);
}
qsort($a, 0, count($a)-1);
foreach($a as $rez)
echo $rez.' ';
?>

дає такий результат:

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

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

<?php
define("n",9);
define("amax",5);
echo 'До упорядкування: ';
for ($j = 1; $j <= n; $j++)
{$a[$j] = rand(0,amax);
 echo $a[$j].' ';}; 
echo '    Після упорядкування: ';
for ($j = 0; $j <= amax; $j++){$b[$j]=0;};
for ($j = 1; $j <= n;    $j++){$b[$a[$j]]++;};
$l=0;
for   ($j = 0; $j <= amax;   $j++)
{ for ($k = 0; $k <  $b[$j]; $k++)
  {$l++;$a[$l]=$j;
  };
};
for ($j = 1; $j <= n; $j++) {echo $a[$j].' ';}
?>

Як правило фахівці програмування не кодує алгоритми упорядкування, а використовує вбудовані функції: array_multisort, asort, arsort, krsort, ksort, natcasesort, natsort, rsort, shuffle, sort, uasort, uksort, usort. Деякі з них упорядковують за ключами елементів, інші за значеннями. Нагадаємо:

$a['ключ'] = 'значення';).

У деяких функціях зв'язок між ключами та значеннями після упорядкування буде збережено, в інших — ні. Можливі критерії упорядкування такі: за алфавітом, за зростанням, за спаданням, числовий, натуральний, випадковий або визначений користувачем. Усі функції упорядкування модифікують передані масиви, а не повертають відсортовану копію. Якщо функції визначають два елементи як рівні, eупорядкування у цьому випадку не визначено (нестабільне).

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

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

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

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

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

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

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

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

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

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

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

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

Код програми:

<?php 
define("n",7);
define("amax",2);
$a[0]=0;
for ($j = 1; $j < n+1; $j++)
{ $a[$j] = $a[$j-1] + 1 + rand(0,amax);
  echo $a[$j].' ';
};
$b = 1 + rand(0,$a[n]);
echo '  Серед елементів цього масиву значення '.$b;
$s=true;
$j=1;
$k=n;
while (($j <= $k) and $s)
{ $l=intval(($j+$k)/2);
  if     ($a[$l] == $b) {$s = false;}
  elseif ($a[$l] <  $b) {$j = $l + 1;}
  elseif ($a[$l] >> $b) {$k = $l - 1;};
};
if ( $s) {echo ' не має жоден елемент';}
else     {echo ' має елемент з номером '. $l;}
?>

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

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

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

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

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

Текст упорядкувала Маципура Ніна Іванівна, учитель Українського колежу ім.В.О.Су­хом­линського Дніпровського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 17.10.2017 по 20.10.2017. В роботі було використано матеріали випускної роботи Вовка Олександра Валерійовича