s******7 发帖数: 1758 | 1 要求不用recursion和iterative求fibonacci
听完就放弃了说数学没那么好,后来忘了问答案
求这里高人求解 |
E*****m 发帖数: 25615 | |
P****i 发帖数: 12972 | 3 F_n = \frac{psi^n-{-psi}^{-n}}{\sqrt{5}}
psi=\frac{1+\sqrt{5}}{2}
【在 s******7 的大作中提到】 : 要求不用recursion和iterative求fibonacci : 听完就放弃了说数学没那么好,后来忘了问答案 : 求这里高人求解
|
z*********8 发帖数: 2070 | 4 这是故意刁难吧, 考数学不考CS
【在 s******7 的大作中提到】 : 要求不用recursion和iterative求fibonacci : 听完就放弃了说数学没那么好,后来忘了问答案 : 求这里高人求解
|
s******7 发帖数: 1758 | 5 多谢上面的解答
看了一下,应该就是用近似公式
是个老白,估计丫是数学出来的想显吧一下 |
s***5 发帖数: 2136 | 6 这是高中数学,数列题,刁难啥?
【在 z*********8 的大作中提到】 : 这是故意刁难吧, 考数学不考CS
|
z*********8 发帖数: 2070 | 7 和CS有什么关系? 怎么不考茴有几种写法?
【在 s***5 的大作中提到】 : 这是高中数学,数列题,刁难啥?
|
s***5 发帖数: 2136 | 8 考智商行不?还有,用这种方法才能实现O(lgn)算法。
【在 z*********8 的大作中提到】 : 和CS有什么关系? 怎么不考茴有几种写法?
|
s******7 发帖数: 1758 | 9 倒,都用近似公式了,要个妹的lgn, 老兄你说的跟我问的是一个问题吗,要不你去看
看二楼的wiki连接,那个公式要当场能推出来,我看高中生估计是奥赛出来的
【在 s***5 的大作中提到】 : 考智商行不?还有,用这种方法才能实现O(lgn)算法。
|
t****t 发帖数: 387 | |
|
|
t**********h 发帖数: 2273 | |
e***s 发帖数: 799 | 12 就算是用矩阵的解法也用递归吧,只是O(logn)而已。 |
g****o 发帖数: 547 | 13 这个是正解
如果是c++ 很可能是考你template
【在 t****t 的大作中提到】 : 用template metaprogramming : http://stackoverflow.com/questions/908256/getting-template-meta
|
l*****t 发帖数: 2019 | 14 跪的好,这个傻B公司的傻B面官。爆名字,让丫以后找不到工作。
【在 s******7 的大作中提到】 : 要求不用recursion和iterative求fibonacci : 听完就放弃了说数学没那么好,后来忘了问答案 : 求这里高人求解
|
d****n 发帖数: 397 | 15 当场也可以推出来的吧,那个closed form formula又不难。
【在 s******7 的大作中提到】 : 倒,都用近似公式了,要个妹的lgn, 老兄你说的跟我问的是一个问题吗,要不你去看 : 看二楼的wiki连接,那个公式要当场能推出来,我看高中生估计是奥赛出来的
|
B*****g 发帖数: 34098 | 16 最近流行,前不久刚有人问了?
【在 s******7 的大作中提到】 : 要求不用recursion和iterative求fibonacci : 听完就放弃了说数学没那么好,后来忘了问答案 : 求这里高人求解
|
q********c 发帖数: 1774 | 17 我才他是想让你用DP解。
【在 s******7 的大作中提到】 : 要求不用recursion和iterative求fibonacci : 听完就放弃了说数学没那么好,后来忘了问答案 : 求这里高人求解
|
n*******k 发帖数: 100 | 18 这是考线性代数还是编程啊?当场很不容易想到
F(k+2) = F(k+1) + F(k)
F(k+1) = F(k+1)
F(k+2) = 1 1 * F(k+1)
F(k+1) 1 0 F(k)
求Eigenvector和Eigenvalue
A = 1 1 ak =(F(k+2),F(k+1))^T a0 = (F1,F0)T = (1,0)^T
1 0
ak = A^k*a0
F(k) = 1/sqrt(5) [ ( 0.5 + sqrt(5)/2)^k - (0.5 - sqrt(5)/2)^k ) ]
然后k 分奇数或偶数的情况,就可以取半,O(log(n)). |
s***e 发帖数: 403 | |
w**s 发帖数: 339 | 20 通项公式都写出来了。为什么是O(logN)不是O(1). |
n*******k 发帖数: 100 | 21 ( 0.5 + sqrt(5)/2)^k k次方的关系,如果直接硬算还是O(k)。
1--> 2 --> 4 --> 8
k==8 时,
log(8) = 3,其实只要做3次乘法就可以了。
奇数稍微麻烦点。 偶数+1的方法来做,但是还是能保证O(log(k))
【在 w**s 的大作中提到】 : 通项公式都写出来了。为什么是O(logN)不是O(1).
|
c********p 发帖数: 1969 | 22 我在这里问过
【在 B*****g 的大作中提到】 : 最近流行,前不久刚有人问了?
|