no_rain

二分思想在幂中的应用(poj3070)

回想起以前从事ACM活动,每当有一些题目做不出来,总是会去网上找别人的解题报告。可是这些解题报告不是写给人看的:一句dp,二分,线段树,然后直接就贴了代码,而且为了追求效率,这些代码做的优化都很大程度增加了阅读的难度。比如不写函数。
poj3070
这道题的意思是通过矩阵的幂来求Fibonacci数列的第n项,且只要求出它的后4位数。
先贴出我认为写的还是比较清晰的代码:
 1 #include<iostream>
 2 using namespace std;
 3 class matrix{
 4 public:
 5   int a[2][2];
 6   matrix(){
 7     a[0][0]=a[0][1]=a[1][0]=1;
 8     a[1][1]=0;
 9   }
10 };
11 //矩阵的乘法
12 matrix multi(matrix a,matrix b){
13   matrix temp;
14   for(int i = 0; i < 2; i++)
15     for(int j = 0; j < 2; j++){
16       temp.a[i][j] = 0;
17       for(int k = 0; k < 2;k++)
18     temp.a[i][j] += a.a[i][k]*b.a[k][j];
19       if(temp.a[i][j] >= 10000)
20     temp.a[i][j] %= 10000;//注释1
21     }
22   return temp;
23 }
24 //矩阵的n次幂
25 matrix power(int n){
26   matrix temp,s;
27   temp.a[1][0] = temp.a[0][1] = 0;
28   temp.a[1][1] = 1;//把temp化成单位矩阵
29   while(n != 0){
30     if(n & 1)
31       temp = multi(temp,s);
32     n = n >> 1;
33     s = multi(s,s);
34   }
35   return temp;
36 }
37 int main(){
38   int n;
39   while(cin >> n && n != -1){
40     matrix ans = power(n);
41     cout << ans.a[1][0] << endl;
42   }
43 }
44     
45 
46   
47 
注释1:为什么可以在每次乘法的取模呢?这是因为:(a*10000+b)*(c*10000+d),即(a*10000+b)和(c*10000+d)这两个数相乘得到的后四位数是由b,d决定的。那么每次取模也就不影响后四位数了。
在做幂的时候其实体现的就是二分的思想,这可以算是计算机科学中最重要的思想之一了。
其实像我这样的小菜是有多么希望那些牛人可以花点时间把自己对一道题的理解和思路写出来,你可以不必每道题都写出详细的解题报告,但是你可以在那道没有人写详细思路题上花点时间,这样可以帮助到很多人!

posted on 2011-12-28 15:06 is-programmer 阅读(1699) 评论(0)  编辑 收藏 引用


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


导航

<2011年12月>
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

搜索

最新评论

阅读排行榜

评论排行榜