題目鏈接

Problem Description

2007年到來了。經過2006年一年的修煉，數學神童zouyu終于把0到100000000的Fibonacci數列(f[0]=0,f[1]=1;f[i] = f[i-1]+f[i-2] (i>=2))的值全部給背了下來。接下來，CodeStar決定要考考他，于是每問他一個數字，他就要把答案說出來，不過有的數字太長了。所以規定超過4位的只要說出前4位就可以了，可是CodeStar自己又記不住。于是他決定編寫一個程序來測驗zouyu說的是否正確。

Input

輸入若干數字n(0 <= n <= 100000000)，每個數字一行。讀到文件尾。

Output

輸出f[n]的前4個數字（若不足4個數字，就全部輸出）。

Sample Input

0
1
2
3
4
5
35
36
37
38
39
40

Sample Output

0
1
1
2
3
5
9227
1493
2415
3908
6324
1023

AC

• 求第n項的斐波那契值，可以用公式和矩陣快速冪，但是這個題讓輸出答案的前4位，只能把所有的值求出來才能得到前四位
• 就用這個公式求第n項
  
• 如果直接套用公式是的話會超時，這里可以兩邊求對數（log10），得到答案的小數部分，然后在求小數對應的10的次方，這樣就得到了原答案除以n個10的結果舉個例子：
  x = 127
  log10(x) = 2.103803720955957
  10的0.103803720955957次方=1.27
  這樣求前4位，只用乘以1000就行
• 先對公式進行化簡，然后取對數
  
• 當n比較小的時候，公式計算不準確，需要把前25項打表出來

#include <iostream> #include <algorithm> #include <stdio.h> #include <vector> #include <map> #include <bitset> #include <set> #include <string.h> #include <cmath> #include <queue> #include <algorithm> #define N 100005 #define P pair<int,int> #define ll long long #define lowbit(a) a&(-a) #define mk(a, b) make_pair(a, b) #define mem(a, b) memset(a, b, sizeof(a)) using namespace std; int f[40]; int main(){ #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout); #endiff[0] = 0;f[1] = 1;for (int i = 2; i <= 20; ++i) {f[i] = f[i - 1] + f[i - 2]; // cout << f[i] << endl;}int n;while (scanf("%d", &n) != EOF) {if (n <= 20)printf("%d\n", f[n]);else {double temp1 = log10(1 / sqrt(5.0));double temp2 = log10((1 + sqrt(5.0)) / 2);double temp = temp1 + n * temp2;double zhi = temp - floor(temp);double ans_x = pow(10, zhi);int ans = ans_x * 1000;printf("%d\n", ans);}}#ifndef ONLINE_JUDGEfclose(stdin);fclose(stdout);system("out.txt"); #endifreturn 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的HDU 1568 Fibonacci的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。