Комбінаторика: формули суми та добутку

Підручник з інформатики для 8 класу (поглиблений рівень вивчення)

Гімнастика для очей

Відеоінструкція (1 хв)

Критерії оцінювання презентації

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

Питання: наскільки надійний такий пароль, тобто, скільки комбінацій потрібно розглянути, щоб підібрати пароль?

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

Методи розв'язання комбінаторних задач:

1) використати комбінаторні формули;

2) використати метод динамічного програмування (тобто одновимірні або багатовимірні масиви для розв'язання допоміжних задач);

3) рекурсивні алгоритми (рекурсивні функції).

Формули суми та добутку

Правило суми: вибрати m способами об'єкт А або n способами об'єкт В .

Правило добутку: вибрати m способами об'єкт А одночасно з n способами об'єкт В

Приклад 1. На пошті продають 3 різних видів конвертів та 4 різних видів марок. Яким числом способів Петрик П'яточкін може купити конверт та марку до нього?

4 способи вибрати марку одночасно з 3 способами вибрати конверт. Отже, 3х4=12 способів (правило добутку).

Розв'язання задачі можна виконати у вигляді дерева варіантів (дерева прийнятих рішень):

Приклад 2. Скільки різних шляхів, які двічі не проходять через одну й ту саму точку, ведуть з A до D?

Дерево вибору варіантів

(3 способи вибрати дорогу АВ)(5 способів вибрати дорогу ВС)(4 способи вибрати дорогу СD) = 60 способів (правило добутку).

Приклад 3. В деякому алфавіті 10 символів (наприклад, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}). Скільки "слів" довжиною 4 символи (наприклад, pin-кодів), можна скласти в цьому алфавіті?

10 * 10 * 10 * 10 = 10 000 способів (або , аналогічно побудувати дерево варіантів) - правило добутку.

Задача. Кількість n-значних чисел

Ознайомитись з умовою задачі на EOlymp: за заданим натуральним числом n виведіть кількість n - значних натуральних чисел.

Підказка до складання алгоритму. Алфавіт для цифр {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. На перше місце можна ставити всі цифри, крім 0.

Для n=3 (тризначного числа) (побудова формули)

відповідь = 9 * 10**2 = 9 * 10**(3 - 1)

Для n-значного числа (узагальнення формули)

відповідь = 9 * 10**(n - 1)

Скласти програму. Виконати тестування на сервері. надіслати звіт.

Підсумок уроку

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

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

Розв'язати задачі (письмово в зошиті).

У Степана на столі лежать 2 яблука та 3 груші. Скількома способами Степан може вибрати 1 яблуко і 1 грушу. (побудувати дерево варіантів).

Аліса має в своєму гардеробі 2 пальто та 3 куртки. Скількома способами Аліса може вдягнути 1 пальто або 1 куртку. (побудувати дерево варіантів).