1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310
1

Возведение матрицу в степень

28.03.2018, 13:05. Показов 15976. Ответов 8
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Всем привет. Надо реализовать алгоритм возведения матрицы в степень. Понимаю как умножать матрицу(возвести в квадрат):
C++
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
#include <iostream>
#include<math.h>
 
using namespace std;
 
int main() {
    double a[100][100], c[100][100];
    int i, j, l, n=2;
    double s(0);
 
    for (i = 0; i<n; i++) {
        for (j = 0; j<n; j++) {
            c[i][j]=0;
        }
    }
 
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 2;
    a[1][1] = 3;
 
    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;
}
Но как возвести в n-ую степень особо не понимаю. Подскажите, пожалуйста.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.03.2018, 13:05
Ответы с готовыми решениями:

Вычислить сумму чисел от 1 до N, возведенных в степень M. Возведение в степень оформить как многократное умножение
Не знаю как это написать.. или объясните пожалуйста или помогите сделать)

Возведение в степень
подскажите,пожалуйста, способ реализации (алгоритм)операции возведение в степень числа с...

Возведение в степень
Вот почему она не работает? #include &lt;stdio.h&gt; #include &lt;iostream&gt; #include &lt;math.h&gt; int...

возведение в степень!
Кто помнит функцию возведения в степень.?? &quot;трам-пам-пам&quot; (a,b) ???? Добавлено через 3 минуты...

8
474 / 426 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
28.03.2018, 13:10 2
Цитата Сообщение от Андей Посмотреть сообщение
Понимаю как умножать матрицу(возвести в квадрат):
Что есть квадрат? - Это умножить матрицу на саму себя 1 раз.
Что есть n`ая степень? - Это умножит матрицу саму на себя n-1 раз.

Реализуйте алгоритм умножения матриц, у вызывайте его n-1 раз.

P.s. n-1 в связи с тем, что за 1 элемент выступает сама матрица изначальная.
0
1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310
28.03.2018, 13:14  [ТС] 3
Просто, когда я умножаю саму на себя делаю так:
C++
1
2
3
 for (j = 0; j<n; j++) {
                s += a[i][j] * a[j][l];
            }
И этот ответ заношу в другую матрицу. Просто пока не особо представляю как.
0
474 / 426 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
28.03.2018, 13:17 4
Цитата Сообщение от Андей Посмотреть сообщение
Просто, когда я умножаю саму на себя делаю так
Почитайте, что такое умножение матриц. Это не просто умножение элементов, это алгоритм, по которому каждый элемент новой матрицы образуется путем Умножения соответствующего столбца первой матрицы умножается на каждый элемент второй матрицы и результаты умножения складываются, образуя этот новый элемент.

Готовых алгоритмов уйма (да и сложности сделать тоже нет), оберните в функцию и действуйте.
0
1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310
28.03.2018, 13:30  [ТС] 5
я вроде так и делаю
0
474 / 426 / 290
Регистрация: 10.03.2015
Сообщений: 1,782
28.03.2018, 13:34 6
Андей, виноват, в коде комментария подумал, что вы умножаете элемент сам на себя.
Матрица должна быть квадратная (что у вас и есть, само собой).
Создаете функцию, которая принимает матрицу и количество раз сколько ее умножать на себя.
И циклом умножаете нужно количество раз.
0
1 / 1 / 1
Регистрация: 20.09.2014
Сообщений: 310
28.03.2018, 13:43  [ТС] 7
просто если степень будет 10000000000(ответы брать по модулю), то так будет очень долго считать
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
28.03.2018, 14:26 8
Цитата Сообщение от Андей Посмотреть сообщение
то так будет очень долго считать
Воспользуйся бинарным возведением в степень, только замени числа на матрицы.
0
1505 / 968 / 812
Регистрация: 30.04.2016
Сообщений: 3,334
31.03.2018, 18:55 9
Лучший ответ Сообщение было отмечено Андей как решение

Решение

Андей, здравствуйте! Вот код, если я все правильно понял. Я учел и это:
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Воспользуйся бинарным возведением в степень, только замени числа на матрицы.
Мой код:

C++
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
#include <bits/stdc++.h>
 
using namespace std;
 
void MatrixInput(int** a, int n)
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }
}
 
int** Multiply(int** a, int** b, int n)
{
    int sum;
    int** c = new int*[n];
    for (int i = 0; i < n; i++)
    {
        c[i] = new int[n];
    }
    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < n; i++)
        {
            sum = 0;
            for (int r = 0; r < n; r++)
            {
                sum += a[j][r] * b[r][i];
            }
            c[j][i] = sum;
        }
    }
    return c;
    for (int i = 0; i < n; i++)
    {
        delete[] c[i];
    }
    delete[] c;
}
 
int** MatrixPower(int** a, int n, int m)
{
    if (m == 1)
        return a;
    if (m % 2 == 1)
        return Multiply(MatrixPower(a, n, m - 1), a, n);
    else {
        a = MatrixPower(a, n, m / 2);
        return Multiply(a, a, n);
    }
}
 
int main()
{
    int n, power;
    cout << "Enter a matrix size:" << "\n";
    cout << "n = ";
    cin >> n;
    int** a = new int*[n];
    for (int i = 0; i < n; i++)
    {
        a[i] = new int[n];
    }
    cout << "Enter a matrix:" << "\n";
    MatrixInput(a, n);
    cout << "Enter matrix power:" << "\n";
    cout << "power = ";
    cin >> power;
    a = MatrixPower(a, n, power);
    cout << "Target matrix:\n";
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout.width(3);
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    for (int i = 0; i < n; i++)
    {
        delete [] a[i];
    }
    delete [] a;
    system("pause");
    return 0;
}
1
31.03.2018, 18:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.03.2018, 18:55
Помогаю со студенческими работами здесь

Возведение в степень
Вам конечно это покажется тупой проблемой, но всё же. Напишите пожалуйста как возводить в степень...

Возведение в степень!
Возник вопрос - Возможно пока не понятна в чем мысль! Попробую на примере объяснить!...

Возведение в степень
Почему, когда я пытаюсь возвести в квадрат x с типом int, то получается 24, а когда с типом double,...

Возведение в степень. C++
можно ли написать программу для возведения в вводимую степень вводимого числа с помощью рекурсивной...

Возведение в степень
Совсем недавно начал изучать C++. Учу по книге. Было задание: Вводишь число Вводишь степень в...

Возведение в степень!
Определить {\chi }^{15} без использования функций и не более чем 5-ю арифметическими операциями.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru