Данная задача довольно распространена в математике и в программировании.
Главным образом приходится иметь дело с её частным случаем. Проверкой, является ли число степенью двойки. Но иногда также возникает необходимость проверить, является ли число степенью числа отличного от двух.
Рассматриваемая задача по праву считается одной из самых простых. Однако если при проверке на степень двойки ещё вспоминают битовые операции, то в случае других оснований степени у многих почему-то возникают затруднения. При этом существует простой и, главное, универсальный способ решить эту задачу с помощью всего лишь на всего одной единственной строки кода.
Этот способ основан на использовании логарифмов.
Допустим, есть два числа a и b. Если a является степенью b, то:
- Логарифм a по основанию b есть целое число;
- Частное логарифмов чисел a и b по одному основанию есть целое число. Так как это, по сути, тот же логарифм числа a по основанию b.
То есть, для проверки достаточно просто вычислить логарифм a по основанию b или частное логарифмов этих чисел по одному основанию и проверить является ли результат целым числом.
Наиболее предпочтителен подход с применением частного натуральных логарифмов, так как готовые функции для вычисления логарифма по произвольному основанию доступны не всегда.
Рассмотрим примеры реализации этого подхода на Delphi, C++, C#, Java и PHP. В тех случаях, где возможно вычисление логарифма по произвольному основанию с использованием штатных средств будет приведён альтернативный вариант.
Delphi
Вариант с использованием натуральных логарифмов:
|
1 2 3 4 |
function IsPower(a, b: double): boolean; begin result := (Frac(ln(a)/ln(b)) = 0); end; |
Альтернативный вариант:
|
1 2 3 4 |
function IsPower(a, b: double): boolean; begin result := (Frac(logN(a,b)) = 0); end; |
В обоих случаях требуется задействовать модуль Math.
C++
Для C++ существует множество библиотек. Однако в стандартной библиотеке доступны только функции для вычисления натуральных и десятичных логарифмов, а также логарифмов по основанию 2.
Поэтому приведём пример только для натуральных логарифмов с использованием функций стандартной библиотеки (модуль math.h).
|
1 2 3 4 |
bool isPower(double a, double b) { return trunc(log(a) / log(b)==(log(a) / log(b))); } |
C#
В C# для вычисления натуральных логарифмов и логарифмов по произвольному основанию служат две перегрузки одного и того же метода Log класса Math.
Вариант с использованием натуральных логарифмов:
|
1 2 3 4 |
private bool IsPower(double a, double b) { return Math.Truncate(Math.Log(a) / Math.Log(b)) == (Math.Log(a) / Math.Log(b)); } |
Вариант с использованием логарифмов по произвольному основанию.
|
1 2 3 4 |
private bool IsPower(double a, double b) { return Math.Truncate(Math.Log(a,b)) == (Math.Log(a,b)); } |
Java
В стандартном классе Math логарифмы по произвольному основанию, к сожалению, недоступны. Воспользуемся натуральными.
|
1 2 3 4 |
private static boolean isPower(double a, double b) { return (int)(Math.log(a)/Math.log(b))==(Math.log(a)/Math.log(b)); } |
PHP
В тоже время в PHP можно напрямую вычислить логарифмы обоих типов.
Вариант с применением натуральных логарифмов:
|
1 2 3 4 |
function IsPower($a,$b) { return (int)(log($a)/log($b))==(log($a)/log($b)); } |
Вариант с применением логарифмов по произвольному основанию
|
1 2 3 4 |
function IsPower($a,$b) { return (int)log($a,$b)==log($a,$b); } |
Из приведённых примеров видно, что задача проверки является ли число степенью другого числа, на самом деле не представляет никаких сложностей и для её решения вовсе не требуется писать сложных конструкций. Вполне достаточно возможностей стандартных библиотек используемых языков программирования. Что лишний раз подчёркивает всю важность их изучения.
Важное замечание:
Помимо собственно основ программирования при решении подобных задач необходимо знать также и школьную математику.
В частности: следующее
- Любое число в степени 0 равно 1;
- Логарифма числа 0 не существует.
Добавить комментарий