我可以做什么来改善我的斐波纳契数生成器？ [英] What can I do to improve my Fibonacci number generator?

问题描述

我解决这个问题：

  G（n）定义为
 
 G（n）= G（n-1）+ f（4n-1），对于n> 0 
 
和G（0）= 0 
 
 f（i）是第斐波纳契数。给定n你需要评估G（n）
  

模数1000000007。

 输入
 
第一行包含测试用例的数量t（t <40000）。每个下一个t 
  

行包含整数n（0 <= n <
2 ^ 51）。

 输出
 
对于每个测试用例打印G（n）modulo 1000000007 。
 
示例
 
输入：
 2 
 2 
 4 
 
 
 $ b b输出：
 
 
 15 
 714 
  

这是我写的代码：

  typedef long long type; 
 #define check 1000000007 
 type x; 
类型y; 
 
 type f（type n）
 {
 return（ceil（（pow（1.618，n）-pow（-0.618，n））/（（sqrt * 1.0））））; 
} 
类型val（类型n）
 {
 if（n == 0）
 return 0; 
 else 
 return（val（n-1）+ f（4 * n-1）） 
} 
 int main（）
 {
 cin>> x; 
 while（x--）
 {
 cin>> y; 
 cout<<< val（y）％check<< endl; 
} 
 // getch（）; 
 return 0;你可以建议任何改进吗？
有时这些问题可以用数学技巧处理，
 
而不是暴力解决方案。
 
 
 
在我看来， n 和模数的值很大，表示
 
a聪明的解决方案存在。当然，找出解决方案是很困难的部分。
 
 
 
（我不知道如果这是理想的情况下，我只是指向一个替代方法） 
 
 
 
例如，在电脑艺术编程，第1卷：基本算法 
 
 Knuth使用生成函数，一种构建封闭形式的聪明方法
 
用于Fn斐波纳契数字。
 
 
 
有关详情，请参阅生成函数（pdf ） 
 
 
为什么要关心序列的
生成函数？ 
有几个答案，但是这里是
一：如果我们可以找到一个生成
函数的序列，那么我们可以
经常找到一个闭合形式为nth 
 coef fi cient-这可以漂亮
有用！例如，
的封闭形式x b（x-x  2 ）
幂系列中x  n 的系数b $ b将是
 nth斐波纳契数的显式公式。 [...] 
 
 
 
I'm solving this problem:

G(n) is defined as

G(n) = G(n-1) + f(4n-1) , for n > 0

and G(0) = 0

f(i) is ith Fibonacci number. Given n you need to evaluate G(n)
modulo 1000000007.
Input

First line contains number of test cases t (t<40000). Each of the next t
lines contain an integer n ( 0 <= n <
  2^51).
Output

For each test case print G(n) modulo 1000000007.

Example

Input:
2
2
4



Output:


15
714

This is the code I've written:
typedef long long type;
#define check 1000000007
type x;
type y;

type f(type n)
{
    return(ceil((pow(1.618,n) - pow(-0.618,n))/((sqrt(5)*1.0))));
}
type val(type n)
{
    if(n==0)
    return 0;
    else 
    return (val(n-1)+f(4*n-1));
}
int main()
{
    cin>>x;
    while(x--)
    {
       cin>>y;
       cout<<val(y)%check<<endl;
       }
    //getch();
    return 0;
}
Can you suggest any improvements?
解决方案
Sometimes such problems can be tackled with mathematical tricks,

instead of brute force solutions.

The large value of n and modulo, in my opinion, are indications that

a clever solution exists. Of course figuring out the solution is the hard part.

(I'm not sure if this is ideal in your case, I'm only pointing you an alternative way)

For example, in the Art of Computer Programming, Volume 1: Fundamental Algorithms

Knuth uses "generating functions", a clever way for constructing a closed form

for the Fn fibonacci number.

For more info read Generating Functions (pdf)

  
Why should one care about the
  generating function for a sequence?
  There are several answers, but here is
  one: if we can find a generating
  function for a sequence, then we can
  often find a closed form for the nth
  coefficient— which can be pretty
  useful! For example, a closed form for
  the coefficient of xn in the
  power series for x/(1−x−x2)
  would be an explicit formula for the
  nth Fibonacci number. [...]


                        
这篇关于我可以做什么来改善我的斐波纳契数生成器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！