Особисто мені дуже подобаються задачі з кількома розв’язками. Вони навчають споглядати світ навколо з різних сторін.
Одну з таких задач і пропоную вашій увазі.
Я побачив одне рішення, моя учениця Анастасія – ще одне. А, можливо, їх ще більше – аргументованих рішень?
Спробуйте спочатку самостійно знайти кілька рішень, а лише потім переглянути вже знайдені, натиснувши "Детальніше"
Пропоную проаналізувати і розв’язати задачу «Садівник-художник»
https://www.eolymp.com/uk/problems/17
Умова:
Після посадки дерев садівнику потрібно їх пофарбувати. У його розпорядженні є фарба трьох кольорів: біла, синя і помаранчева. Скількома способами він може пофарбувати N дерев, якщо ніякі два однакові кольори не можуть бути поруч?
Вхідні дані:
Кількість дерев N (1 ≤ N ≤ 50).
Вихідні дані:
Кількість способів фарбування.
Приклад:
Вхідні дані:
3
Вихідні дані:
12
Пропоную не звертати увагу на сам факт необхідності фарбування щойно посаджених дерев, тим більше фарбами. Давайте спробуємо розглянути не біологічну дикість, а математичну суть задачі.
У людей, що вивчають комбінаторику є відповідні формули, використання яких робить розв’язок такого роду задач ефективним і елегантним. Але можна спробувати знайти рішення «хлопським розумом», або якщо сучасною мовою, «з використанням логіки і критичного мислення».
Припустим, що у нас одне дерево. Скількома способами його можна пофарбувати? Трьома. Тобто це одне дерево можна пофарбувати білою (Б) фарбою – це один варіант. Або синьою (С) – це другий варіант. Або помаранчевою (П) – третій варіант. Отже, при N = 1 відповідь на нашу задачу – три.
Далі припустим, що у нас два дерева. Скількома способами їх можна пофарбувати так, щоб два кольори не були поряд?
Розпишемо всі варіанти для двох дерев:
БС – це дерева пофарбовані білою і сильною фарбою.
Розписуємо:
1) БС
2) БП
3) CБ
4) СП
5) ПБ
6) ПС
Звернемо увагу, що варіанти БС і СБ ми зараховуємо як різні способи. І у нас виходить шість способів.
Для трьох дерев відповідь є в тестовому прикладі задачі.
Можна спробувати спіймати формулу залежності результату від початкового N:
1 >> 3
2 >> 6
3 >> 12
Бачимо очевидне подвоєння попереднього значення результату. Для олімпіадного програмування, коли на вивід формул часу небагато, багато хто просто скористається циклом, що певну кількість разів подвоїть попереднє значення змінною, наприклад, так:
n = int(input())
s = 3
for _ in range(1, n):
s *= 2
print(s)
До речі, цей код здає задачу на 100%, але для допитливого «хлопського розуму», незважаючи на стать його носія, було б класно вивести формулу, яка б розв'язала дану задачу не циклом, що довго і негарно, а за один раз – елегантно і «вау!». Ну, повинен же бути такий спосіб? Повинен і є.
Ще раз відношення вхідних і вихідних даних:
1 >> 3
2 >> 6
3 >> 12
Спробуйте зловити формулу. Вивести, написати, підібрати. Як вийде. Нехай на це піде година. Або день чи тиждень. Але спробуйте. Покрутіть. І не читайте обговорення цієї задачі на сайті eolymp.com – там один учасник цю формулу відкрито написав. Не підглядайте туди.
Для перевірки вашої формули можна просто здати задачу на сайті eolymp.com
Формулою - швидко і гарно, можна увесь розв’язок умістити в один рядок.
Виведіть формулу, здайте задачу, ну і вже потім, з задоволенням від себе, перегляньте цю саму формулу на екциклопедії цілочислових послідовностей, ось тут:
Успіхів!
Розв’яжемо задачу «Гарне число»
https://www.eolymp.com/uk/problems/7817
Умова:
«Гарним» будемо вважати число, що складається лише з непарних цифр. Наприклад число 157953 гарне, а число 2452117 ні. Необхідно з'ясувати, скільки існує n - значних гарних чисел.
Вхідні дані
Одне ціле невід'ємне число n (1 ≤ n ≤ 20).
Вихідні дані
Вивести кількість гарних чисел.
Приклад
Вхідні дані
4
Вихідні дані
625
Розпочнемо з аналітики.
Якщо числа одноцифрові, тобто n = 1, то таких чисел десять: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Серед них гарних буде п’ять: 1, 3, 5, 7, 9.
Якщо числа двоцифрові, тобто n = 2, то таких чисел всього дев’яносто, від 10 до 99. За допомогою листочка і ручки можна за незначний час порахувати кількість гарних чисел – їх буде 25.
При n = 3 можна також порахувати кількість гарних чисел за допомогою листочка, але то ліньки, бо тризначних чисел аж 900.
При n = 4 ми вже маємо відповідь з тестового прикладу задачі, тому можна спробувати зловити формулу залежності n і результату:
1 >> 5
2 >> 25
3 >> ?
4 >> 625
Якщо ви вже бачите тут формулу – чудово, здавайте задачу. Якщо не бачите, давайте спробуємо порахувати кількість гарних чисел для n = 3.
Уточнимо задачу.
Нам потрібно перебрати всі числа від 100 до 999 і в кожному числі визначити, чи складається число лише з непарних цифр. Звичайно, за допомогою циклу можна перебрати всі числа, за допомогою вкладеного циклу перебрати цифри кожного числа. Але якщо писати на Python, то повинно бути більш гарне і стильне рішення ніж перебір вкладеними циклами.
Пропоную скористатися множинами — структурами даних, що містять невпорядковані елементи, які не повторюються. Давайте кожне число з діапазону 100…999 переведемо в множину, таким чином позбавимося повторів цифр в числі. А далі порівняємо цю множину з множиною непарних чисел. Якщо множина конкретного числа менше або дорівнює множини непарних чисел, то це буде означати, що число складається лише з непарних чисел.
Для незнайомих з множинами, на «Плетиві» є відповідний довідник, побудований по принципу «менше тексту, більше прикладів».
За допомогою наступного коду з використанням множин ми зможемо визначити кількість гарних тризначних чисел:
count = 0
odd = {'1','3','5','7','9'}
for number in range(100,1000):
digits = set(str(number))
if digits <= odd:
count +=1
print(count)
Відповідно, зловити формулу тепер стає простіше:
1 >> 5
2 >> 25
3 >> 125
4 >> 625
Якщо так і не видно формули, то звертаємось до екциклопедії цілочислових послідовностей, де в перших рядках і бачимо шукану формулу:
Успіхів!
На гуртку i7, граємося математикою:
— Назвіть найбільший спільний дільник чисел 12 і 18?
— Шість.
— Добре, напишіть код що це визначить.
— print(math.gcd(12,18))
— Добре, назвіть найменше спільне кратне цих 12 і 18. Тобто НСК.
— Тридцять шість.
— Добре. Пишіть код, що це визначить.
— print(math.lcm(12,18))
— Ой, а ви де це взяли?
— ChatGPT підказав, у Python з версії 3.9
— Ну, тоді у нас сьогодні версія 3.8 і ChatGPT – гріх. Шукаємо НСК в нових умовах ))
Чудовий телеграм-канал "Мат. Салат" опублікував алгоритм визначення дня святкування православного Великодня будь-якого року.
Цитата:
Чим тільки не займалися математики. Наприклад, Карл Фрідріх Гаус у 1800 році представив математичний алгоритм, призначений для визначення дня святкування православного Великодня будь-якого року. Сам Гаус привів формули без висновку. Пояснення кожного кроку алгоритму дав професор Базельського університету Герман Кінкелін у 1870 році.
Для визначення дати Православної Великодня за новим стилем необхідно:
Розділити номер року на 19 та визначити залишок від поділу a.
Розділити номер року на 4 та визначити залишок від поділу b.
Розділити номер року на 7 та визначити залишок від поділу c.
Розділити суму 19a + 15 на 30 та визначити залишок d.
Розділити суму 2b + 4c + 6d + 6 на 7 та визначити залишок e.
Визначити суму f=d+e.
Якщо f ≤ 26, то Великдень святкуватиметься 4 + f квітня; якщо f > 26, то Великдень святкуватиметься f – 26 травня.
Натуральні числа записані підряд - одиниця на першій позиції. А яка цифра буде на 100500 позиції? Якщо не дуже зрозуміла умова, запитайте штучний інтелект, підкаже в доступній формі.
