Урок 03                                                                                                Інформатика 11 (АП)

Черга.

Мета.

Навчальна. Ввести поняття черга, навчитися записувати елементи в чергу та читати елементи з черги.

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

Виховна. Виховувати наполегливість, естетичність у оформленні, грамотно висловлювати свої думки.

Тип уроку. Засвоєння нових знань і навичок.

Матеріали для роботи з учнями:

Інформатика: Методи побудови алгоритмів та їх аналіз. Необчисл. алгоритми: Навч. посіб. для 9-10 кл із поглибл. вивч. інформатики. - К.: Генеза, 2007.

Мультимедійне обладнання.

План

• Організація класу.
• Мотивація навчальної діяльност.
• Структури даних: проста змінна, масив, стек.
• Практичні завдання.
• Типові запитання до уроку.
• Домашнє завдання.

Пам’ятка для учня!

• Пригадайте правила техніки безпеки при роботі з ПК.
• Через кожні 15 хв. виконуйте вправи для очей та для зняття м’язової втоми.

Хід уроку

1. Організаційний момент.

2. Актуалізація опорних знань.

1. Що називають структурами даних?
2. Чому виникає необхідність організації різних структур даних?
3. Які два основні моменти пов’язані з визначенням структури даних?
4. Які основні дії виконуються над елементами структури даних?
5. Який доступ до елементів заданої структури називають прямим?
6. Який доступ до елементів заданої структури називають послі­довним?
7. Що представляє собою структура даних «масив»?
8. Як відображається на пам’ять комп’ютера одновимірний масив?
9. Дайте означення структури даних «стек».
10. Як структура даних «стек» відображається на пам’ять комп’ютера?
11.  Що називається вершиною стека?

3. Мотивація навчальної діяльності.

Основним завданням будь-якого алгоритму є обробка інформації. Яким чином представити інформацію? Адже від зручно­го способу її представлення залежить і зручність обробки.

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

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

Отже, перш ніж починати обмірковувати питання опра­цювання інформації, треба визначитися, як її представити. Найчастіше на практиці обидва ці процеси взаємопов’язані. Тобто інколи під час роботи з інформацією нам доводиться змі­нювати, вдосконалювати те представлення, що було обране спочатку.

4. Структури даних: черга.

Чергою називається структура даних, організована за і принципом «першим прийшов — першим пішов».

Черга, так само як і стек, відображається на пам’ять комп’ютера у вигляді одновимірного масиву (мал. 7).

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

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

Але при такій логіці існує один суттєвий недолік: після ви­бування з черги першого елемента всі решта повинні зсуватися на одну позицію вліво. Тобто потрібно кожний раз при вико­нанні операції читання виконувати таку послідовність дій:

аі:= аі + 1 для і = 1, 2, ..., <індекс кінця черги >.

Зрозуміло, що така схема обробки операції читання забирає багато часу. Для його економії застосуємо ідею читання елемента стека. Тобто після читання елемента не будемо намагатися знищити його значення, а просто перемістимо індекс початку черги на наступний елемент. Таким чином ми приходимо до ідеї існування двох індексів: і - початок черги, який ще носить назву «голова» черги, та у - кінець черги, що називається «хвостом» черги. Тепер схематично чергу можна зобразити так (мал. 9):

На схемі сірим кольором позначена та частина масиву, в якій розміщені елементи черги.

Подамо алгоритм запису в чергу елемента х:

j:=j+1;

aj:=x.

Тобто ми спочатку збільшуємо значення індексу «хвоста» черги на 1, а потім елементу масиву з індексом j присвоюємо значення х.

Алгоритм читання елемента черги виглядатиме так:

x:=ai;

i:=i+1.

Тобто значення «голови» черги читаємо в х, а потім збіль­шуймо індекс «голови» черги на 1.

Тепер можна уявити собі, що наша черга ніби повзає по маcину, переміщуючись від першого елемента до останнього. Причому елементи черги не розриваються і знаходяться в тій послідовності, в якій записувалися. Можна говорити, що запис y Чергу буде неможливий, тобто черга переповнена, коли «хвіст» досягне останнього елемента масиву, а читання стане неможливим, тобто черга порожня, коли «голова» пережене «хвіст».

Запишемо в термінах такого тлумачення процедуру читання елемента черги:

procedure read_from_queue;

begin

if і > j then writeln(’Queue is empty’)

    else

begin

     writeln(a[i]);

     inc(i)

end

end;

Процедура запису елемента в чергу:

procedure write_to_queue;

begin

       if j = n then writeln(’Queue is full’)

       else

begin

      inc(j);

     readln(a[j])

end

end;

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

Нехай виконуємо лише операції запису в чергу. При цьому «голова» черги весь час знаходиться на першому елементі ма­сиву, а «хвіст» зміщується в сторону останнього. Коли буде до­сягнуто кінця масиву, це означатиме, що черга переповнена і наступні операції запису стануть неможливими. Це видно з наведених вище процедур запису та читання.

Однак ситуація зміниться, якщо поряд із операціями запису виконуватимемо і операції читання з черги. На перший погляд, що запис стане неможливим, коли «хвіст» черги досягне останнього елемента масиву. Але на початку масиву є вільні місця, що залишилися після виконання читання з черги (і > 1). Чому б їх не використати під елементи черги? Для цього треба лише виконати операцію j:= 1. Наша черга ніби завернеться своїм хвостом на початок масиву. Тепер ознакою того що черга переповнена, буде ситуація, коли «хвіст» дожене «то лову». Схематично це виглядатиме так (мал. 10):

Отже, перед тим як розглянути удосконалені процедури запису в чергу та читання з неї, введемо деякі домовленості. Цe пов’язане з тим, що конкретна реалізація алгоритму мовою; програмування не дає можливості використовувати певні умовності. А саме, ми зазначали вище, що виконання умови і = j свідчить про те, що черга порожня, a j = і- про те, що черга повна. Але з погляду будь-якої мови програмування ці дві умови абсолютно ідентичні, тому для їх «розпізнавання» потрібно ввести додаткові ознаки. Однак нашим завданням не є завершена реалізація всіх алгоритмів, оскільки кожний програміст має свій власний «почерк» реалізації алгоритмів. Тому умову і <= j замінятимемо виразом <«голова» передує «хвосту»>, а у <= і - виразом <«хвіст» передує «голові»>.

Тепер запишемо удосконалену процедуру запису в чергу:

procedure write_to_queue;

begin

if (j = і) and (<«хвіст» передує «голові» > )

then writelnfQueue is full’)

else

    begin

readln(a[j]);

if j = n

then

    begin

j:= 1; < «хвіст» передує «голові»>

end

          else inc(j);

     end

end;

Аналогічно можна поставити запитання і щодо «голови» черги, коли вона досягне останнього елемента масиву. Якщо і «хвіст» не збігається з початком масиву, тобто там ще є місце для нашої черги, то чому б не почати відлік «голови» з початку масиву. Тобто якщо і > п, то потрібно виконати операцію і := 1. Удосконалимо і процедуру читання з черги:

produre read_from_queue;

begin

if (і = j) and (оголова» передує «хвосту»>)

then writeln (’Queue is empty’)

else begin

writeln(a[i]); if і = n then

begin

                                                         і:=1;<«голова» передує «хвосту»>

end

else inc(i);

end

еnd;

Ми можемо сказати, що удосконалюючи алгоритм обробки елементів черги, зробили її кільцевою.

Процедуру перегляду елементів черги можна записати в такомуму вигляді:

procedure print_queue;

var k: word;

begin

if <«голова» передує «хвосту»>

then for k := і to j - 1 do write(a[k], ’ ’)

else begin

for k := і to n do write(a[k], ’ ’);

for k := 1 to j - 1 do write(a[k], ’ ’);

  end;

writeln

end;

Залишилося лише визначитися з принципом доступу до еле­ментів черги. Зрозуміло, що в кожний момент часу ми можемо здійснювати операції читання та запису над елементами черги, що знаходяться в «голові» або в «хвості» черги. Дістатися до деякого «внутрішнього» елемента черги ми можемо, лише ви­конавши відповідну кількість операцій читання з «голови» черги. Тому можна зробити висновок, що черга є структурою послідовного доступу.

5. Типові питання до уроку

1. Яка структура даних називається чергою?
2. Як структура даних «черга» відображається на пам’ять ком­п’ютера?
3. Який елемент називають «головою» черги?
4. Який елемент називають «хвостом» черги?
5. Як відбувається читання елементів черги? Запишіть алгоритм читання елемента з черги.
6. Як відбувається запис елементів у чергу? Запишіть алгоритм за пису елемента в чергу.
7. Яким чином організовано ефективну обробку елементів черги?
8. Зобразіть схематично роботу з елементами черги.
9. Запишіть процедуру запису елемента в чергу.
10. Запишіть процедуру читання елемента з черги.
11. Запишіть процедуру перегляду елементів черги.
12. Який принцип доступу здійснюється до значень елементів черги при їх обробці? Обґрунтуйте свою відповідь.

6. Розв’язування задач.

1. Розробити діалогову меню-орієнтовану програму роботи :і елементами черги за такими пунктами:

1) записати елемент у чергу;

2) прочитати елемент із черги;

3) показати вміст черги;

4) показати вміст масиву;

5) завершити роботу з чергою.

2. Протестувати програму завдання 1 для масиву роз­мірністю п = 6, спостерігаючи за вмістом черги і масиву, за та­кою схемою:

-  заповнити повністю чергу;

-   спорожнити чергу;

-  заповнити чергу до половини;

-   вичитати один елемент;

-  записати два елементи;

-  вичитати два елементи;

-  записати чотири елементи;

-  спробувати записати п’ятий елемент;

-  вичитати шість елементів;

-   спробувати прочитати сьомий елемент.

3. Зробити письмовий аналіз виконання завдань 1, 2.

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

1. Вивчити конспект.

2. Підготуватися до тестування.

3. Виконати завдання 1.