关键词：
【中文标题】如何求解：f(n) = f(n-1) + 3*f(n-2) + 3*f(n-3) + f(n-4)【英文标题】：how to solve: f(n) = f(n-1) + 3*f(n-2) + 3*f(n-3) + f(n-4) 【发布时间】：2014-11-02 05:42:49 【问题描述】：我该如何解决
f(n) = f(n-1) + 3*f(n-2) + 3*f(n-3) + f(n-4) maximum value of n = 10^18 minimum is 1
initial conditions are
f(1) = 1
f(2) = 3
f(3) = 3
f(4) = 1
f(n) 什么时候可以很大？ print f(n) modulus 10000007
我对这个问题的尝试如下 （使用模数可能会出错）
1st test case:
3
2
5
9
output:
3
20
695
(working fine)
2nd tst case:
3
1554894
5959595
2562651
output:
7505501
9551828
6592801
(working fine)
但是对于更大的数字，程序会失败；为什么？
#!/usr/bin/python
T = int(raw_input())
def fib_iter(n):
if n == 1:
return 1
if n == 2:
return 3
if n == 3:
return 3
if n == 4:
return 1
prev1, prev2, prev3, prev4 = 1, 3, 3, 1
i = 5
while i < n+1:
curr = (prev1%10000007 + 3*prev2%10000007 + 3*prev3%10000007 + prev4%10000007)%10000007
prev1, prev2, prev3, prev4 = prev2%10000007, prev3%10000007, prev4%10000007, curr%10000007
i = i + 1
return curr%10000007
for t in xrange(T):
n = int(raw_input())
print fib_iter(n)
【问题讨论】：
您是否考虑过查看 google codejam 提交的解决方案？ 这个问题似乎是题外话，因为它是一个“我可以危害 codez plz”的问题 ideone.com/qHudOC 我已经嵌入了我当前程序的链接......当输入很大（比如 10000000）并且给出错误的答案时，程序在执行过程中需要很长时间......但也给出了错误的答案 我建议您编写一个新问题，其中包含您的代码并说明您遇到的具体问题。简单地询问如何编写代码而没有其他任何事情不会得到有用的答案。 【参考方案1】：阅读this book，然后手工解决。
编辑： 当我被要求提供更多细节时：通过“求解”，我的意思是推导出一个直接给出系数 f(n) 的显式公式 [这样就没有递归必要的]。对于正常的斐波那契数列，这由比内公式给出。按照链接书中的食谱，您可以通过以下步骤完成：
导出第 n 个系数的生成函数。基本上，这是通过考虑一个函数来完成的，该函数在所寻求的系数 f(n) 方面具有幂级数展开，并将这几个项组合成一个函数。
给定生成函数，推导出单项式x^n前面的膨胀系数。由于您指定的生成函数最多包含四阶多项式，因此甚至可以通过解析来完成。
如果这里有一些数学模式，我会提供更多数学细节，如果运气好的话，我也会提供解决方案。但是就这样试试吧，它很简单，而且这本书可读性很好。
【讨论】：
虽然书籍推荐似乎不太适合这个网站，但似乎只能通过数学来解决【参考方案2】：更新 - 尝试将循环中的这两行更改为：
curr = (prev1 + 3*prev2 + 3*prev3 + prev4)%10000007
prev1, prev2, prev3, prev4 = curr, prev1, prev2, prev3
模数为 10000007，n = 15616511848，你应该得到 5370032，正如你提到的。请注意，10000007 = 941 x 10627 并且不是素数。我不确定为什么选择它。通常这些类型的问题使用 1000000007 (7 + 10^9) 这是一个素数。
加速这个算法更多的是一个数学问题，而不是一个编程问题。其矩阵形式为：
| 1 3 3 1 |
a = | 1 0 0 0 |
| 0 1 0 0 |
| 0 0 1 0 |
| 1 |
x[4] = | 3 |
| 3 |
| 1 |
x[i+1] = a x[i]
x[i+j] = a^j x[i]
可以使用重复平方来加快计算 a^j 的速度。
如果您对没有模数的 x[0] 到 x[4] 感到好奇。对于模数，将模数 (10000007) 添加到负数：
x[0] = -14, 39, -73, 117
x[1] = 1, -14, 39, -73
x[2] = 3, 1, -14, 39
x[3] = 3, 3, 1, -14
x[4] = 1, 3, 3, 1
【讨论】：
【参考方案3】：使用矩阵方法，执行变得非常快速和可靠。 http://x-perienceo.blogspot.in/
【讨论】：
【参考方案4】：我写了一个更详细的答案here。
重要的是要知道 1000007 是 素数。因此，您可以使用欧拉定理。欧拉定理指出，对于素数 p，a**x % p == a**y % p（Python 表示法）如果 x % (p-1) == y % (p-1)。
尝试找到一个矩阵符号来计算任何 n 的 f(n)，而无需首先递归地计算 f(n-1) 等等。然后通过平方使用取幂来计算它（直到你的模，如上面 1. 中所述）。
【讨论】：
在这种情况下，使用的是 10000007，它不是素数，所以欧拉定理不适用，但这个问题不需要它，即使在对矩阵求平方时也是如此。 谢谢！！我已经使用矩阵方法解决了这个问题..非常快！！！ x-perienceo.blogspot.in矩阵幂求解骨牌覆盖数(soj3021)(代码片段)
...Tiling题意：给出$4 imesN$的矩形以及尺寸为$2 imes1$的骨牌，求解该矩形能被骨牌覆盖的种数。分析：起初我自己一直尝试推导出一个递推式，但是一直没有成功。后来看了网上别人给的递推式：$f(n)=f(n-1)+5*f(n-2)+f(n-3)-f(n-4)$，有了这... 查看详情
递归算法的特性
...递归算法是一种分而治之，把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是有效地。2递归算法的时间效率低本回答被提问者采纳 参考技术B递推定义递推算法是一种简单的算法，即通过... 查看详情
递归的感悟
...计算过程，令n=4调用这个函数，用下面的形式来表示递归求解的过程：（1）F(4)=4×F(3)‘n=4调用函数过程F(3)（2）F(3)=3×F(2)‘n=3调用函数过程F(2)（3）F(2 查看详情
递归小记(代码片段)
...循环推理。递归的基本法则：基准情形，不用递归就可以求解 不断推进，递归调用总能向着一个基准情形前进 设计法则，假设所有递归调用都能运行 合成效益法则，求解一个... 查看详情
高数偏微分题求解
f(xy,x/y)=x,求[af(x,y)/ax]+[af(x,y)/ay]=?你这根本不对这个题要用复合函数求导公式算：记m=xy,n=x/y，那么有：∂m/∂x=y∂m/∂y=x∂n/∂x=1/y∂n/∂y=-x/y²对于f(m,n)=x就有（记A=∂f/∂m，B=∂f/∂n）：∂... 查看详情
初赛知识点相关
...###Catalan数公式1：$f(n)=sum_i=0^n-1f(i) imesf(n-1-i)$,其中$f(0)=1$如何去理解这个公式？我们可以~~感性地~~把这个化为一个二叉树状态方案问题。当n=1的时候显然方案数为1,即f(1)=1当n=2的时候，有以下情况左边sz|右边sz|总方案|---|---|---|1|0|... 查看详情
9.变态跳台阶(代码片段)
...关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:f(1)=1f(2)=f(2-1)+f(2-2) //f(2-2)表示2阶一次跳2阶的次数。f(3)=f(3-1)+f(3-2)+f(3-3) ...f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-(n-1))+f(n-n) 说明： 1）这里的f(n)代表的... 查看详情
斐波那契数列的公式是啥
斐波那契数列：1，1，2，3，5，8，13，21……如果设F(n)为该数列的第n项(n∈N+)。那么这句话可以写成如下形式：F(1)=F(2)=1,F(n)=F(n-1)+F(n-2)(n≥3)显然这是一个线性递推数列。通项公式的推导方法一：利用特征方程线性递推数列的特征... 查看详情
动态规划1——01背包详解(代码片段)
...f(1)=1;n=2时，f(2)=f(0)+f(1)；n=3时，f(2)=f(1)+f(2)；以此类推…求解f(n)。最早，我们可能在课本上学过，这是个经典的递归问题，于是，能很很快写出递归的代码：publicintfib(intN)if(N==0) 查看详情
动态规划1——01背包详解(代码片段)
...f(1)=1;n=2时，f(2)=f(0)+f(1)；n=3时，f(2)=f(1)+f(2)；以此类推…求解f(n)。最早，我们可能在课本上学过，这是个经典的递归问题，于是，能很很快写出递归的代码：publicintfib(intN)if(N==0) 查看详情
斐波那契数列性质
1.$F(1)+F(2)+F(3)+...+F(n)=F(n+2)-1$2.$F(1)^2+F(2)^2+F(3)^2+...+F(n)^2=F(n)F(n+1)$3.$F(1)+F(3)+F(5)+...+F(2n-1)=F(2n)$4.$F(2)+F(4)+F(6)+...+F(2n)=F(2n+1)-1$5.$F(n)=F(m)F(n-m+1)+F(m-1)F(n-m)$ $(n\gem) 查看详情
青蛙跳台阶
...青蛙跳上一个n级的台阶总共有多少种跳法。解答：假设f(n)是n个台阶跳的次数。f(1)=1f(2)会有两个跳得方式，一次1阶或者2阶，这回归到了问题f(1),f(2)=f(2-1)+f(2-2)f(3)会有三种跳得方式，1阶、2阶、3阶，那么就是第一次跳出1阶后面... 查看详情
具体数学-1
...移动一个圆盘。问：(n)层的汉诺塔要移动多少次？命名并求解：设(f(n))表示(n)层汉诺塔所需的步数。递归的本质思想就是把问题的一部分看做“黑匣子”：当我们需要移动(n)层汉诺塔时，这里红色的代表一片，黑色的就是“黑匣... 查看详情
一个数的因子个数求解公式
对于任何一个自然数$N$，都可以分解质因子得到如下形式：\[N=p_1^e_1*p_2^e_2*p_3^e_3*\cdots*p_k^e_k\] 那么，$N$的因子的个数为：$f(n)=(1+e_1)*(1+e_2)*\cdots*(1+e_k)$。 如$N=100$，分解质因子变形为：$100=2^2*5^2$，$N$的因子的个数为：$... 查看详情
关于矩阵快速幂的用法总结qwq
...觉得解释得真的贼好QwQ特别便于理解QwQ然后直接进正题,如何构造矩阵很容易能发现我们是从f[n-1],f[n-2],f[n-3]推出f[n],f[n-1],f[n-2],那我们就可以做出这样一个东西f[n-1] f[n]f[n-2]×T= f[n-1]f[n-3] f[n-2]然后!如果我们... 查看详情
蓝桥杯算法提高递推求值
题目如下：问题描述 已知递推公式： F(n,1)=F(n-1,2)+2F(n-3,1)+5, F(n,2)=F(n-1,1)+3F(n-3,1)+2F(n-3,2)+3. 初始值为：F(1,1)=2,F(1,2)=3,F(2,1)=1,F(2,2)=4,F(3,1)=6,F(3,2)=5。 输入n，输出F(n,1)和F(n,2)，由于答案可能很大，你只需要输出答案... 查看详情
变态跳台阶
解题思路1.由上题跳台阶思路得f(n)=f(n-1)+f(n-2)+f(n-3)+.....+f(n-n),同时得f(n-1)=f(n-2)+f(n-3)+....+f(n-n);2.由1得f(n)=f(n-1)+f(n-1)=2*f(n-1);3.f(n-x)代表的是最后一次跳x个台阶的跳法种类数题目描述一只青蛙一次可以跳上1级台阶，也可以跳上2级…... 查看详情
hdu5950
题意：t组，输入n,a,b;f(1)=a;f(2)=b;求f(n);f(n)=f(n-1)+2*f(n-2)+n^4;思路：肯定是矩阵快速幂啦，(n+1)^4=n^4+4n^3+6n^2+4n+1,所以为7*7的矩阵，{1,n,n^2,n^3,n^4,f(n),f(n-1)}*A={1,(n+1)^2,(n+2)^3,(n+1)^4,f(n+1),f(n)},1#include<iostre 查看详情