Ridicarea la putere a unei matrici

[•Mitza444]

Cum pot sa ridic la o anumita putere  n  o matrice?? Am nevoie pt. ACSL pt. problemele cu grafuri in care se cer sa se gaseasca numarul drumurilor de lungime  n  dintr-un nod sau din toate nodurile.Am vazut ca se poate afla numarul lor prin ridicarea matricii de adiacenta la putere(puterea=lungimea unui drumului) si mi se pare mai usor si mai sigur decat sa  numeri drumurile pt. ca poti gresi foarte usor asa.

[•laurion]

pentru a inmulti 2 matrice: (de exemplu cu 2 linii si 2 coloane)

Cod:

inline void mult(int A[][2],int B[][2])
{
    double C[2][2]= {0};
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                C[i][j] += A[i][k] * B[k][j];
    memcpy(A,C,sizeof(C));
}

iar pentru a ridica la putere, folosesti ridicarea la putere in timp logaritmic: http://infoarena.ro/problema/lgput si in loc sa inmultesti a*a sau a*b faci mult(a,a) unde "a" este o matrice in cazul asta...
Exemple:
http://infoarena.ro/problema/iepuri
http://infoarena.ro/problema/swaps -- de la Algoritmiada 2012, runda 3 (super problema)

[•Mitza444]

Mersi!!Dar nu este si un algoritm mai usor pentru a ridica matricea la o putere pe foaie??Imi trebuie la partea de short problems unde nu poti folosi calculatorul,doar o foaie si un pix.(cred ca am uitat sa mentionez )

[•laurion]

pe foaie... inmultesti singur... dar de obicei la probleme de mate gasesti formula(inmultesti de 3-4 ori si iti dai seama de regula), si apoi faci inductie

[•popoiu.george]

Daca ai de ridicat la o putere o matrice patratica de ordin 2 poti folosi teorema lui Cayley-Hamilton. Google it. 

[•Mitza444]

Pai matricea mea poate fi si mai mare depinde de numarul nodurilot din graf.Am atasat un exemplu la ce folosesc matricea ca sa fie mai clar. (eu nu stiu cum au obtinut matricea a 2-a si a 3-a,cum au ridicat la putere sa ajunga la acelea)

[•psycho21r]

Probabil el este clasa a 10-a sau a 9-a, asta se învață în clasa a 11-a, așa că doar vrea să știe cum se înmulțesc două matrici.

Când ai de înmulțit două matrici, nu înmulței fiecare element cu elementul său corespunzător, metoda este puțin mai complicată. Caută pe google matrix multiplication și ar trebui să găsești răspunsul.

LE: Dacă nu te descurci, revino cu întrebări.