当前位置:首页 > 资讯 > info6 > 正文

斐波那契数的皮萨诺周期

发表于: 2016-11-30   作者:caozhankui   来源:转载   浏览:
摘要: 斐波那契数的皮萨诺周期fibonacci数为f0=0,f1=1,fi=f(i-1)+f(i-2)pisanoperiod指的是一个序列对n取模后的周期fibonacci的周期性明显可见对2取模结果为:0110110110110110fibonacci对3取模结果为:0112022101120221此性质在用于计算超大fibonacci数时非常有用,以下为数个例子fibonacci序列之和的最低位首

斐波那契数的皮萨诺周期

  • fibonacci数为f0=0, f1=1, fi = f(i-1)+f(i-2)
  • pisano period指的是一个序列对n取模后的周期
  • fibonacci的周期性明显可见
    • 对2取模结果为:0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
    • fibonacci对3取模结果为:0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1
  • 此性质在用于计算超大fibonacci数时非常有用,以下为数个例子

fibonacci序列之和的最低位

  • 首先计算出模10的pisano period,再根据周期性求解

    int pisano(long long n, long long m, vector<long long>& v){
        long long a = 0;
        long long b  = 1;
    
        v.push_back(0);
        v.push_back(1);
        for (int i = 2; i <= n; ++i) {
            long long t = b;
            b = a + b;
            a = t;
            b %= m;
    
            v.push_back(b);
    
            if(i & 1 == 1){
                int r = (i >> 1) + 1;
                int j = 0, k = r;
    
                /* for(auto e:v)
                    cout << e << ' ';
                cout << endl; */
    
                for(; k <= i; j++, k++){
                    if(v[j] != v[k])
                        break;
                }
                //cout << k << ' ' << i << endl;
                if(k == i+1)
                    return r;
            }
        }
        return 0;
    }
    
    
    long long fibonacci_sum_best(long long n) {
        if (n <= 1)
            return n;
    
        vector<long long>v;
        int p = pisano(n, 10, v);
        // for(auto e:v)
            // cout << e << ' ';
        // cout << endl;
    
        // cout << "get pisano " << n << " " << p << endl;
    
        if(p == 0)
            return accumulate(v.begin(), v.end(), 0) % 10;
        else{
            int period_sum = accumulate(v.begin(), v.end(), 0) % 10;
            int c = n / p;
            int sum = accumulate(v.begin(), v.begin() + (n % p) + 1, 0) + period_sum * c;
            return sum % 10;
        }
    }
    

作者Focustc,来自于 CSDN

斐波那契数的皮萨诺周期

编辑推荐
 众所周知斐波那契数在数学和计算机中有着广泛的应用 斐波那契数的原理是第一个数是 1,第二个
问题描述:斐波那契数列是指如下数列: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2).数列的前10个数如下: 0,
这个学期开了一门叫算法的课,为了今天的ITAT复赛,这两天研究了一下这门课。感觉算法真的是太
斐波那契数计算的方法一般采用递归的方法,返回类型一般采用int或者long类型。在这种条件下会产生两
骨牌铺方格 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) T
问题及代码: /* *Copyright (c) 2016,烟台大学计算机学院 *All rights reserved. *文件名称:main.
一写在前面的话 二普通版 三改进版 四动态规划版 一、写在前面的话 在csdn上看到一篇博客,博客的内
斐波那契数列是犹如0、1、1、2、3、5、8、·····、fn这样的数,从前书本上一般介绍的方法都是递归的
在计算机科学中,斐波那契堆是由树的集合所组成的堆数据结构。它比二项堆的平摊运行时间更好。斐波
斐波纳契堆(Fibonacci Heap)于 1984 年由 Michael L. Fredman 与 Robert E. Tarjan 提出,1987 年
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号