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