HDU3117 Fibonacci Numbers【数学】

题目链接：

​ ​http://acm.hdu.edu.cn/showproblem.php?pid=3117​​

题目大意：

给你一个整数N(0 <= N <= 10^8)，求斐波那契数列第N项F[N]的前四位数字和末尾四位数字。

思路：

斐波那契数列是一个很大的数，直接暴力枚举显然不科学。先考虑末尾4位是否有循环节，写个

程序发现循环节是15000，直接用数组存储前15000的斐波那契数列的末尾4位。至于斐波那契

数列的前4位。通过计算得出N >= 40之后，F[N]就大于8位数了。对于N < 40的部分可以直接

输出结果，对于N >= 40的部分，考虑公式 F[N] =(1/√5) * ( ((1+√5)/2)^n - ((1-√5)/2)^n )。

设F[N]可表示为t * 10^k(t为一个小数)，那么对F[N] = t * 10^k两边分别取对数log10，得到：

log10(F[N]) = log10(t) + k 。log10(t) = log10(F[N]) - k，因为t肯定是小于10的小数，所以，

log10(t) < 1，而且k为整数，那么log10(t)的值就是log10(F[N])去掉整数部分的小数部分。

用pow(10.0，log10(t))求出t。将t*1000取整数部分就得到了F[N]的前4位。

还有一点，求F[N] = (1/√5) * ( ((1+√5)/2)^n - ((1-√5)/2)^n )的时候，因为N>=40的时候，

((1-√5)/2)^n已经是一个非常小的小数(小数点后10位左右)，所以可以直接忽略。这样子，

F[N] ≈ (1/√5) * ((1+√5)/2)^n。log10(F[N])化简为：1/sqrt(5.0) + N*log10(1+(sqrt(5.0))/2.0)。

AC代码：

登录后复制

      
      

       
       #include<iostream>
       
       

       
       #include<algorithm>
       
       

       
       #include<cstdio>
       
       

       
       #include<cstring>
       
       

       
       #include<cmath>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       

       
       int 
       
       f[
       
       15010],
       
       f1[
       
       110];
       
       

       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       f[
       
       0] 
       
       = 
       
       0,
       
       f[
       
       1] 
       
       = 
       
       1;
       
       
    
       
       for(
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       <= 
       
       15001; 
       
       i
       
       ++) 
       
       //保存后四位
       
       
        
       
       f[
       
       i] 
       
       = (
       
       f[
       
       i
       
       -
       
       1] 
       
       + 
       
       f[
       
       i
       
       -
       
       2])
       
       %
       
       10000;
       
       

       
       
    
       
       f1[
       
       0] 
       
       = 
       
       0,
       
       f1[
       
       1] 
       
       = 
       
       1;
       
       
    
       
       for(
       
       int 
       
       i 
       
       = 
       
       2; 
       
       i 
       
       <= 
       
       100; 
       
       ++
       
       i)     
       
       //0~39
       
       
    {
       
       
        
       
       f1[
       
       i] 
       
       = (
       
       f1[
       
       i
       
       -
       
       1] 
       
       + 
       
       f1[
       
       i
       
       -
       
       2]);
       
       
        
       
       if(
       
       f1[
       
       i] 
       
       >= 
       
       100000000)
       
       
        {
       
       
            
       
       break;
       
       
        }
       
       
    }
       
       

       
       
    
       
       int 
       
       N;
       
       
    
       
       while(
       
       cin 
       
       >> 
       
       N)
       
       
    {
       
       
        
       
       if(
       
       N 
       
       <= 
       
       39)
       
       
            
       
       cout 
       
       << 
       
       f1[
       
       N] 
       
       << 
       
       endl;
       
       
        
       
       else
       
       
        {
       
       
            
       
       double 
       
       temp 
       
       = 
       
       log10(
       
       1
       
       /
       
       sqrt(
       
       5.0)) 
       
       + 
       
       N
       
       *
       
       log10((
       
       1
       
       +
       
       sqrt(
       
       5.0))
       
       /
       
       2.0);
       
       
            
       
       temp 
       
       -= (
       
       int)
       
       temp;
       
       
            
       
       temp 
       
       = 
       
       pow(
       
       10.0,
       
       temp);
       
       
            
       
       while(
       
       temp 
       
       < 
       
       1000)
       
       
                
       
       temp 
       
       *= 
       
       10;
       
       
            
       
       int 
       
       ans 
       
       = (
       
       int)
       
       temp;
       
       
            
       
       printf(
       
       "%d...",
       
       ans);
       
       
            
       
       printf(
       
       "%4.4d\n",
       
       f[
       
       N
       
       %
       
       15000]);
       
       
        }
       
       
    }
       
       

       
       

       
       
    
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
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.