1

Пытаюсь сделать возведение матрицы в степень. Знаю, как выглядит умножение матриц (возведение в квадрат):

#include <iostream>
#include<math.h>

using namespace std;

int main() {
    double a[100][100], c[100][100];
    int i, j, l, n;
    double s(0);
    cout << "Matrix size:";
    cin >> n;
    cout << endl;

    for (i = 0; i<n; i++) {
        for (j = 0; j<n; j++) {
            c[i][j]=0;
        }
    }

    cout << "a matrix:" << endl;
    for (i = 0; i<n; i++) {
        for (j = 0; j<n; j++) {
            cin >> a[i][j];
        }
    }

    for (i = 0; i<n; i++) {
        for (l = 0; l<n; l++) {
            s = 0;
            for (j = 0; j<n; j++) {
                s += a[i][j] * a[j][l];
            }
            c[i][l] += s;
        }
    }

    cout << "rezult:" << endl;
    for (i = 0; i<n; i++) {
        for (j = 0; j<n; j++) {
            cout << c[i][j] << " ";
        }
        cout << endl;
    }


    return 0;
}

Но как из этого сделать возведение в степень, не представляю. Подскажите. пожалуйста

8
  • 1
    Откройте мат-анализ, раздел операции над матрицами. Там есть название операции и алгоритмы что как делать.
    – nick_n_a
    28 мар 2018 в 9:40
  • просто не особо понимаю как это реализовать 28 мар 2018 в 10:02
  • Во первых нет смысла инициализировать матрицу нулями, а потом числами. А по поводу как это сделать: если нет книги, то погуглите как умножаются матрицы. 28 мар 2018 в 10:17
  • Если я не буду заполнять 0, то там хранится хлам, когда я прибавляю к нему, то получается не тот ответ. Простое возведение я понимаю как, но надо быстрый алгоритм возведения, как его сюда пристроить пока не понимаю 28 мар 2018 в 10:18
  • Вам нужно сразу инициализировать две матрицы какими то числами. чтоб потом эти матрицы умножать 28 мар 2018 в 10:23

2 ответа 2

4

Ну вот смотрите - для чисел это выглядит так:

long long power(long long i, unsigned int p)
{
    long long r = (p%2) ? i : 1;
    while(p/=2)
    {
        i = i*i;
        if (p%2) r *= i;
    }
    return r;
}

Если у вас есть матрица, и функция перемножения матриц типа

mul(a,b,c)

которая в c записывает произведение матриц a*b - то просто

void power(matrix i, unsigned int p, matrix&r)
{
    r = (p%2) ? i : I;  // I - единичная матрица
    while(p/=2)
    {
        mul(i,i,i);
        if (p%2) mul(i,r,r);
    }
}

Собственно, все. Надо только аккуратно написать функцию умножения матриц, чтоб она умела возводить в квадрат или умножать, и записывать на старое место - чтоб вызов типа mul(i,i,i) корректно отрабатывал.

Сами справитесь?

Update

Вот примерный вид такой функции для ваших матриц (раз уж вы их как матрицу 100x100 делаете, а не, скажем, классом):

typedef double matrix[100][100];

void mul(int n, matrix a, matrix b, matrix c)
{
    matrix d;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
        {
            double s = 0.0;
            for(int k = 0; k < n; ++k)
                s += a[i][k]*b[k][j];
            ((c == a || c == b) ? d[i][j] : c[i][j]) = s;
        }
    if (c == a || c == b)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                c[i][j] = d[i][j];
}

Примерно так. Но не тестировал, написано просто чтоб показать идею; так что потестируйте сами.

Update2

По просьбам трудящихся :) - вот это

r = (p%2) ? i : I;  // I - единичная матрица

должно выглядеть примерно так в развернутом коде (n - размер матрицы):

if (p%2)
{
    for(int j = 0; j < n; ++j) for(int k = 0; k < n; ++k)
        r[j][k] = i[j][k];
}
else
{
    for(int j = 0; j < n; ++j) for(int k = 0; k < n; ++k)
        r[j][k] = (j==k) ? 1 : 0;
}

Ну, матрицу i лучше, конечно, переименовать - это имя было взято просто из кода для простого целого числа. Параметр n тоже можете передавать.

А вообще, матрицы - раз уж у нас C++ - лучше организовывать в виде классов...

1
1

Все уже сделано. У вас есть код который умножает одну матрицу на другую. Поместите этот код в функцию

void multiply( const double** a, const double** b, int size, double** result)
{
 //Реализация умножения
}

int main()
{
 double** a;
 double** result;
 //..инициализация
 multiply( a, a, size, result);//Возвели в квадрат
 multiply( result, a, size, result);//Возвели в 3 степень

 multiply( result, a, size, result);//Возвели в 4 степень

 return 0;
}
7
  • смысл понятен, просто хотелось бы воспользоваться быстрым алгоритмом возведения в степень. 28 мар 2018 в 10:26
  • Что вы понимаете под быстрым алгоритмом? Сначала умножение, которое вы реализовали, куда проще(быстрее) я не знаю. Потом просто повторить необходимое количество раз. 28 мар 2018 в 10:37
  • просто если степень будет 10000000000(ответы брать по модулю), то так будет очень долго считать 28 мар 2018 в 10:42
  • а в какой тип вы собираетесь помещать результат таких степеней? Если только в строку... 28 мар 2018 в 10:44
  • Это ж откуда такие степени? Те варианты которые предложены в ответах самые простые. Если реально нужно возводить в такие степени, то, нужно, во первых, писать реализацию больших чисел, потому что в long long int - 64 бита точно не влезет и распаралеливать этот процесс на несколько потоков, это уже нетривиальная задача. 28 мар 2018 в 10:46

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.