注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

Modular Fibonacci  

2009-04-23 16:55:14|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

The Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...) are defined by the recurrence:

F0 = 0
F1 = 1
Fi = Fi-1 + Fi-2 for i>1

Write a program which calculates Mn = Fn mod 2m for given pair of n and m. 0<=n<=2147483647 and 0<=m<20. Note that a mod b gives the remainder when a is divided by b.
Input and Output

Input consists of several lines specifying a pair of n and m. Output should be corresponding Mn, one per line.
Sample Input

11 7
11 6

Sample Output

89
25

Arun Kishore

 

题目大意:给定n和m求斐波那契数列第n项的值模2的m次方后的值

主要思想:由于给定的n可能很大,所以采用一般的递归方法不仅时间上面会很耗时而且很容易爆栈。如果采用公式法由于精度的原因也可能会出错。所以在这里采用矩阵的方法来求解F[n],具体算法分析见我的上一篇日志斐波那契(Fibonacci)数列

代码如下:

#include<iostream>
using namespace std;
struct Matrix{
    unsigned long long i,j,k,h;
};
void MatrixMul(Matrix &result,Matrix m);    //实现矩阵的乘法result*m,并把结果保存到result中
unsigned long long a[20];          //保存2的次方
int main(){
    int n,m;
    Matrix A,result;
    int i;
    for(i=0;i<20;i++){
        if(i==0)a[i]=1;
        else a[i]=a[i-1]*2;
    }
    while(cin>>n>>m){
        A.i=A.j=A.k=1;
        A.h=0;                            //A为上篇中提到的矩阵
        result.i=result.h=1;        //result保存每次的运算结果,初始化为单位矩阵
        result.j=result.k=0;
        while(n){
            if(n&1){
                MatrixMul(result,A);
            }
            MatrixMul(A,A);
            n>>=1;
        }
        cout<<(result.j)%a[m]<<endl;
    }
}
void MatrixMul(Matrix &result,Matrix m){
    Matrix temp;
    temp.i=result.i*m.i+result.j*m.k;
    temp.j=result.i*m.j+result.j*m.h;
    temp.k=result.k*m.i+result.h*m.k;
    temp.h=result.k*m.j+result.h*m.h;
    result.i=temp.i;
    result.j=temp.j;
    result.k=temp.k;
    result.h=temp.h;
}

后记:这里由于n的取值可能非常大,导致F[n]会很大,int型和long long型都会溢出。所以选用unsigned long long,也可以在矩阵相乘的时候就取余。

  评论这张
 
阅读(341)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017