А706 Алгоритм быстрого возведения в степень

Степень Входная матрица Результирующая матрица
2
0 1
2 3
2 3
6 11
3
0 1
2 3
6 11
22 39

Пусть даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex] и натуральное число [latex]n[/latex]; требуется найти [latex]A^{n}[/latex]. Алгоритм, основанный на непосредственной применении формулы [latex]A^{n} = A*A*A…*A [/latex]([latex]n[/latex] сомножителей), слишком разорителен. Например, [latex]A^{4}[/latex] экономичнее вычислять как [latex]A^{2^{2}}[/latex]. Идея одного достаточно экономичного алгоритма вычисления [latex]A^{n}[/latex] заключается в следующем: если  [latex]n = 2k[/latex], то [latex]A^{n} = (A^{2})^{k}[/latex]; если же [latex]n = 2k + 1[/latex], то [latex]A^{n} = (A^{2})^{k} * A[/latex]. Степень с показателем [latex]k[/latex] вычисляется с учетом этих же соображений. Итак, надо разделить [latex]n[/latex] на [latex]2[/latex] с остатком:[latex] n = 2k + l [/latex] [latex](0\le l\le 1[/latex]), потом это же проделать с [latex]k[/latex] и т.д. Эти действия приводят, как известно, к построению двоичной записи [latex]n[/latex]. Алгоритм, основанный на этой идее, состоит в том, что последовательно вычисляются [latex]A^{a_{0}}, A^{a_{1}*a_{0}}, …,A^{a_{l}*…*a_{0}}, a_{l}*…*a_{0}[/latex] — двоичная запись числа [latex]n[/latex]. Для этого вычисляется, цифра за цифрой, двоичная запись [latex]n[/latex] и, параллельно, степень за степенью,[latex]A^{(2^{0})}, A^{(2^{1})}, …[/latex] — каждая следующая степень получается из предыдущей возведением в квадрат. Подсчитывается произведение тех из вычисленных степеней, для которых соответствующая цифра двоичного представления равна 1. Например, запись [latex]9[/latex] в двоичной системе есть [latex]1001[/latex][latex](9 = 1*8 + 0*4 + 0*2 + 1)[/latex]; для вычисления [latex]A^{9}[/latex] достаточно найти [latex]A^{2},A^{4},A^{8},[/latex]([latex]3[/latex] умножения), а затем определить [latex]A*A^{8},[/latex] ([latex]1[/latex] умножение).

Преимущество этого алгоритма в сравнении с простейшим состоит в том, что простейший алгоритм требует числа умножений, растущего как линейная функция от [latex]n[/latex], а здесь число умножений грубо говоря, пропорционально количеству цифр числа [latex]n[/latex] или двоичному логарифму [latex]n[/latex]. Это преимущество весьма ощутимо при работе с матрицами (из-за трудоемкости каждого умножения), хотя, разумеется, этот алгоритм может быть использован и для вычисления степени любого числа.

Написать программу, реализующую предположенный алгоритм.

Суть алгоритма была описана в задании. Реализация была через свою структуру данных, такую как матрица. В ней мы определили умножение и присваивание, для удобства. Есть несколько конструкторов, но нужен по сути только самый первый, остальные для разыгравшейся фантазии. Инициализация при создании матрицы обязательна, поскольку может выдавать неправильный ответ в связи с забытым  в памяти мусором. Как перемножать матрицы можно узнать здесь. Нам понадобятся три матрицы, исходная, временная и матрица для ответа. Само двоичное представление удобно хранить в строке, поскольку идя по ней и находя [latex]1[/latex] мы можем домножить на  временную  матрицу матрицу ответ.

 

link.

4 thoughts on “А706 Алгоритм быстрого возведения в степень

  1. — Почему в названии вдруг «Перемножение матриц»? В задаче требуется реализовать алгоритм быстрого возведения в степень.
    — Если Вы написали класс для матриц, то почему быстрое возведение в степень не сделали его методом?
    — Зачем целый массив матриц? Это очень расточительно. Для чего можно использовать больше трёх матриц — исходная, очередная степень, результирующая.
    — Где тесты? Как Вы проверяли, что программа работает? Пришлось придумывать самому:
    $$\begin{pmatrix} 0 & 1\\ 2 & 3 \end{pmatrix} \times \begin{pmatrix} 0 & 1\\ 2 & 3 \end{pmatrix} = \begin{pmatrix} 2 & 3\\ 6 & 11 \end{pmatrix}$$
    Ваша программа 4 раза выводит 2 11.

    Вывод. Опять торопитесь лишь бы сдать на проверку и забыть.
    Ну, хорошо, я вместо Вас проверил.
    Поставил 0.
    И что? Все труды (и мои, и Ваши) никак не скажутся на оценке?

  2. Отлично. Сделал тесты молча, видимо обиделся.
    Теперь осталось еще прочесть мой самый первый вопрос:
    «– Почему в названии вдруг “Перемножение матриц”? В задаче требуется реализовать алгоритм быстрого возведения в степень.»

Добавить комментарий