Пусть даны квадратная матрица А порядка m и натуральное число n; требуется найти:

10. Пусть даны квадратная матрица А порядка m и натуральное число n; требуется найти . Алгоритм, основанный на непосредственном применении формулы (n сомножителей), слишком разорителен. Например, экономичнее вычислять как . Идея одного достаточно экономного алгоритма вычисления заключена в следующем: если , то , если же , то . Степень с показателем k вычисляется с учётом этих же соображений. Итак, надо разделить n на 2 с остатком: (0≤l≤1), потом это же проделать с k и т. д. Эти действия приводят, как известно, к построению двоичной записи n. Алгоритм, основанный на этой идее, состоит в том, что последовательно вычисляются , где - двоичная запись числа n. Для этого вычисляется, цифра за цифрой, двоичная запись n и, параллельно, степень за степенью, - каждая следующая степень получается из предыдущей возведением в квадрат. Подсчитывается произведение тех из вычисленных степеней, для которых соответствующая цифра двоичного представления равна 1. Например, запись 9 в двоичной системе есть 1001 (9 = 1 8+0 4 + 0 2+ 1); для вычисления доста¬точно найти , , (3 умножения), а затем определить (1 умножение). Преимущество этого алгоритма в сравнении с простейшим состоит в том, что простейший алгоритм требует числа умножений, растущего как линейная функция от n, а здесь число умножений, грубо говоря, пропорционально количеству цифр числа n или двоичному логарифму n. Это преимущество весьма ощутимо при работе с матрицами (из-за трудоемкости каждого умножения), хотя, разумеется, этот алгоритм может быть использован и для вычисления степени любого числа.
Написать программу, реализующую предложенный алгоритм.

0

a_maziar, что это?

0