| Степень | Входная матрица | Результирующая матрица | ||||||||
| 2 |
|
|
||||||||
| 3 |
|
|
Пусть даны квадратная матрица [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] мы можем домножить на временную матрицу матрицу ответ.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include <iostream> #include <string> #include <vector> #include <deque> using namespace std; class matrix{ //создаем класс матрицы, в основном для красивого перемножения private: int n,m; int long long **arr; public: matrix(){ n = 1; m = 1; } matrix(int x){ n = x; m = x; arr = new int long long *[n]; for(int i = 0; i < n; i++){ arr[i] = new int long long [m]; } for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ arr[j][k] = 0; } } } matrix(int x, int y){ n = x; m = y; arr = new int long long *[n]; for(int i = 0; i < n; i++){ arr[i] = new int long long [m]; } for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор for(int k = 0; k < this->m; k++){ arr[j][k] = 0; } } } // выше были описанны конструкторы ~matrix(){ for(int i = 0; i < n; i++){ delete arr[i]; } delete arr; }// деструктор void read(){ for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ cin >> arr[j][k]; } } }//функция ввода void write(){ for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ cout << arr[j][k] << " "; } cout << endl; } }// функция вывода void create(int x, int y){ n = x; m = y; arr = new int long long *[n]; for(int i = 0; i < n; i++){ arr[i] = new int long long [m]; } }//функция измененияколичества выделяемой под нас памяти matrix& operator=(const matrix& x){ for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ arr[j][k] = x.arr[j][k]; } } return *this; }// переопределение оператора присваивания для матриц const matrix operator*(const matrix& x){ matrix ans(this->n, this->m); for(int i = 0; i < this->n; i++){ for(int j = 0; j < this->m; j++){ for(int k = 0; k < this->m; k++){ ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j]; } } } return ans; }//переопределение умножения для матриц matrix& operator*=(const matrix& x){ matrix ans(this->n, this->m); for(int i = 0; i < this->n; i++){ for(int j = 0; j < this->m; j++){ for(int k = 0; k < this->m; k++){ ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j]; } } } *this=ans; return *this; }//переопределение присвоить равно matrix& pow(int n){ string s; for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0 s+= to_string((n >> i)&1);; } int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой matrix ans(this->n,this->m); for(int j = 0; j < this->n; j++){ for(int k = 0; k < this->m; k++){ if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0; } } matrix temp(this->n,this->m); temp = *this; for(int j = 0; j <= i; j++){ if(s[j] == '1'){ ans*=temp; } temp*=temp; } *this=ans; return *this; } }; int main() { int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа cin >> n; matrix mas(size); // создаем матрицу mas.read(); mas.pow(n); mas.write(); return 0; } |