Задача 20 - неможливість здати задачу на 100% на e-olymp.

Надрукувати

Скільки можна?

(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). При цьому я рекомендую в програмах використовувати обнулення змінних. Якщо так звикнути, то нас не будуть цікавити налаштування «по замовчуванню» компіляторів і інтерпретаторів.