Лучший способ сделать выключение питания (интервал x, интервал n)?
Так данный x и питание, n, решают для X^n. Существует простой способ, которым это O(n)... Я могу свалить его к O(n/2), путем выполнения
numSquares = n/2;
numOnes = n%2;
return (numSquares * x * x + numOnes * x);
Теперь существует a O(log(n)) решение, кто-либо знает, как сделать это? Это может быть сделано рекурсивно.
5 ответов
Ну, вы знаете, что x a + b = x a x b , так что ...
int pow(int x, unsigned int y)
{
if (y == 0) return 1;
if (y == 1) return x;
int a = y / 2;
int xa = pow(x, a);
if (a + a == y) // y even
return xa * xa;
else
return xa * xa * x;
}
Математическая концепция, которую можно использовать, состоит в том, что x2n+1 = x2n ⋅ x и x2n = xn ⋅ xn.
Вы найдете объяснение здесь: Быстрое возведение в степень . Для некоторых значений n вы можете вычислить x ^ n с меньшим количеством умножений, чем при использовании трюка степени двойки.
Стандартный трюк состоит в том, чтобы сгенерировать степени x в последовательности x 2 , x 4 , x 8 , x 16 , x 32 , ... и включить те, которые необходимы в результате.
Обычная реализация - это нечто подобное (заимствовано из статьи в Википедии ):
long power(long x, unsigned long n)
{
long result = 1;
while (n > 0) {
/* n is odd, bitwise test */
if (n & 1) {
result *= x;
}
x *= x;
n /= 2; /* integer division, rounds down */
}
return result;
}
Рекурсия не требуется или ( Я бы сказал) особенно желательно, хотя по очевидности можно выиграть:
long power(long x, unsigned long n)
{
if (n == 0) return 1;
long result = power(x, n/2); // x ^ (n/2)
result *= result; // x ^ (n/2)*2
if (n & 1) result *= x; // x ^ n
return result;
}
Конечно, в любой версии вы довольно быстро переполняете лонг. Вы можете применить те же алгоритмы к своему любимому представлению bigint, хотя любая библиотека bigint уже будет включать целочисленную степенную функцию.
Обе версии функции выше возвращают 1 для power (0,0) . Вы можете считать это ошибкой, а можете и не считать.