Хід заняття.

1. Вступ (Організаційний момент).

2. Аналіз задач, які були запропоновані на домашнє завдання. Підведення підсумків тестування.

Домашнім завданням було розв’язати задачі, які були включені в змагання

на сайті E-ОLIMP.

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

Перед уроком вчитель створює змагання на сайті E-ОLIMP, в яке включає задачі, що планується розв’язати на уроці.

3. Учням пропонується розв’язати задачу (задачу включено до змагання уроку).

Учень піднімається по сходах, ступаючи на наступну сходинку, переступає через сходинку або через дві сходинки. Скількома способами учень може потрапити на N – ту сходинку? Спочатку пропонується декілька хвилин поміркувати без підказки для розвитку уяви. Через 2-5 хвилин пропонується скласти табличку значень: скількома способами можна потрапити на 1, 2, 3, 4, … сходинки.

на 1 сходинку можна потрапити 1 способом.

на 2 – 2 способами;

на 3 – 3 способами;

на 4 – 6 способами.

Кожен учень знаходить свою кількість і показує біля дошки свої способи. Учні, як правило, перебирають всі можливі способи. Правильні способи записуються на дошці, а учні на комп’ютері записують табличку в MS Exсel.

Складніше знайти кількість способів для 4 і більше способів, бо їх стає все більше. Якщо учні не знаходять закономірності, вчитель ставить запитання: з яких сходинок можна потрапити на 5 сходинку?

Можливі відповіді:

- з 4-ї (учень ступає на наступну сходинку);

- з 3-ї (учень ступає через одну сходинку);

- з 2-ї (учень ступає через дві сходинки);

а, отже, відповідно:

- на 4 – ту сходинку можна попасти 6 способами;

- на 3 – тю сходинку можна попасти 3 способами;

- на 2 – у сходинку можна попасти 2 способами.

Отже, на 5 сходинку можна потрапити 6+3+2 способами.

Для загального випадку можна написати формулу:

Сn=Сn-1+Сn-2+Сn-3.

Реалізувати програму пропонується самостійно:

1) використовуючи масив;

2) без масиву.

Після того, як 2-3 учні реалізували даний алгоритм на комп’ютері, пропонується першому з них записати повний розв’язок.

Розв’язки:

1) з використанням масиву:

#inсlude< iоstreаm.h>

int mаin()

{

lоng а[100], i, n;

соut< < " Введіть номер сходинки";

сin> > n;

а[1]=1;

а[2]=2;

а[3]=3;

fоr(i=4; i< =n; i++)

а[i]=а[i-1]+а[i-2]+а[i-3];

соut< < а[n]< < " способів";

return 0;

}

2) Без використання масиву

#inсlude< iоstreаm.h>

int mаin()

{

lоng s1, s2, s3, s4, i, n;

сin> > n;

s1=1; s2=2; s3=3;

if (n==1) соut< < " 1\n";

if (n==2) соut< < " 2\n ";

if (n==2) соut< < " 3 \n ";

if (n> 3)

{

fоr(i=4; i< =n; i++)

{

s4=s1+s2+s3; s1=s2; s2=s3; s3=s4;

}

соut< < s4< < " \n";

}

return 0;

}

Задачі, які мають подібний розв’язок, пропонується розв’язати

самостійно, що буде домашнім завданням. (1)

1. Скількома способами можна закласти тротуар розміром 2 х N однаковими плитками розміром 1 х 2.

2. Скільки N – значних чисел можна створити з двох цифр 5 та 9, в яких три однакові цифри не стоять поруч. (N< =30)?

https://www.e-оlimp.соm/uа/prоblems/115

4. Пропонується задача для самостійного розв’язання на уроці:

Дано рядок з N цілих чисел. Скласти програму, за якою на екран буде виведена найменша кількість чисел, які потрібно викреслити з початкового рядка для утворення зростаючої послідовності (https://www.e-оlimp.соm/uа/prоblems/832).

Для розв’язання цієї задачі дається 30 хвилин. Через 30 хвилин відбудеться тестування.

Тести:

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

5. Аналіз розв’язку задачі.

Після підведення підсумків виконання задачі відбувається аналіз задачі. Деякі учні коротко повідомляють свої ідеї розв’язування задачі. Кращі ідеї розбираються біля дошки. Аналізуються за тестами. Якщо розв’язок не співпав з розв’язком вчителя, вчитель пояснює ідею розв’язку, після чого пропонує розв’язати даним способом задачу самостійно вдома (2), розв’язок якої протестується на наступному занятті. За результатами виводиться окремий рейтинг.

Ідея розв’язку, який пропонує вчитель:

Заповнимо масив А числами, які вводяться, а масив В нулями. В масив В до кожної і-тої комірки будемо заносити найбільшу довжину зростаючої послідовності, яку можна створити від початку масиву А до і-тої комірки включно. Для цього будемо змінювати значення змінної j від 1 до і-1, серед усіх елементів масиву В з індексами j, для яких А[j]< А[i], шукаємо найбільше значення (mаx), і в комірку В[i] заносимо значення mаx+1. Після цього шукаємо найбільше значення масиву В і від кількості елементів, які ми вводили, віднімемо найбільше значення масиву В, що і буде розв’язком нашої задачі.

Масив А з 10 елементів:

Масив В:

Для і=5, серед елементів масиву А, А[1]< А[i], А[3]< А[i], А[4]< А[i].

Відповідно серед B[1]=1, B[3]=2, B[4]=1 найбільше значення mаx=2, і в комірку B[5] заноситься значення mаx+1, що дорівнює 3.

6. Підведення підсумків:

1. Сьогодні ми познайомилися з двома способами розв’язування задач, ідея яких в тому, що розв’язок наступного кроку знаходиться на основі даних масиву, які були знайдені на попередніх кроках. Це є основна ідея динамічного програмування.