我可以做些什么来改进我的斐波那契数生成器？
我正在解决这个问题：
G(n) 定义为 G(n) = G(n-1) + f(4n-1) ，对于 n > 0 且 G(0) = 0 f(i) 是第 i 个斐波那契数。给定 n 你需要评估 G(n)以 1000000007 为模。
<前><代码>输入 第一行包含测试用例的数量 t (t<40000)。接下来的每个t行包含整数 n ( 0 <= n < 2^51)。
<前><代码>输出 对于每个测试用例，打印 G(n) 模 1000000007。 例子 输入： 2 2 4 输出： 15 第714章
这是我编写的代码：
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;
}
您能提出任何改进建议吗？
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 tlines 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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
有时此类问题可以通过数学技巧来解决，
而不是暴力解决方案。
在我看来，
n和模的较大值表明存在一个聪明的解决方案。当然，找出解决方案是困难的部分。
（我不确定这对于您的情况是否理想，我只是为您指出另一种方法）
例如，在 计算机编程艺术，第一卷：基本算法
Knuth 使用“生成函数”，这是一种构建封闭形式的巧妙方法
为 Fn 斐波那契数。
有关详细信息，请阅读生成函数 (pdf)
Sometimes such problems can be tackled with mathematical tricks,
instead of brute force solutions.
The large value of
nand modulo, in my opinion, are indications thata 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)
G(n) = G(n-1) + f(4n-1) = G(n-2) + f(4n-1) + f(4n-5) 等等，
因此
G(n) = f(4n) -1) + f(4n-5) + f(4n-9) ... f(3)
f(n) = f(n-1) + f(n-2) = 2f(n-2) + f(n-3) = 3f(n-3) + 2f(n-4) = 5f(n-4) + 3f(n-5)
f(n-5) = 3f(n-8) + 2f(n-9)
因此
f(n) = 5f(n-4) + 9f(n-8) + 6f(n-9)
= 5f(n-4) + 9f(n-8) + 18f(
n-12) + 12f(n-13) = 5f(n-4) + 9f(n-8) + 18f(n-12) + 36f(n-16) + 24f(n-17)
无论如何，很明显系数每次都会加倍。当然，从上面我们可以用 f(n-8) 等来定义 f(n-4) 。不确定这会导致什么结果。
这里有一个级数，f(3)=2 和 f(2) = 1，所以最后您将添加常数。
实际上，出于您的目的，您可以一次计算 f(n)，而不必在此时存储 2 个以上的 f(n)，并且正如您知道上面 G 的公式一样，当您通过计算 f(n) 时，您可以更新当 n 在每个点与 3 mod 4 全等时，G 适当地对斐波那数进行求和。
您将找不到空间来保存具有如此巨大数字（2 的 51 次方）的表，甚至不在磁盘上，尽管它实际上是您需要存储在表中的总和 (f(3), f(3 )+f(7)、f(3)+f(7)+f(11) 等）如果您要保存任何内容。
G(n) = G(n-1) + f(4n-1) = G(n-2) + f(4n-1) + f(4n-5) etc.
therefore
G(n) = f(4n-1) + f(4n-5) + f(4n-9) ... f(3)
f(n) = f(n-1) + f(n-2) = 2f(n-2) + f(n-3) = 3f(n-3) + 2f(n-4) = 5f(n-4) + 3f(n-5)
f(n-5) = 3f(n-8) + 2f(n-9)
thus
f(n) = 5f(n-4) + 9f(n-8) + 6f(n-9)
= 5f(n-4) + 9f(n-8) + 18f(n-12) + 12f(n-13)
= 5f(n-4) + 9f(n-8) + 18f(n-12) + 36f(n-16) + 24f(n-17)
in any case it is clear the coefficients will double each time. Of course from the above we can define f(n-4) in terms of f(n-8) etc. Not sure where this will lead.
There is a series here and f(3)=2 and f(2) = 1 so at the end you will add the constant.
Practically though for your purpose you can calculate f(n) in a single pass without having to store more than 2 of them at this point and as you know the formula for G above, as you pass through calculating f(n) you can update G as appropriate summing the fibonnaci numbers when n is congruent to 3 mod 4 at each point.
You will not find the space to save a table with such a huge number (2 to the power of 51) not even to disk, though it is really the sums you need to store in a table (f(3), f(3)+f(7), f(3)+f(7)+f(11) etc.) if you were going to save anything.
那么f()是斐波那契函数吗？我建议您使用常规递归算法。但是，您可以通过添加缓存来显着提高性能，因为会经常重复调用 f(i) 以获取较小的 i 值。
您可以通过使用静态局部整数数组来做到这一点。如果元素为 0，则表示未命中，因此您需要计算该值并将其存储在数组中。
这样您就可以避免使用浮点运算，并且不会填满堆栈。
So f() is the fibonacci function? I would suggest that you use the regular recursive algorithm. But you can improve performance significantly by adding a cache, as calls to f(i) for smaller values of i will be repeated very often.
You can do that by using a static local array of integers. If the element is 0 it's a miss so you calculate the value and store it in the array.
That way you avoid using floating point operations and you won't fill up the stack.
我认为获取
G(n)值的更好方法是像这样计算它：（对于整个代码，请检查 http://www.ideone.com/jorMy）
尽可能避免递归，这样就不会每次计算斐波那契函数。
编辑：我花了很多时间才找到这一点（我的数学有点生疏），但你也可以像这样编写 val ：（
http://www.ideone.com/H1SYz)
这是您的总和的封闭形式。如果你想自己找到它（毕竟这是家庭作业），请按照 Nick D 的回答。
I think the better way to get value of
G(n)is to compute it like this:(For whole code check http://www.ideone.com/jorMy)
Avoid recursion everywhere it's possible and this way it won't compute everytime Fibonacci function.
Edit: I've spent much time to find that (my math is little rusty), but you can also write val like this:
(code on http://www.ideone.com/H1SYz)
This is closed form of your sum. If you want to find it by yourself (it's homework after all) follow Nick D answer.