Re: Как быстро посчитать?
От: Буравчик Россия  
Дата: 19.10.15 08:53
Оценка: 3 (1)
Здравствуйте, olimp_20, Вы писали:

_>Пусть в калькулятор введем некоторое натуральное число N. Нажмем клавишу +. Ваша задача: получить на экране число состоящее из одинаковых цифр. Для этого можно выполнять только одно действие: нажать клавишу = (возможно и 0 раз). После первого нажатия получим результат N + N, после следующего нажатия результат увеличивается на N. Нужно определить, можно ли выполнить эту задачу. Если да, то определить первое число состоящее из одинаковых цифр. Количество цифр которые может отображать калькулятор считать неограниченным.


Читать про делители репьюнитов
Вот здесь интересно Удивительные приключения периодических дробей

Или так:

Максимальное количество цифр в искомом числе равное N.
Нужно проверить все числа у которых все цифры одинаковые и число цифр не более N. Таких чисел всего порядка 10*N
Для каждого числа (в порядке возрастания) проверяем делится ли оно на N. Первое найденное число — ответ.

Т.к. числа большие (длинная арифметика), то операции с каждым числом занимают O(количество цифр), в нашем случае O(N).
Итого сложность алгоритма O(N^2), где N — заданное число
Best regards, Буравчик
Отредактировано 19.10.2015 9:51 Буравчик . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.