Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Рекурсия >> Номер 23

[Назад]    [Содержание ]    [Вперед]

  


Номер 23


  Условие: Номер 23


Задача 22. Возвести число А в натуральную степень n за как можно меньшее количество умножений.

  Решение задачи: Номер 23


Решение задачи 22. Можно, конечно, число A умножить само на себя n-1 раз, но для этого надо выполнить n-1 операцию умножения. Рассмотрим метод, требующий меньшего числа умножений (он, однако, не всегда дает минимальное число умножений). Если n - четное, n=2m то будем вычислять An, используя тождество Aam=(Am)2; если же n=2m+1, то A2m+1=(A2m)*A=((Am)2)*A. Так(м образом, возведение A в 13 степень будет выглядеть следующим образом: (A13)=((A6)2)*A=(((A3)2)2)*A=(((A*A*A)2)2)*A и вычисление требует 5 операций умножения. Используя данный метод, для возведения в степень n потребуется порядка log2(n) операций умножения. Программа на Паскале может выглядеть так: var A,N: integer; function power(N: integer): integer; begin if N>1 then if odd(N) {N нечетно?} then power:=SQR(power(N div 2))*A else power:=SQR(power(N div 2)) else power:=A end; begin read(A,N); writeln(power(N)); end; Можно ту же самую идею реализовать и по другому ( далее мы приводим выдержку из книги Д.Кнута "Искусство программирования для ЭВМ", т.2, с.482): "Запишем n в двоичной системе счисления и заменим в этой записи каждую цифру "1" парой букв SX, а каждую цифру "0" - буквой S, после чего вычеркнем крайнюю левую пару букв SX. Результат, читаемый слева направо, превращается в правило вычисления xn, если букву "S" интерпретировать как операцию возведения в квадрат, а букву "X" - как операцию умножения на x. Например, если n=23, то его двоичным представлением будет 10111; строим последовательность SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем следующее правило вычисления: S SX SX SX. Согласно этому правилу, мы должны "возвести x в квадрат, затем снова возвести в квадрат, затем умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и, наконец, умножить на x"; при этом мы последовательно вычисляем x2, x4, x5, x10, x11, x22, x23. Этот "бинарный метод" легко обосновать, рассмотрев последовательность получаемых в ходе вычисления показателей: если "S" интерпретировать как операцию умножения на 2, а "X" - как операцию прибавления 1 и если начать с 1, а не с x, то наше правило дает нам в соответствии со свойствами двоичной системы счисления число n". Приведенный метод не дает минимального числа операций умножения. Для вычисления x23 нам, по изложенному выше методу, потребуется 7 операций умножения. В действительности их необходимо только 6: x -> x2 -> x3 -> x5 -> x10 -> x20 -> x23. Алгоритм нахождения минимального числа операций (кроме полного перебора) сейчас неизвестен (см. там же у Д.Кнута).

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017