大自然中的斐波那契数列,股市中的斐波那契数列

文章目录斐波那契数列问题1求斐波那契数列第n项数列递推式数列通项式斐波那契数列的若干性质循环节

斐波那契数列问题1求斐波那契数列的第n项

51nod1242斐波那契数列的第n项

数列递推公式F 0=0，f1=1fn=fn1fn2f_0=0，f _1=1 newlinef _ n=f _ { n-1 } f _ { n-2 } F0=0，f1=1fn=fn1

a=[f(n1 ) f ) n )0]=[f )1]

F ( 0 ) 0 0 ] [ 1 1 1 0 ] n − 1 A=\ begin{bmatrix} F(n+1)&F(n)\ 0&0 end{bmatrix}= begin{bmatrix} F(1)&F(0)\ 0&0 end{bmatrix} begin{bmatrix} 1&1\ 1&0 end{bmatrix}^{n-1} A=[F(n+1)0​F(n)0​]=[F(1)0​F(0)0​][11​10​]n−1

struct Matrix{int n,m;#define maxn 10LL a[maxn][maxn];Matrix(int n = 2,int m = 2):n(n),m(m){};};Matrix m1(2,2),m2(2,2);Matrix Mutiply(const Matrix &a,const Matrix &b){Matrix c;assert(a.m == b.n );for(int i = 1;i <= a.n; ++i){for(int j = 1;j <= b.m; ++j){c.a[i][j] =0;for(int k = 1;k <= a.m; ++k){c.a[i][j] =(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;// a.a[i][k]*b.a[]}}}return c;}int main(void){ LL n;cin>>n; m1.a[1][1] = 1; m1.a[1][2] = 0; m2.a[1][1] = 1; m2.a[1][2] = 1; m2.a[2][1] = 1; if(n == 0) puts("0"); else{ n--; while(n > 0){ if(n&1) m1 = Mutiply(m1,m2); n >>= 1; m2 = Mutiply(m2,m2); } cout<<m1.a[1][1]<<endl; } return 0;} 数列的通项公式

在模意义下的 ( 5 ) sqrt(5) ( ​5)有两个解 383008016 , 616991993 383008016 ,616991993 383008016,616991993
所以这种方法要求解存在，比较局限

LL sqr5 = 383008016;int main(void){ LL n;cin>>n;LL a = (1+sqr5)*qpow(2,mod-2)%mod;LL b = (1-sqr5+mod)%mod*qpow(2,mod-2)%mod;cout<<1ll*qpow(sqr5,mod-2)*(qpow(a,n)-qpow(b,n)+mod)%mod; return 0;}/*sqrt(5)383008016616991993*/

求解通项的方法 有待补充

斐波那契数列的一些性质 g c d ( F ( a ) , F ( b ) ) = F ( g c d ( a , b ) ) gcd(F(a),F(b)) = F(gcd(a,b)) gcd(F(a),F(b))=F(gcd(a,b))
循环节

类斐波那契数列的循环节
A The power of Fibonacci