Implementazione algoritmo fibonacci

[giuliomontenero]

ho dei problemi nell'implementazione di questo algoritmo per risolvere i numeri di fibonacci
vi posto lo pseudocodice e il codice

algoritmo fibonacci(intero n)->intero
M<-(1 0)
      (0 1)
potenzadimatrice(M,n-1)
return M[0][0]

procedura potenzadimatrice(matrice M,intero n)
if(n>1)then
potenzadimatrice(M,n/2)
M<-M*M
if(n è dispari) then M<-M*(1 1)
                                      (1 0)

ecco qui il codice sviluppato da me invece
lo pseudocodice l'ho preso invece dal libro,quindi è esatto, ma avrò sbagliato qualcosa nell'implementazione che non capisco

#include<iostream>
using namespace std;
const int DIM=2;
int A[DIM][DIM]={{1,1},{1,0}};
void potenzaDiMatrice(int M[DIM][DIM],int n)
{
    if(n>1)
    potenzaDiMatrice(M,n/2);
    {
    int i,j,k;
    int somma;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++){
            somma=0;
            for(k=0;k<2;k++)
            somma+=M[i][k]*M[k][j];
            M[i][j]=somma;
        }
    }
    if(n%2!=0)
    {
    int I[DIM][DIM]={{1,1},{1,0}};
    int i,j,k;
    int somma;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++){
            somma=0;
            for(k=0;k<2;k++)
            somma+=M[i][k]*I[k][j];
            M[i][j]=somma;
        }
    }
}
int fibonacci(int n)
{
    int M[DIM][DIM]={{1,0},{0,1}};
    potenzaDiMatrice(M,n-1);
    return M[0][0];
}
int main()
{
    int num=0;
    cout<<"Inserisci un numero maggiore di 0 : ";
    cin>>num;
    cout<<fibonacci(num);
return 0;
}

[vict85]

La matrice A non l'hai più usata e penso che mettere una variabile per memorizzare 2 che è evidentemente una costante che non cambia mai sia inutile. E poi ci metti meno a scrivere 2 che a scrivere DIM... Poi fai come vuoi tu. Al massimo cambiano gli elementi delle matrice ma certo non la sua dimensione.

Comunque semplicemente la matrice M è sbagliata, doveva essere come A. Per esempio vedi qui http://mathworld.wolfram.com/FibonacciQ-Matrix.html

Detto questo la funzione di elevamento a potenza la puoi vedere qui http://en.wikipedia.org/wiki/Exponentiation_by_squaring (il primo), qui http://en.wikipedia.org/wiki/Modular_exponentiation oppure anche su Knuth. Non ho controllato se il tuo è corretto. A mio avviso però è meglio se dividi l'implementazione della moltiplicazione matriciale da quella di calcolo della potenza ennesima. Detto questo Io personalmente memorizzerei la matrice con un più semplice array di 4 elementi.