Розв’яжемо задачу «Гарне число»
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
Якщо так і не видно формули, то звертаємось до екциклопедії цілочислових послідовностей, де в перших рядках і бачимо шукану формулу:
Успіхів!