Итеративное логарифмическое возведение в степень
Я недавно разбомбил интервью (экран телефона с коллабитом).
Вот вопрос:
Напишите интерактивный алгоритм O (lg n) для нахождения степени x ^ y (x — это двойное число, y> 0 — это целое число).
Сначала я выполнил рекурсивный метод «разделяй и властвуй» и пытался преобразовать его в итеративный … и я не смог: S
Есть ли метод для преобразования рекурсии в итеративный (это легко для хвостовой рекурсии, но как насчет рекурсивных функций с двумя возможными рекурсивными вызовами, которые зависят от условий, определяющих, какой вызов будет вызван)?
Решение
Типичный способ развернуть это использует побитовое представление b. Вычислить1, 2, 4, 8, и т. д., и на каждом шаге определите, умножать ли это на общую сумму Это показано здесь:
double result = 1;
double multiplier = a;
for (double multiplier = a; b != 0; multiplier *= multiplier, b /= 2) {
if (b % 2 == 1) {
result *= multiplier;
}
}
Например, чтобы вычислить 35, мы заметили, что 5 имеет двоичное представление 101, поэтому мы умножим на 31 и 34.
Надеюсь это поможет!
Другие решения
Других решений пока нет …