Решение задачи №4044
Условие задачи №4044:
Условие: Даны натуральные числа x и n. Вычислить xn, используя алгоритм быстрого возведения в степень:
Решение
Описание отсутствуетРешение:
Разберем этот пока неясный алгоритм, представленный в нашей задаче лишь единственной формулой. Легко понять, что указанное равенство имеет место: например, 34 = 34 div 2 = (32)2 = 92 = 81. Другой пример: 45 = 4 * (42)5 div 2 = 4 * (42)2 = 4 * 162 = 4 * 256 = 1024. Причем если выражение со степенью нельзя в один шаг преобразовать таким образом, то необходимо продолжить преобразование выражения вплоть до получения конечного ответа. Однако как теперь реализовать эту схему?
Рассмотрим пример немного сложнее. Вычислим 47 = 4 * (42)3 = 4 * (16)3 = 4 * 16 * (162)1 = 4 * 16 * 256 = 16384. Стоит обратить внимание на то, что на каждом шаге при вычислении изменяется только единственное обрабатывающееся число, а остальные множители выносятся однократно и необходимы только для получения ответа в последнем действии.
Чтобы исключить их из рассмотрения, при нечетном текущем числе n мы будем домножать на них некоторую промежуточную переменную r, поначалу равную 1 (кстати, нечетность числа в Pascal определяет функция odd), затем (уже независимо от условий) возведем в квадрат текущее x и разделим n на 2 с отбрасыванием остатка. При повторении этих действий на некотором шаге n обязательно станет равным 1. Это происходит потому, что деление любого нечетного числа a на 2 с отбрасыванием остатка равносильно делению на двойку числа (a – 1), которое является четным, и при делении, двигаясь по цепочке четных чисел, мы всегда придем к единице. Условие n = 1 и будет окончанием цикла с предусловием. По выходе из цикла необходимо будет в качестве ответа вывести последнее значение x, умноженное на r.
Теперь алгоритм на естественном языке:
1) Ввод x и n;
2) Присваивание переменной r числа 1;
3) Запуск цикла с предусловием n < > 1. В цикле:
1. Если n нечетно, домножаем r на x;
2. Переменной x присваиваем значение x * x;
3. Переменной n присваиваем результат от деления этой переменной на 2 с отбрасыванием остатка;
3) Вывод выражения x * r.
Код всей программы:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | program FastExponentiation; var x, n, r: word; begin readln(x, n); r := 1; while n <> 1 do begin if odd(n) then r := r * x; x := x * x; n := n div 2 end; writeln(x * r)end. |
Из анализа данного алгоритма известно, что его асимптотическая сложность порядка O(log2n).
