bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

pku 3070
题目要求计算Fibonacci数列的第n项最后4位。因为n可以很大(0 ≤ n ≤ 1,000,000,000)。因此直接计算在时限内是不可能的(有多个case)。题目还给出了计算的方法:表示成矩阵连乘的形式为



这就给我们提供了快速算法,因为矩阵相乘满足结合律。预先计算上面一个矩阵的2的幂次方,再将n表示成2进制。如当n=5时,只需计算一次矩阵乘法:1次方乘以4次方。当n=1000000000时最多只需计算29次矩阵乘法2^29 = 536870912),而且由于矩阵只是2阶,计算量大大减少。
// pku 3070 求fabonacci数列的快速算法
/*

    化为以下矩阵连乘的形式
    |F(n+1) F(n)  | |1 1|(n)
    |F(n)   F(n-1)|=|1 0| 
    将n表示成2进制, 矩阵的二进制的积可以预先保存
    只需计算结果的后4位
*/
#include 
<iostream>

using namespace std;

int m[31][4]; // 保存29个2阶矩阵
long fact[31];// 2的k次方

void cal()
{
    
// 单位矩阵
    
//m[0][0]=1,m[0][1]=0,m[0][2]=0,m[0][3]=1;
    m[1][0]=1,m[1][1]=1,m[1][2]=1,m[1][3]=0;
    
//fact[0]=1;
    fact[1]=1;
    
for(int i=2;i<=30;i++)
    {
        m[i][
0]=(m[i-1][0]*m[i-1][0]+m[i-1][1]*m[i-1][2])%10000;
        m[i][
1]=(m[i-1][0]*m[i-1][1]+m[i-1][1]*m[i-1][3])%10000;
        m[i][
2]=(m[i-1][2]*m[i-1][0]+m[i-1][3]*m[i-1][2])%10000;
        m[i][
3]=(m[i-1][2]*m[i-1][1]+m[i-1][3]*m[i-1][3])%10000;
        fact[i]
=2*fact[i-1];
    }
}

void solve(long n)
{
    
// 对n表示成2进制
    int e[31];
    memset(e,
0,sizeof(e));
    
int i,j;
    
for(i=30;i>=1;i--)
    {
        
if(n>=fact[i])
        {
            e[i]
=1;
            n
-=fact[i];
        }
    }
    
//for(i=1;i<=30;i++) printf("%d\n",e[i]);
    
//  结果矩阵,初始时为单位矩阵
    int res[4]={1,0,0,1},tmp[4];
    
for(i=1;i<=30;i++)
    {
        
if(e[i]!=0)
        {
            tmp[
0]=(res[0]*m[i][0]+res[1]*m[i][2])%10000;
            tmp[
1]=(res[0]*m[i][1]+res[1]*m[i][3])%10000;
            tmp[
2]=(res[2]*m[i][0]+res[3]*m[i][2])%10000;
            tmp[
3]=(res[2]*m[i][1]+res[3]*m[i][3])%10000;
            
for(j=0;j<4;j++) res[j]=tmp[j];
        }
    }
    printf(
"%d\n",res[1]);
}

int main()
{
    cal();
    
long n;
    
while(scanf("%ld",&n) && n>=0)
    {
        solve(n);
    }
    
return 1;
}
posted on 2008-02-29 00:04 bon 阅读(592) 评论(2)  编辑 收藏 引用

Feedback

# re: pku 3070 2008-11-10 20:34 Zeor
方法不错额~~~  回复  更多评论
  

# re: pku 3070 2009-04-16 11:37 bear
学习下,哇哈哈  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Google PageRank 
Checker - Page Rank Calculator