Как проверить, является ли число мощностью 5?Как проверить, является ли номер мощностью 5
Я мог придумать ниже алгоритм. Есть ли способ улучшить его? Любой математический трюк?
Вам не нужно смотреть на отдельные цифры, вы можете просто сделать это следующим образом:
n = (int)(log(x)/log(5)); // get n = log5(x), truncated to integer
if (pow(5, n) == x) // test to see whether x == 5^n
// x is a power of 5
Звучит неплохо. Однако с точки зрения программирования/алгоритма метод «журнал» может быть недоступен на всех языках. –
Правда - я не знаю какого-либо современного языка, который не имеет базовых математических функций, таких как 'log',' pow' и т. Д., Но вы никогда не знаете. И, конечно, вы всегда можете реализовать свои собственные версии, если язык их не поддерживает. –
Есть только несколько мощности из пяти, которые соответствуют в межд/длинный поэтому вам нужно просто сгенерировать их все и проверить один за другим (менее 60 номеров), используя HashSet будет иметь сложность времени O (1)
Мой профессор CS использовал, чтобы дать мне числа в больших файлах, а не как int или long. –
@TimothyHa, поэтому в HashSet вы можете хранить строки, BigNums или любое другое представление (например, хэш, арифметика модуля ...). Однако вы можете легко проверить это в O (lg n), не сохраняя результаты. Посмотрите [мой ответ] (http://stackoverflow.com/a/26869655/2349936). Pham Trung: +1, для написания решения O (1) (после предварительной обработки). – Tacet
Последовательное разделение, пока вы не достигнете числа, разделенного на 5 и проверьте, равен ли результат 1, это неплохое решение. Выполняют операции log_5 (n), поэтому это O (lg n), это очень хорошее время. Для 9094947017729282379150390625 это всего лишь 40 операций!
Что такое ** n ** здесь в этом режиме? – Hengameh
Это номер для проверки. (Предполагалось, что деление на 5 имеет сложность O (1).Это явно неверно для чисел с миллионами цифр, но у любого алгоритма есть эта проблема, поэтому я пропустил это.) В том числе размер числа будет около O (lg^2 n). – Tacet
Что бы я сделал, сначала создайте массив чисел с степенями 5. Вы можете использовать диапазон, а затем сказать, для каждого значения в диапазоне, принять это значение в пятую степень и нажать новый значение в массив.
После этого вы обнаружите, что n, номер, который вы ищете, включен в массив.
Этот вопрос не соответствует теме, потому что это математический вопрос (и тот, который имеет достаточную документацию). – Mat
Посмотрите на это: http://math.stackexchange.com/questions/22580/how-to-check-if-a-integer-is-a-power-of-some-integer –
@mat, что вы предлагаете ? Удалить шаг и что делать? Что вы подразумеваете под не по теме. Если вы знаете какую-либо конкретную документацию, просто укажите на нее. Это поможет, чем такие комментарии. –