Implementazione algoritmo fibonacci

di il
1 risposte

Implementazione algoritmo fibonacci

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;
}

1 Risposte

  • Re: Implementazione algoritmo fibonacci

    Non ho mai visto un algoritmo di Fibonacci che abbia un costo computazionale di n^3. Riguarda completamente il tuo codice
    Saluti
    Danilo
Devi accedere o registrarti per scrivere nel forum
1 risposte