Скільки можна?
(https://www.e-olymp.com/uk/problems/20)
Дано натуральне число n. Від даного числа віднімемо суму цифр цього числа, від утвореного числа знову віднімемо суму цифр утвореного числа і т. д. Дану операцію над числом будемо виконувати, поки утворене число додатне. Скільки разів будемо виконувати дану операцію.
Вхідні дані
Одне натуральне число n, що не перевищує 2 *109.
Вихідні дані
Кількість виконаних операцій.
Ліміт часу 2 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
21
Вихідні дані #1
3
Дана задача – яскравий приклад задач на e-olymp, умови яких не дають можливості розв’язання задачі на 100% мовою python через обмеження часу. Всі знають, що python – інтерпретатор, а, відповідно, достатньо повільний.
На python наразі я зробив два розв’язки, обидва проходять 70% тестів на e-olymp. Рішення на 100% я не знайшов.
Виникає концептуальне питання – а як до цього ставитися? На дану хвилину я переконаний, що python – найкращий для навчання учнів (незважаючи на неймовірну крутизну Brainfuck і Whitespace). І треба враховувати, що частину задач в системі e-olimp не можна здати на 100% мовою python. Виходів тут, як мінімум, я бачу два:
1. Прийняти такий стан речей як інформацію і жити далі. Якщо ви плануєте у майбутньому бути програмером, то вам скоріше за все з часом буде треба познайомитися з однією з швидких, «компільованих» мов, щось із родини сі-подібних. Якщо ваші думки плинуть у сторону продуктів яблучної компанії, то варто звернути увагу на Objective C та найновішу на даний час мову від Apple під назвою Swift. Не можу рекомендувати Pascal. Вчити мову, знання якої не допоможе вам у працевлаштуванні, немає практичного сенсу. Нішу простої мови для початкового навчання шикарно зайняв python, а для швидких програм дідусь Pascal не може бути конкурентом родині сі, яка живе і розвивається.
2. Другий вихід при неможливості здати частину задач на e-olymp мовою python завдяки обмеженнях по часу – це відмовитися від мови python, замінив її на варіант з родини сі. Мені цей варіант менше подобається, як мінімум, через більш складний синтаксис сі, необхідність типізації і описання змінних, більшу кількість «магії» при написанні програм. Те, що на python робиться просто і прозоро, далеко не завжди на сі так само. Мені здається, що python для програмування – чудовий і для початківців найкращий (як ефективно хреститися, хтось знає?).
Саме тому я буду пропонувати собі і своїм учням задачі такого класу розв’язувати алгоритмічно, шукати оптимальне рішення, можливо розв'язок в даних умовах існує. Якщо планувати майбутнє в IT, то готувати голову для пошуку оптимальних розв'язків - дуже перспективно. Ну а якщо частина тестів при всіх оптимізаціях не проходить по часу на e-olymp, то пропоную (плювати слюнями - закреслено) до цього відноситися філософськи.
А для аналізу даної задачі пропоную два підходи. Вони різняться способом отримання суми розрядів числа.
Перший підхід – для тих, хто не шарить в математиці або плутається з div та mod
(звичайно, по таким програмерам плаче ремінь і біржа безробітних, я в курсі).
Можна визначити суму цифр за допомогою list comprehension. При такому підході значення текстової змінної n буде перебиратися посимвольно:
n = input()
sumа_tsyfr = sum([int(x) for x in n])
(до речі, можете спробувати так просто на Сі написати)
Звичайно, для математичних розрахунках нам треба буде конвертувати текст в число, а по звершенню розрахунків, знову повертатися до текстової змінної, бо ми з неї отримуємо суму цифр.
Другий підхід – математичний. Сума цифр числа визначається в python просто і зручно через функцію divmod, Зручно і концептуально правильно оформити підрахунок суми цифр числа в функцію. Ми даній функції передаємо число, функція повертає суму його цифр. Можливо так:
def suma_tsyfr (x):
result = 0
while x > 0:
x, a = divmod(x, 10)
result += a
return result
Окреме питання – обнулення змінної result. Тут це не лише обнулення, а ще і ініціалізація. Якщо другий рядок видалити, програма видасть помилку на рядку result+=a (local variable 'result' referenced before assignment). При цьому я рекомендую в програмах використовувати обнулення змінних. Якщо так звикнути, то нас не будуть цікавити налаштування «по замовчуванню» компіляторів і інтерпретаторів.