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 的大作中提到】
: 最近流行，前不久刚有人问了？
|
