Конструктор уроків
Цілі:
навчальна: алгоритм двійкового пошуку
розвивальна: розвивати логічне мислення; формувати вміння діяти за інструкцією, планувати свою діяльність, аналізувати i робити висновки;
виховна: виховувати інформаційну культуру учнів, уважність, акуратність, дисциплінованість.
2
3
4
Як налаштувати пристрій або алгоритм?
У відео продемонстровано як базове оформлення автомобіля можна змінити програмним способом.
Аналогічний підхід застосовується, коли використовують певний алгоритм до розв'язування конкретної задачі: "підганяють" окремі його частини, залишаючи базову структуру без змін.
5
Алгоритм двійкового пошуку (алгоритм ділення відрізка навпіл або дихотомія) - це пошук конкретного значення у масиві або кореня рівняння з певною точністю на числовому інтервалі [a; b]
Кількість кроків пошуку, які здійснює алгоритм:
1) якщо виконувати лінійний пошук серед n чисел, то потрібно виконати n порівнянь серед цих чисел;
2) якщо застосовувати алгоритм двійкового пошуку, то виконується Log2n порівнянь (онлайн-калькулятор)
6
Етапи алгоритму двійкового пошуку
Підготовка.
1) n чисел, до яких застосовують алгоритм двійкового пошуку, мають бути обов'язково впорядковані за зростанням чи спаданням
2) На початку пошуку встановити ліву та праву межу масиву або числового інтервалу.
Виконання
Результат виконання
Після виконання алгоритму змінна r (right) або дорівнює шуканому елементу, або вказує на найближчий до шуканого більший елемент (елемент справа на числовій осі).
Змінна l (left) на самий ближчий менший елемент до шуканого елемента (зліва на числовій прямій).
7
Задача. Вгадай число
Ознайомитись з умовою задачі на EOlymp
Скласти програму
Підказки:
ідея алгоритму: за допомогою алгоритму двійкового пошуку обчислити задумане число на інтервалі [1; n]; щоб врахувати всі можливі варіанти (коли n парне або непране, коли задумане число лежить в інтервалі [1; n], або на лівій чи правій межі - використати нескінченний цикл (цикл зупиняється коли знайдено співпадіння з задуманим числом)
Виконати тестування програми на сервері.
Надіслати скріншот програми та результатів тестування на сервері.
.png)
8
Задача. Дуже Легка Задача
Ознайомитись з умовою задачі на EOlymp
Скласти програму
Підказки:
Ідея алгоритму: знайти мінімальний час друку n-1 сторінки за допомогою алгоритму двійкового пошуку, а потім мінімальний час для друку першої сторінки на найшвидшому ксероксі; результати - додати
Виконати тестування програми на сервері.
Надіслати скріншот програми та результатів тестування на сервері.
9
Домашнє завдання
Вивчити етапи алгоритму двійкового пошуку
Вивчити алгоритми розв'язування задач "Дуже Легка Задача" та "Вгадай число"
Рефлексія від 8 учнів
Сподобався:
Так: 7
Ні: 1
Зрозумілий:
Так: 7
Ні: 1
Потрібні роз'яснення:
Ні: 7
Так: 1
