[C++] Potenza di Matrice
Ciao a tutti, chiedo aiuto in questo forum per risolvere un esercizio proposto nelle dispense dal mio professore di informatica. É un esercizio riguardante le potenze di matrici in c++ (come da titolo). Premetto che, seppur ho passato l'appello di Geometria ed Algebra Lineare, non mi sono mai e poi mai trovato nella situazione di dover calcolare una potenza di matrice, pertanto sono nel buio totale. L'unica cosa che mi viene in mente, sarebbe una moltiplicazione per se stessa della matrice, per un determinato numero di volte...quindi pensavo ad un algoritmo che mi permettesse questo. Vi posto intanto l'intestazione del problema, ed il codice fin'ora scritto:
Scrivere un programma C++ che legge da tastiera (e da file) una matrice m di dimensioni N*M
calcola la matrice trasposta di m, mT
calcola la matrice prodotto m* mT
Per una buona organizzazione del codice vanno definiti e usati i seguenti sottoprogrammi
void calcolaTrasposta(int m[N][M], int t[M][N])
void calcolaProdotto(int m1[N][M], int m2[M][N], int prodotto[N][N])
__________________________________________________________________________________________________
Aggiungere al programma precedente le funzionalità necessarie per calcolare l'n-esima potenza del prodotto di un matrice m per la sua trasposta, ovvero ( m*mT )n
Per una buona organizzazione del codice vanno aggiunti, ed usati almeno i seguenti sottoprogrammi
void calcolaPotenza(int m[N][N], int n, int potenza[N][N])
che calcola mn e restituisce il risultato in potenza
void unita(int m[N][N])
che inizializza m alla matrice unità di dimensione N
void copiaMatrice(int s[N][N], int d[N][N])
che copia elemento per elemento la matrice s nella matrice d
P.S. sinceramente questa volta, non riesco a capire nemmeno perché mi abbia dato questi ultimi sottoprogrammi...
_________________________________________________________________________________________________
Questo é il codice, che riguarda solo la prima parte (perfettamente funzionante
)
Scrivere un programma C++ che legge da tastiera (e da file) una matrice m di dimensioni N*M
calcola la matrice trasposta di m, mT
calcola la matrice prodotto m* mT
Per una buona organizzazione del codice vanno definiti e usati i seguenti sottoprogrammi
void calcolaTrasposta(int m[N][M], int t[M][N])
void calcolaProdotto(int m1[N][M], int m2[M][N], int prodotto[N][N])
__________________________________________________________________________________________________
Aggiungere al programma precedente le funzionalità necessarie per calcolare l'n-esima potenza del prodotto di un matrice m per la sua trasposta, ovvero ( m*mT )n
Per una buona organizzazione del codice vanno aggiunti, ed usati almeno i seguenti sottoprogrammi
void calcolaPotenza(int m[N][N], int n, int potenza[N][N])
che calcola mn e restituisce il risultato in potenza
void unita(int m[N][N])
che inizializza m alla matrice unità di dimensione N
void copiaMatrice(int s[N][N], int d[N][N])
che copia elemento per elemento la matrice s nella matrice d
P.S. sinceramente questa volta, non riesco a capire nemmeno perché mi abbia dato questi ultimi sottoprogrammi...
_________________________________________________________________________________________________
Questo é il codice, che riguarda solo la prima parte (perfettamente funzionante
)#include <iostream>
using namespace std;
int const N=3;
int const M=4;
void leggiMatrice(int matrice[N][M]);
void stampaMatrice(int matrice[N][M]);
void calcolaTrasposta(int m[N][M], int t[M][N]);
void calcolaProdotto(int m1[N][M],int m2[M][N], int prodotto[N][N]);
void calcolaPotenza(int m[N][N], int n, int potenza[N][N]);
int main(){
int matrice[N][M], trasposta[M][N],prodotto[N][N];
leggiMatrice(matrice);
stampaMatrice(matrice);
calcolaTrasposta(matrice,trasposta);
calcolaProdotto(matrice,trasposta,prodotto);
system("PAUSE");
}
void leggiMatrice(int matrice[N][M]){
cout << "Inserisci la matrice " << N << " X " << M << ": " <<endl;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin >> matrice[i][j];
}
}
return;
}
void stampaMatrice(int matrice[N][M]){
cout << "La matrice immessa e': " <<endl;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cout << matrice[i][j] << "\t";
}
cout <<endl;
}
return;
}
void calcolaTrasposta(int m[N][M], int t[M][N]){
cout << "La matrice trasposta e': " <<endl;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
t[j][i]=m[i][j]; //scopri perché solo in questo ordine funziona, e non scrivendo "m[i][j]=t[j][i]"
}
}
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cout << t[i][j] << "\t";
}
cout <<endl;
}
return;
}
void calcolaProdotto(int m1[N][M],int m2[M][N], int prodotto[N][N]){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
prodotto[i][j] = 0; // inizializziamo a zero tutti gli elementi della matrice, grazie ai due cicli "for" nidificati
for(int k=0;k<M;k++){ //(spiegazione accurata) qui usiamo un parametro qualsiasi per bloccare una volta la "riga", una volta una "colonna"
prodotto[i][j] += m1[i][k]*m2[k][j]; // usiamo "+=" per andare a sostituire lo "0" con il prodotto riga per colonna
}
}
}
cout << "La matrice prodotto delle due e': " <<endl;
for (int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout << prodotto[i][j] << "\t";
}
cout <<endl;
}
return;
}
void calcolaPotenza(int m[N][N], int n, int potenza[N][N]){
}
Risposte
Il metodo più semplice per calcolare la potenza di una matrice è certamente quella di moltiplicare la matrice per se stessa \(n\) volte partendo ovviamente dalla matrice identità (se l'esponente è zero il risultato deve essere la matrice identità). Un metodo un po' più efficiente sarebbe quello di usare la "fast exponentiation" (cerca su google il termine e troverà degli algoritmi). Il metodo più semplice da implementare è probabilmente questo. Esistono infine metodi alternativi basati ad esempio sulla diagonalizzazione della matrice con performance decisamente migliori nel caso di esponenti grandi.
Perfetto, ti ringrazio. Stavo dando anche io un'occhiata ad I vari metodi, ma credo che esulino dal corso di informatica che sto seguendo, in quanto é un semplice ELEMENTI DI INFORMATICA per Ing. Meccanica. Sarei piú propenso ad usare il metodo della "moltiplicazione per se stessa". Non riesco peró ad arrivare ad un codice che mi permetta di ripetere l'array del prodotto piú volte. Tu come faresti?
In questo momento stavo provando ad usare la libreria
pow(m[N][N],n)...ma non viene assolutamente (come immaginavo).
pow(m[N][N],n)...ma non viene assolutamente (come immaginavo).
Un ciclo for che si ripeta n-volte, con n scelto dall'utente?
Si, devi inizializzare una matrice uguale all'identità e poi moltiplicare n volte questa matrice per quella di cui devi calcolare la potenza.
aspetta...sei sicuro che moltiplicando n-volte la matrice identitá per quella di cui devo calcolare la Potenza mi dia la matrice elevate alla n?? Io so che moltiplicando una matrice identitá per una matrice, é esattamente uguale a moltilicare per 1 un numero, avendo quindi indietro solamente il numero stesso...
Certo che sono sicuro.. È in pratica la definizione di potenza di una matrice.. Come definisci la potenza di una matrice?
come la matrice per se stessa, come dicevamo prima...peró mi sto confondendo...perché se io facessi:
{{1,2,3},{4,5,6},{7,8,9}}*{{1,0,0},{0,1,0},{0,0,1}}*{{1,0,0},{0,1,0},{0,0,1}} per elevare alla seconda ad esempio, altro non ritroverei che la matrice di partenza
{{1,2,3},{4,5,6},{7,8,9}}*{{1,0,0},{0,1,0},{0,0,1}}*{{1,0,0},{0,1,0},{0,0,1}} per elevare alla seconda ad esempio, altro non ritroverei che la matrice di partenza
Dato un qualsiasi elemento \(a\) di un anello, in questo caso quello delle matrici, definiamo la potenza \(n\)-esima di \(a,\) (\(n \in \mathbb N \)) come l'elemento
\[ a^n = 1 \cdot \underbrace{ a \cdot a \dotsm a \cdot a }_{n \text{ volte}}. \]
Alternativamente puoi non moltiplicare per l'unità e definire separatamente il caso \( a^0. \) Ovviamente puoi anche scrivere la funzione in modo ricorsivo osservando che \( a^n = a \cdot a^{n-1} \) e \( a^0 = 1. \)
\[ a^n = 1 \cdot \underbrace{ a \cdot a \dotsm a \cdot a }_{n \text{ volte}}. \]
Alternativamente puoi non moltiplicare per l'unità e definire separatamente il caso \( a^0. \) Ovviamente puoi anche scrivere la funzione in modo ricorsivo osservando che \( a^n = a \cdot a^{n-1} \) e \( a^0 = 1. \)
ok adesso ho capito. Sto provando da ore a scrivere il codice peró, ancora non riesco, sono riuscito a scrivere la matrice identitá, ma gli altri due sottoprogrammi per la copia e la Potenza non vengono. Puoi dargli un'occhiata?
o meglio...solo quello dell'elevamento a potenza
Se posti il codice vedo cosa c'è di sbagliato...
Amio avviso é nel calcolaPotenza...o nel passaggio dei parametri nel main o proprio nel codice potenza[j]+=m[k]*m[k][j];
_____________________________________________________________________________________________________
_____________________________________________________________________________________________________
#include <iostream>
#include <math.h>
using namespace std;
int const N=3;
int const M=4;
void leggiMatrice(int matrice[N][M]);
void stampaMatrice(int matrice[N][M]);
void calcolaTrasposta(int m[N][M], int t[M][N]);
void calcolaProdotto(int m1[N][M],int m2[M][N], int prodotto[N][N]);
void calcolaPotenza(int m[N][N], int n, int potenza[N][N]);
void unita(int m[N][N]);
void copiaMatrice(int s[N][N], int d[N][N]);
int main(){
int matrice[N][M],trasposta[M][N],prodotto[N][N],copia[N][N],identita[N][N],n,potenza[N][N];
leggiMatrice(matrice);
stampaMatrice(matrice);
calcolaTrasposta(matrice,trasposta);
calcolaProdotto(matrice,trasposta,prodotto);
unita(identita);
copiaMatrice(prodotto,copia);
calcolaPotenza(prodotto,n,potenza);
system("PAUSE");
}
void leggiMatrice(int matrice[N][M]){
cout << "Inserisci la matrice " << N << " X " << M << ": " <<endl;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cin >> matrice[i][j];
}
}
return;
}
void stampaMatrice(int matrice[N][M]){
cout << "La matrice immessa e': " <<endl;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cout << matrice[i][j] << "\t";
}
cout <<endl;
}
return;
}
void calcolaTrasposta(int m[N][M], int t[M][N]){
cout << "La matrice trasposta e': " <<endl;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
t[j][i]=m[i][j]; //scopri perché solo in questo ordine funziona, e non scrivendo "m[i][j]=t[j][i]"
}
}
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cout << t[i][j] << "\t";
}
cout <<endl;
}
return;
}
void calcolaProdotto(int m1[N][M],int m2[M][N], int prodotto[N][N]){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
prodotto[i][j] = 0; // inizializziamo a zero tutti gli elementi della matrice, grazie ai due cicli "for" nidificati
for(int k=0;k<M;k++){ //(spiegazione accurata) qui usiamo un parametro qualsiasi per bloccare una volta la "riga", una volta una "colonna"
prodotto[i][j] += m1[i][k]*m2[k][j]; // usiamo "+=" per andare a sostituire lo "0" con il prodotto riga per colonna
}
}
}
cout << "La matrice prodotto delle due e': " <<endl;
for (int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout << prodotto[i][j] << "\t";
}
cout <<endl;
}
return;
}
void calcolaPotenza(int m[N][N], int n, int potenza[N][N]){
cout << "A che valore vuoi elevare la matrice: ";
cin >> n;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
potenza[i][j]=0; //inizializziamo tutti i valori a zero
for(int ripeti=0;ripeti<n;ripeti++){
for(int k=0;k<N;k++){
potenza[i][j]+=m[i][k]*m[k][j];
}
}
}
}
cout << "L'elevamento alla " << n << " della matrice risulta: " <<endl;
for (int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout << potenza[i][j] << "\t";
}
cout <<endl;
}
return;
}
void unita(int m[N][N]){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(i==j){
m[i][j]=1;
}else{
m[i][j]=0;
}
}
}
cout << "La matrice identita' e': " <<endl;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout << m[i][j] << "\t";
}
cout <<endl;
}
return;
}
void copiaMatrice(int s[N][N], int d[N][N]){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
s[i][j]; //nel "main" qui verranno inseriti i valori del prodotto
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
d[i][j]=s[i][j]; // qui verranno copiati
}
}
}
}
cout << "La matrice copia e': " <<endl;
for (int i=0;i<N;i++){
for(int j=0;j<N;j++){
cout << d[i][j] << "\t";
}
cout <<endl;
}
return;
}
Ma perché stai cercando di implementare il prodotto all'interno di calcolaPotenza? Le funzioni che ti ha fatto scrivere hanno un senso.. Vuole che tu le utilizzi all'interno della funzione per calcolare i prodotti..
ehi aspettate!!!!!! É venuto!!!!!!!!! IT WORKS!!!!!!!
si in effetti ci avevo pensato anche io, é un controsenso....per la fretta ho seguito due strade contemporaneamente (potrei usarlo per scrivere due variant del programma). Come combino il tutto adesso?
P.S. Il programma funziona comunque, ho controllato adesso l'elevamento a Potenza, l'unica cosa é che mi moltiplica tutti I valori per 2...o comunque per il valore n.
P.S. Il programma funziona comunque, ho controllato adesso l'elevamento a Potenza, l'unica cosa é che mi moltiplica tutti I valori per 2...o comunque per il valore n.
Non ho capito che cosa fa.. Ottieni il risultato corretto a meno di un fattore scalare uguale a \(n\)?
Nota che il tuo professore probabilmente si aspetta che tu faccia uso di quelle funzioni e che valuti negativamente il tuo non averlo fatto.. Lo penso principalmente per via della frase "Per una buona organizzazione del codice vanno aggiunti, .." che sembra suggerire che nel corso si desideri anche insegnare qualche nozione base su come si dovrebbe organizzare il codice..
Nota che il tuo professore probabilmente si aspetta che tu faccia uso di quelle funzioni e che valuti negativamente il tuo non averlo fatto.. Lo penso principalmente per via della frase "Per una buona organizzazione del codice vanno aggiunti, .." che sembra suggerire che nel corso si desideri anche insegnare qualche nozione base su come si dovrebbe organizzare il codice..
si si hai assolutamente ragione. Infatti voglio riuscirci anche nel modo da lui richiesto. Useró il codice che ho appena scritto come variante, o soo per mia conoscenza. L'errore praticamente era la moltiplicazione per 2 dei valori della matrice, una volta elevate a Potenza 2 (e quindi di conseguenza per n, in caso di elevamento alla n-esima Potenza qualsiasi). L'ho peró risolto, era un errore off-by one, corretto semplicemente metendo al ciclo for della potenza, la variabile bandiera "ripeti" iniziante da "1"e non da "0".
Comunque chiedevo, come faccio allora ad inserire le due funzioni "unitá" e "copiaMatice"?
Comunque chiedevo, come faccio allora ad inserire le due funzioni "unitá" e "copiaMatice"?
Come scriveresti il codice di elevamente a potenza se fossero dei semplici numeri interi? Se riesci a scrivere questa funzione è sufficiente sostituire i tipi da interi a matrici, l'inizializzazione ad uno con la funzione che crea la matrice identità e il prodotto con la funzione corrispondente.
ma intendi la funzione pow(m[N][N],n)????
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo