ОП 2017: Условия задач

По заданным вещественному значению x и целому неотрицательному значению n вычислите x^n (операция возведения в степень в языке Pascal отсутствует). Для решения задачи используйте алгоритм эффективного возведения в степень. Алгоритм основан на тождестве x^(2n) = x^n * x^n. Тогда, если n = 2^k, то значение x^n можно получить из x, домножая результат сам на себя k раз (таким образом мы будем последовательно получать значения 2-ой, 4-ой, 8-ой, и т.д. 2^k-ой степеней числа x). В свою очередь, произвольное n можно представить как сумму степеней двойки (фактически перевести в двоичную систему счисления): n = 2^k1 + 2^k2 + … Соответственно x^n = x^(2^k1) * x^(2^k2) * ... . Фактически алгоритм быстрого возведения в степень сводится к последовательному получению 2-ой, 4-ой, 8-ой, и т.д. степеней числа x и перемножению необходимых степеней.