沧州做网站哪家好,如何做网站图片,服务器注册,十堰网站整站优化公司FibonacciTime Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d %I64uDescription2007年到来了。经过2006年一年的修炼#xff0c;数学神童zouyu终于把0到100000000的Fibonacci数列 (f[0]0,f[1]1;f[i] f[i-1]f[i-2](i2))的值全部给背了下来。 接…Fibonacci Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d %I64u Description2007年到来了。经过2006年一年的修炼数学神童zouyu终于把0到100000000的Fibonacci数列 (f[0]0,f[1]1;f[i] f[i-1]f[i-2](i2))的值全部给背了下来。 接下来CodeStar决定要考考他于是每问他一个数字他就要把答案说出来不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。 Input 输入若干数字n(0 n 100000000)每个数字一行。读到文件尾。 Output 输出f[n]的前4个数字若不足4个数字就全部输出。 Sample Input0123453536373839 40 Sample Output01123592271493241539086324 1023 【思路】 loga(b^c)c*loga(b),loga(b*c)loga(b)loga(c);假设给出一个数10234432,那么log10(10234432)log10(1.0234432*10^7)log10(1.0234432)7;log10(1.0234432)就是log10(10234432)的小数部分.log10(1.0234432)0.01006374410^0.0100637441.023443198那么要取几位就很明显了吧~先取对数(对10取),然后得到结果的小数部分bit,pow(10.0,bit)以后如果答案还是1000那么就一直乘10。注意偶先处理了0~20项是为了方便处理~这题要利用到数列的公式:an(1/√5) * [((1√5)/2)^n-((1-√5)/2)^n](n1,2,3.....) 取完对数 log10(an)-0.5*log10(5.0)((double)n)*log(f)/log(10.0)log10(1-((1-√5)/(1√5))^n) 其中f(sqrt(5.0)1.0)/2.0;因为log10(1-((1-√5)/(1√5))^n)趋近于0所以可以写成log10(an)-0.5*log10(5.0)((double)n)*log(f)/log(10.0);最后取其小数部分。 AC代码 1 #includeiostream2 #includecmath3 #includecstdio 4 using namespace std;5 const double s (sqrt(5.0)1.0)/2;6 int main()7 {8 int n,i;9 double bit;
10 int fib[21] {0, 1};
11 for(i 2; i 21; i)//小于10000部分提前处理
12 fib[i] fib[i-1] fib[i-2];
13 while(cin n)
14 {
15 if(n 20)
16 { cout fib[n] endl; continue; }
17 else
18 {
19 bit -0.5*log(5.0)/log(10.0)((double)n)*log(s)/log(10.0);//调用公式
20 bit bit - floor(bit);//取小数部分
21 bit pow(10.0,bit);
22 while(bit 1000)//要求四位,所以要将小数点右边的数移到左边直到符合要求
23 bit 10.0 * bit;
24 cout (int)bit endl;
25 }
26 }
27 return 0;
28 } 转载于:https://www.cnblogs.com/123tang/p/6045043.html
