P*i
3 楼
F_n = \frac{psi^n-{-psi}^{-n}}{\sqrt{5}}
psi=\frac{1+\sqrt{5}}{2}
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
psi=\frac{1+\sqrt{5}}{2}
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
z*8
4 楼
这是故意刁难吧， 考数学不考CS
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
s*7
5 楼
多谢上面的解答
看了一下，应该就是用近似公式
是个老白，估计丫是数学出来的想显吧一下
看了一下，应该就是用近似公式
是个老白，估计丫是数学出来的想显吧一下
s*5
6 楼
这是高中数学，数列题，刁难啥？
【在 z*********8 的大作中提到】
: 这是故意刁难吧， 考数学不考CS
【在 z*********8 的大作中提到】
: 这是故意刁难吧， 考数学不考CS
z*8
7 楼
和CS有什么关系？ 怎么不考茴有几种写法？
【在 s***5 的大作中提到】
: 这是高中数学，数列题，刁难啥？
【在 s***5 的大作中提到】
: 这是高中数学，数列题，刁难啥？
s*5
8 楼
考智商行不？还有，用这种方法才能实现O(lgn)算法。
【在 z*********8 的大作中提到】
: 和CS有什么关系？ 怎么不考茴有几种写法？
【在 z*********8 的大作中提到】
: 和CS有什么关系？ 怎么不考茴有几种写法？
s*7
9 楼
倒，都用近似公式了，要个妹的lgn, 老兄你说的跟我问的是一个问题吗，要不你去看
看二楼的wiki连接，那个公式要当场能推出来，我看高中生估计是奥赛出来的
【在 s***5 的大作中提到】
: 考智商行不？还有，用这种方法才能实现O(lgn)算法。
看二楼的wiki连接，那个公式要当场能推出来，我看高中生估计是奥赛出来的
【在 s***5 的大作中提到】
: 考智商行不？还有，用这种方法才能实现O(lgn)算法。
t*t
10 楼
用template metaprogramming
http://stackoverflow.com/questions/908256/getting-template-meta
http://stackoverflow.com/questions/908256/getting-template-meta
t*h
11 楼
e*s
12 楼
就算是用矩阵的解法也用递归吧，只是O(logn)而已。
g*o
13 楼
这个是正解
如果是c++ 很可能是考你template
【在 t****t 的大作中提到】
: 用template metaprogramming
: http://stackoverflow.com/questions/908256/getting-template-meta
如果是c++ 很可能是考你template
【在 t****t 的大作中提到】
: 用template metaprogramming
: http://stackoverflow.com/questions/908256/getting-template-meta
l*t
14 楼
跪的好，这个傻B公司的傻B面官。爆名字，让丫以后找不到工作。
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
d*n
15 楼
当场也可以推出来的吧，那个closed form formula又不难。
【在 s******7 的大作中提到】
: 倒，都用近似公式了，要个妹的lgn, 老兄你说的跟我问的是一个问题吗，要不你去看
: 看二楼的wiki连接，那个公式要当场能推出来，我看高中生估计是奥赛出来的
【在 s******7 的大作中提到】
: 倒，都用近似公式了，要个妹的lgn, 老兄你说的跟我问的是一个问题吗，要不你去看
: 看二楼的wiki连接，那个公式要当场能推出来，我看高中生估计是奥赛出来的
B*g
16 楼
最近流行，前不久刚有人问了？
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
q*c
17 楼
我才他是想让你用DP解。
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
【在 s******7 的大作中提到】
: 要求不用recursion和iterative求fibonacci
: 听完就放弃了说数学没那么好，后来忘了问答案
: 求这里高人求解
n*k
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)).
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
19 楼
用矩阵幂。
w*s
20 楼
通项公式都写出来了。为什么是O(logN)不是O(1).
n*k
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).
1--> 2 --> 4 --> 8
k==8 时，
log(8) = 3，其实只要做3次乘法就可以了。
奇数稍微麻烦点。 偶数+1的方法来做，但是还是能保证O(log(k))
【在 w**s 的大作中提到】
: 通项公式都写出来了。为什么是O(logN)不是O(1).
c*p
22 楼
我在这里问过
【在 B*****g 的大作中提到】
: 最近流行，前不久刚有人问了？
【在 B*****g 的大作中提到】
: 最近流行，前不久刚有人问了？
相关阅读
求问GG狗家的Cloud infra组微软冷冻期多久？remote contractor好还是不好现在leetcode哪些题可以刷啊报个NVIDIA的offer看到那些每周领免费福利的人公司有人收到H1B的notice了种族斗争可以借鉴阶级成分划分，华人划到黑五类王艮为什么不自己开公司？为啥发了个intern的opening被删了？做了将近10年backend，转去做Android怎么样？中国五大最顶级圈子 这里是社会精英俱乐部老印搶功LinkedIn全球注册用户超过5亿请问寄钱回国怎么又快又便宜？G 面经一点心得 给还在弯区煎熬却找不到工作的SDN startup Big Switch Networks are hiring电面冷冻期多久?背景调查请教