斐波那契数列问题大家都知道。https://www.zhihu.com/question/28062458/answer/39763094


关于求其第N项的值。尤其是当N很大很大比如N=10000000000时求其值。本来之前同学在群里说面试的时候问过,然后大家普遍说的解法可能是大数之类的。当时搜了一下,只有https://www.zhihu.com/question/23582123/answer/40464211    这篇文章提到了用快速矩阵幂的方法做。但是当时也么有细看。因为没有Java的代码。。。。。。。。。。。。。。。然后就是报名了学校第11届算法设计竞赛,其中第F题 http://code.bupt.edu.cn/problem/contest/650/problem/F/

  类似斐波那契,不过通项公式稍有变化,并且其中N的范围竟然是从0到10000000000【100亿】,当时就蒙蔽了。这他么也太大了啊!!!!!递归肯定不行啊!!!!!然后想到了用下面这种已经是比较好的方法了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;
   
public class Main {
    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            long n = scanner.nextLong();
               System.out.println(fibonacci(n));
        }
    }
    public static int fibonacci(long n){
        if(n <= 1){
            return 1;
        }
        long n1 = 1, n2 = 1, sn = 0;
        for(int i = 0; i <=n - 2; i ++){
            sn = (3*n1 + 2*n2)%1000000007;
            n1 = n2;
            n2 = sn;
        }
        return (int)sn;
    }  
}

但是,还是因为N太特么大了,算9位数的时候还能算出来,但到了10位数的时候就算不出来了。很显然还有其他的更高效的算法。于是就想到了之前看的这个快速矩阵幂的算法。

这是百度百科关于快速矩阵幂的介绍:http://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E5%B9%82?fr=aladdin

https://www.zhihu.com/question/28062458/answer/39763094 提到了怎么把斐波那契问题转换为用矩阵幂的计算。大家可以看看。

然后我就直接上Java代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.Date;
import java.util.Scanner;
 
public class buptf1_1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        ////矩阵ma就是根据通项写出来的
        long[][] ma = { { 11 }, { 10 } };
        while (in.hasNext()) {
            long c = in.nextLong();
            long start = new Date().getTime();
            ////第三个参数可根据题目要求有没有第0项做相应变化
            System.out.println(calculate(ma, c - 1));
            System.out.println("time=" + (new Date().getTime() - start) + "ms");
        }
    }
 
    public static int calculate(long[][] ma, long c) {
        if (c < 0) {
            return 1;
        }
        /////对比整数的快速幂对应操作,此处用个单位矩阵相乘
        long[][] cp = { { 10 }, { 01 } };
        while (c > 0) {
            if ((c & 1) == 1) {
                multiDoubleMatrix(cp, ma);
            }
            multiMatrix(ma);
            c = c >> 1;
        }
        ////因为初始值f1=1,f0=1;所以乘的时候就相当于之前求出的矩阵的这两项想加了
        return (int) (cp[0][0] + cp[0][1]) % 1000000007;
    }
 
    public static void multiMatrix(long[][] ma) {
        ////ma*ma。相当于整数求幂的那个base*base
        int i, j;
        long[][] temp = { { 00 }, { 00 } };
        for (i = 0; i < 2; i++) {
            for (j = 0; j < 2; j++) {
                temp[i][j] = ((ma[i][0] * ma[0][j]) % 1000000007 + (ma[i][1] * ma[1][j]) % 1000000007) % 1000000007;
            }
            // printf("\n");
        }
        for (i = 0; i < 2; i++) {
            for (j = 0; j < 2; j++) {
                ma[i][j] = temp[i][j];
            }
        }
        // long[][] ret={{0,0},{0,0}};
        // int i=ma.length;
        // int j=ma[0].length;
        // int k=ma.length;
    }
 
    public static void multiDoubleMatrix(long[][] cp, long[][] ma) {
        ////cp*ma
        long[][] temp1 = { { 00 }, { 00 } };
//      int i, j;
//      for (i = 0; i < 2; i++) {
//          for (j = 0; j < 2; j++) {
//              temp[i][j] = ((cp[i][0] * ma[0][j]) + (cp[i][1] * ma[1][j])) % 1000000007;
//          }
//      }
//      for (i = 0; i < 2; i++) {
//          for (j = 0; j < 2; j++) {
//              cp[i][j] = temp[i][j];
//          }
//      }
        int i,j,k,temp;
        for(i=0;i<cp.length;i++){
            for(j=0;j<ma[0].length;j++){
                temp=0;
                for(k=0;k<cp[0].length;k++){
                    temp+=cp[i][k]*ma[k][j];
                    temp%=1000000007;
                }
                temp1[i][j]=temp;
            }
        }
        for (i = 0; i < 2; i++) {
            for (j = 0; j < 2; j++) {
                cp[i][j] = temp1[i][j];
            }
        }
    }
}