Приклади виконання практичних завдань. Приклад 1. Задано множину {1,2,3,4,5,6,7}

Приклад 1. Задано множину {1,2,3,4,5,6,7}. Побудуйте 10 розміщень по 4 елементи із цієї множини, лексикографічно наступних після 4517.

Розв’язок. Знаходимо у розміщенні 4517 перше справа число, яке можна збільшити за допомогою чисел, що знаходяться справа від нього, або ж чисел {2,3,6}, яких немає у розміщенні.

Число 7 не підходить, бо є найбільшим. Отже, ми збільшуємо число “1” яке можна змінити на одне з чисел {2,3,6,7}. На місце 1-ці ставимо найменше з цих чисел, яке більше від неї. Отримуємо, що перші 3 числа є 452. На місце 7 ставимо найменше з чисел, які не входять в розміщення, тобто “1”. В результаті отримуємо розміщення чисел 4521, яке є лексикографічно наступною після 4517.

Повторюємо попередні дії: останнє число, яке можна збільшити – це “1”, яку ми збільшуємо на одне з доступних чисел {3,6,7}, тобто “3”, і в результаті ми отримуємо 4523. Аналогічно отримуємо наступні числа: 4526 та 4527.

Тепер, оскільки останнє число в розміщенні “7” збільшувати уже не можна, то збільшуємо попереднє число “2” на найменше, яке водночас є більше “2”, решту чисел впорядковуємо у висхідному порядку(числа з множини), отримуємо наступне розміщення 4531.

Продовжуючи процес отримуємо 4532, 4536, 4537, 4561, 4562. ▲

Приклад 2. Задано множину {1,2,3,4,5,6,7}. Побудуйте 5 сполучень без повторень по 4 елементи лексикографічно наступних після {1, 4, 5, 6}.

Розв’язок. Сполучення будемо подавати без дужок, для спрощення запису, тобто {1, 4, 5, 6} будемо подавати як 1456, пам’ятаючи, що цифри можуть бути лише у висхідному порядку.

Побудуємо наступне лексикографічне сполучення після 1456. Очевидно, що його можна отримати, збільшивши останній елемент, і отримати 1457.

При отриманні наступного лексикографічного сполучення після 1457, останнє число збільшити не можна (бо 7 є найбільшим числом у вихідній множині). Тому ми збільшуємо друге число справа, тобто “5”. Отримуємо перші три числа перестановки – 146. Оскільки порядок у перестановці повинен бути висхідним, то на останнє місце ми повинні поставити число, більше за “6”, тому наступна перестановка рівна 1467.

Побудуємо наступне лексикографічне сполучення після 1467. Останнє число збільшити не можна, тому переходимо до “6”. “6” також збільшувати не можна, бо отримаємо перші три числа перестановки 147, і тоді останнє число має бути більше “7”. Тоді переходимо до наступного числа “4”. Його можна збільшити до “5”, а наступні числа мають бути у висхідному порядку, з чого випливає, що наступна перестановка може бути лише 1567.

Виходячи з попередніх міркувань, у наступному сполученні можна збільшувати лише останній елемент, тобто першим елементом перестановки буде “2”. Наступні числа будуємо у висхідному порядку, і отримаємо 2345.

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

Розв’язок. Для того, щоб реалізувати перебір, нам необхідно увести лексикографічний порядок та визначити процедуру знаходження лексикографічно наступного порядку. Для спрощення задачі вважатимемо намистину білого кольору “0”, а синього – “1”. Отже, задача зводиться до наступної – реалізувати перебір усіх бітових рядків довжиною 6, так щоб при повороті рядка на 180 градусів не було збігів.

Тобто бітові рядки 100101 і 101001 вважаються однаковими, бо їх можна утворити одна з одної переворотом на 180 градусів. Як і у переборі сполучень, введемо обмеження, щоб уникнути повторів: оскільки такі рядки вважаються однаковими, розглядатимемо тільки ті рядки, переворот яких веде до зменшення значення.

Поділимо умовно нитку на 2 частини.

.

Переворот веде до числа 001011, що є менше за задане. Отже перша половина рядку має бути більша за другу, записану у зворотньому порядку. Знову таки, для спрощення, введемо оператор F, який обертає другу частину рядка, а перші три цифри залишає без змін:

F(101100)= 101 001, F(111110)= 111 011, і т.д.

Тепер визначити лексикографічний порядок дуже просто – можна порівнювати бітові рядки, тобто:

Рядок більший від рядка , якщо:

F() >F().

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

Покажемо, як діятиме алгоритм.

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

Оскільки частини не рівні, то наступний рядок буде 001 001.При повороті отримуємо 001 100. Отже, оскільки в попередньому рядку права і ліва частина рівні, то отримуємо 010 000. Наступні варіанти будуть рівними 010 100, 010 010, 011 000, 011 100, 011 010, 011 110, 100 000, 100 100, 101 000 і т.д.

Приклад 4. Для роботи над програмним проектом потрібно відібрати групу з 7 програмістів з двадцяти. Скількома способами можна це зробити? Скількома способами можна скласти список з семи програмістів із двадцяти?

Скількома способами можна роздати цим програмістам 7 різних завдань? Скількома способами можна розділити відповідальність між програмістами за підтримку роботи проекту, щоб троє відповідали за написання Unit-тестів, двоє за постійну інтеграцію проекту і двоє за постачання проміжних версій клієнту?

Відомо, що керівник проекту за результатами роботи проекту надіслав 5 різних листів з інструкціями окремим програмістам. Скількома способами він міг це зробити, якщо жоден адресат не отримав більше одного листа? Скількома способами він міг це зробити, якщо кожному адресату він міг відіслати кілька листів?

Розв’язок. Для того, щоби правильно обчислити кількість вибірок, необхідно точно визначити тип вибірки. Для цього необхідно:

· визначити, чи елементи у вибірці можуть повторюватись, чи ні;

· визначити, чи елементи у вибірці будуть впорядкованими. Якщо вони не впорядковані, то це сполучення, в протилежному разі маємо справу з розміщеннями або перестановками;

· якщо вибірка є розміщенням або перестановкою, то треба точніше визначити її тип. Якщо вибрати без повторень, то формула для кількості така сама, а якщо вибірка з повтореннями, то треба визначати кількість способів її отримання відповідно до означення;

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

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

.

Якщо складати список програмістів, то вибірка буде впорядкованою, тому скористаємось формулою розміщень без повторень:

.

Для того, щоб обчислити кількість розподілу завдань, уявімо, що ми маємо фіксований список програмістів і навпроти кожного імені пишемо його завдання (табл. 13.1.). Міняючи порядок завдань (але при цьому залишаючи порядок імен розробників сталим), отримуємо різні варіанти розподілу завдань.

Таблиця 13.1. Список завдань.

1. Максим	1. Розробка бізнес-логіки
2. Олег	2. Розробка рівня БД
3. Тарас	3. Дослідження SSO
. . .	. . .

Таким чином, вибірки є впорядкованими, не містять повторень, і кожна з них включає усі елементи. Отже, це перестановка без повторень.

Для того, щоб обчислити кількість розподілу додаткових відповідальностей, скористаємось попередніми судженнями, записавши навпроти кожного імені його відповідальність (табл. 13.2).

Таблиця 13.2. Список відповідальностей.

1. Максим	1. Написання Unit-тестів
2. Олег	2. Continuous integration
3. Тарас	3. Написання Unit-тестів
. . .	. . .

Таким чином, єдина відмінність із попереднім варіантом у тому, що в даному варіанті маємо перестановку з повтореннями:

.

Обчислимо кількість способів розсилань листів. В даному вибірка є розміщенням з усіх семи розробників проекту по п’ять чоловік. У випадку якби лист був однаковий, то ми б мали сполучення, але різні листи ми надсилаємо різним людям, тому вибірка є розміщенням. Вибірка також не може бути перестановкою, бо листи розіслані тільки п’ятьом людям. В першому випадку всі адресати різні, тому розміщення не має повторень:

.

В другому випадку адресати можуть повторюватись, тому скористаємось формулою розміщень з повтореннями:

.

Приклад 5. Скількома способами можна вибрати дві пари карт (дві дами і два туза, дві двійки і два валети, тощо)? Вважати порядок карт несуттєвим.