Уроки математики и физики (RU + UA)

среда, 28 ноября 2018 г.

Урок 1. Прості методи рішення комбінаторних завдань

ВИДЕО УРОК
У повсякденному житті часто доводиться створювати різноманітні комбінації, наприклад: грошових купюр різної вартості, щоб утворити потрібну суму: страв для обіду; матеріалів для ремонту тощо. При цьому виникає запитання: <<Скількома способами можна утворити ту чи іншу комбінацію ?>>. Шукаючи відповідь на нього, ми розв'язуємо особливу задачу. У ній задано елементи для комбінування, а вимагається знайти кількість можливих комбінацій. Такі задачі називаються комбінаторними. Для їх розв'язування використовують різні способи.

Перебір можливих варіантів.

Прості завдання вирішують звичайним повним перебором можливих варіантів.

ЗАДАЧА:

У Маші є спідниця з брюками і кофта, светр, сорочка. Скільки комплектів можна скласти з цього одягу ?
РОЗВ'ЯЗАННЯ:
ЗАДАЧА:

Які двозначні числа можна скласти з цифр  

1,  3,  4,  5 ?

РОЗВ'ЯЗАННЯ:

11,  13,  14,  15,  33,  31,  34,  35,
41,  43,  44,  45,  51,  53,  54,  55.

ПРИКЛАД:

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

РОЗВ'ЯЗАННЯ:

Введемо позначення: математика – М, українська мова – У, історія – І. Якщо на перший урок поставити математику, тоді на другий урок можна поставити або українську мову, або історію, а на третій урок – або історію, або українську мову відповідно. Отримали  2  комбінації:  МУІ  та  МІУ. Міркуючи аналогічно, дістанемо ще  4  комбінації:  УМІ  та  УІМ, ІМУ  та  ІУМ. Отже, розклад можна скласти  6  способами.

Розв'язуючи задачу, ми перебрали всі можливі комбінації із заданих елементів для комбінування. У цьому і полягає суть способу перебору. Щоб перебрати всі комбінації заданих елементів і не загубити якусь із них, варто записувати проміжні результати, наприклад у таблиці.

Табличний метод (усі умови вносяться в таблицю, в ній же виконується рішення).

Вирішити комбінаторні завдання можна за допомогою таблиць. Вони наочно представляють рішення таких завдань.

ЗАДАЧА:

Скільки непарних двозначних чисел можна скласти з цифр:

1,  2,  3,  5,  6,  7,  8,  9 ?

РОЗВ'ЯЗАННЯ:

Складемо таблицю: ліворуч перший стовпець – перші цифри шуканих чисел, вгорі перший рядок другі цифри.
ВІДПОВІДЬ:  40.

ЗАДАЧА:

Маша, Оля, Віра, Іра, Андрій, Миша і Ігор готувалися стати ведучими на Новорічному святі. Назвіть можливі варіанти, якщо ведучими можуть бути тільки одна дівчинка і один хлопчик.

РОЗВ'ЯЗАННЯ:

Складемо таблицю: ліворуч перший стовпець – імена дівчаток, вгорі перший рядок – імена хлопчиків.
ВІДПОВІДЬ

Усі можливі варіанти перераховуються в рядках і стовпцях таблиці.

Побудова граф – схеми.

Граф – сукупність об'єктів із зв'язками між ними.

Об'єкти представляються як вершини, або вузли графа, а зв'язку – як дуги, або ребра.
ЗАДАЧА:

Зустрілися п'ять друзів, як годиться, привіталися один з одним. Скільки рукостискань було зроблено ?

РОЗВ'ЯЗАННЯ:
ВІДПОВІДЬ:  10.

ЗАДАЧА:

Побудуйте відрізок  АВ, і відмітьте на нім  4  точки  М, С, К, Д. Визначите за допомогою граф – схеми кількість відрізків.

РОЗВ'ЯЗАННЯ:
ВІДПОВІДЬ15.

При побудові граф – схем окрім дуг і вершин використовується петля. Вона використовується у випадках, коли вимагається показати, що число ділиться саме на себе.
ЗАДАЧА:
Виберіть граф, на якому показано, що одно число ділиться на інше і на саме себе.
ВІДПОВІДЬ:  Перший граф.
Дерево можливих варіантів рішень.

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

Дерево можливих варіантів – граф, схема, що відбиває структуру завдання, впорядкування багатокрокового процесу ухвалення рішень.

Гілки дерева відображають різні події, які можуть мати місце, а корінь дерева – стан, в якому виникає необхідність вибору.
ЗАДАЧА:

Запишіть усі тризначні числа, які можна скласти з цифр  1, 2, 3, так, щоб числа не повторювалися.

РОЗВ'ЯЗАННЯ:
ЗАДАЧА:

Катя, Олена і Соня сьогодні чергові. Їм треба розставити книги (К), вимити підлогу (П), полити квіти (Ц). Скількома способами вони можуть розподілити між собою обов'язки ?

РОЗВ'ЯЗАННЯ:
ЗАДАЧА:

Які тризначні числа можна скласти з цифр  0,  3,  5 ?

РОЗВ'ЯЗАННЯ:

Побудуємо дерево можливих варіантів, враховуючи, що  0  не може бути першою цифрою в числі.
ВІДПОВІДЬ:

300,  303,  305,  330,  333,  335,  350,  353,  355,
500,  503,  505,  530,  533,  535,  550,  553,  555,

ЗАДАЧА:

Є три слова  "ДРУЖБА", "СПРАВА", "ЛЮБИТЬ". Скількома способами з цих слів можна скласти фразу ?

РОЗВ'ЯЗАННЯ:

Позначимо запропоновані слова буквами:

ДРУЖБА – Д
ЛЮБИТЬ – Л
СПРАВА – Е
ВІДПОВІДЬ:  6 способів.

ПРИКЛАД:

Скількома способами можна розмістити на столі в один ряд підручник, зошит і щоденник ?

РОЗВ'ЯЗАННЯ:

Введемо позначення: підручник – П, зошит – З, щоденник – Щ. бачимо, що вже утворилась перша комбінація. Запишемо її в один ряд і обведемо кожну літеру квадратиком. Від кожного квадратика проведемо по  2  гілки, які показують, що перебирати залишилось із  2  елементів. На кінцях гілок розмістимо квадратики, в які впишемо позначення цих елементів. Залишилось перебрати  по  1  елементу, тому проводимо по  1  гілці від кожного квадратика другого рівня і вписуємо в них відповідні елементи.
Тепер порахуємо кількість квадратиків у найнижчому, третьому рівні. Ії виявляється  6. Отже, підручник, зошит і щоденник можна розмістити  6  способами. Щоб виписати ці комбінації, пройдемо кожним ланцюжком гілок від найвищого до найнижчого рівня:

ПЗЩ,  ПЩЗ,  ЗПЩ,  ЗЩП,  ЩПЗ,  ЩЗП.

У дереві можливих варіантів:

– стільки рівнів, скільки задано елементів для комбінування;
– на кожному рівні проводять стільки гілок, скільки елементів залишилось перебрати. 

Завдання до уроку 1

Комментариев нет:

Отправить комментарий