实习时面试面到这个问题,当时还不知道斐波那契数列,讲给同学听时,他说,这不就是斐波那契数列吗?! (尴尬脸)
然后这是我面试的回答:
$total = [0, 1];
for ($i = 2; $i < 100; $i++)
{
$total[] = $total[$i - 1] + $total[$i - 2];
}
今天看到别人(书本)的实现,需要定义几个变量来交换当前值、上一个值,感觉好麻烦。
还有我的代码应该没啥问题吧
1
laoyuan 2017-01-03 16:30:47 +08:00
新年刚开始又来黑 PHP 。。总之不用递归都是好的
|
2
superYy 2017-01-03 16:35:04 +08:00
性能低!应该创建一个缓冲数组存贮之前的值
|
3
misaka19000 2017-01-03 16:36:05 +08:00 via Android
还行,不过不是非得用数组吧
|
4
GPIO 2017-01-03 16:45:20 +08:00
中学学数列的时候都会讲到斐波那契数列的啊,你是不是当时没好好听课。。。
|
6
gisonrg 2017-01-03 17:02:00 +08:00 via iPhone
不用数组只用两个变量可以省空间→_→
|
7
mrgeneral 2017-01-03 17:17:06 +08:00
算法没啥问题啊。
前面的存下来没啥意义, echo 输出了吧,换成俩变量,节省空间。 |
8
SteveLee 2017-01-03 17:26:25 +08:00 via iPhone
矩阵快速 mi
|
9
dtfm 2017-01-03 17:46:16 +08:00 via Android 1
fib 不应该这样么? a, b = b , a+b
|
10
em2046 2017-01-03 17:49:34 +08:00
没毛病
为啥不用递归呢 PS :递归也可以不是 O(2^n) |
11
akira 2017-01-03 18:04:57 +08:00
没问题。只是当 N 比较大的时候,会略尴尬
|
12
q397064399 2017-01-03 18:09:32 +08:00
@em2046 空间复杂度为 O(2^n) 递归过深,直接爆栈,所以才有了 stackoverflow.com
|
13
q397064399 2017-01-03 18:12:10 +08:00
@em2046 递归调用每一次 call ,按照计算机的函数堆栈模型,栈帧要向下延伸,然后栈容量不够用的时候,就直接爆了
|
14
q397064399 2017-01-03 18:13:45 +08:00
一般问菲波那切数列的话,都会接着问 栈溢出的问题,
如果不知道函数递归调用过深导致的爆栈问题,就会略显尴尬了 |
15
loggerhead 2017-01-03 18:18:16 +08:00 6
可以看看我这篇文章——求 Fibonacci 数列的 N 种算法: https://loggerhead.me/posts/qiu-fibonacci-shu-lie-de-n-chong-suan-fa.html
|
16
xjp 2017-01-03 18:25:44 +08:00 via iPhone
没有问题
|
17
assad 2017-01-03 18:25:47 +08:00
import numpy
def mm_fib(n): return (numpy.matrix([[2,1],[1,1]])**(n//2))[0,(n+1)%2] [mm_fib(i) for i in range(20)] |
18
Kilerd 2017-01-03 18:35:11 +08:00
|
19
loggerhead 2017-01-03 18:39:55 +08:00
@Kilerd 文章中有写。比如: 2^8 = 2^4 * 2^4 就只用算一次 2^4 和一次乘法,时间复杂度降到了 O(logn)
|
20
Contextualist 2017-01-03 18:43:08 +08:00 via iPad
@Kilerd 文章中下面的矩阵乘法和代数方法就是“重复平方”(其实就是乘法结合律)的具体实现
|
21
raysonx 2017-01-03 18:45:21 +08:00
话说如果只是要求求出某一个 Fibonacci 数而不是整个数列的话,可以直接用公式在 O(1)的时间内求得。
|
23
SplendentDraco 2017-01-03 19:00:09 +08:00 via Android
我记得高一时上课时无聊吧这玩意儿通项公式求出来了。。😂
|
25
Kilerd 2017-01-03 19:06:41 +08:00
@loggerhead 重复平方,我懂。
@Contextualist @xiaopc GET 到了。 矩阵方法确实神奇。 至于代数方法,感觉是像是把矩阵方法拆开些而已。 完蛋了,现在看博客都专心不了了。 |
26
chuanqirenwu 2017-01-03 19:09:52 +08:00
这个面试比较蛋疼,他是要考察你什么呢?斐波拉契数列的定义?还是高效的代码实现?
|
27
Cbdy 2017-01-03 19:15:37 +08:00
@raysonx 我想了一下没想出来怎么在 O(1)时间内求出来。通项是无理数,比如 n 很大,算出来的精度就很可疑了。有什么好方法吗? O(1)
|
28
blackjar 2017-01-03 19:15:38 +08:00
@q397064399 尾递归打开优化 没区别
|
31
Jakesoft OP @chuanqirenwu 应该是如何实现“后面一个数等于前两个数之和”吧,至于如何高效实现我还需要花点功夫。
|
32
manongvpn 2017-01-03 19:45:22 +08:00
会 Google ,你就离大牛近了一步。
|
33
bdbai 2017-01-03 20:06:04 +08:00 via Android
@loggerhead 弱弱问一下,你的博客文章中矩阵为什么乘在向量的右边?
|
34
CFM880 2017-01-03 20:17:51 +08:00
看下 sicp 里面就有,树形递归和线性迭代,书上讲两种过程的优缺点说的很清楚
|
35
j5shi 2017-01-03 20:21:53 +08:00 via iPhone
@q397064399 这么浅显的问题要是面试官顺着你的思路真的问了那只能恭喜你局面被你控制了😄
|
36
loggerhead 2017-01-03 20:35:47 +08:00
@bdbai 这不是矩阵乘法吗? 1x2 乘以 2x2 的矩阵 = 1x2 的矩阵。你可以看看这个: http://www.ruanyifeng.com/blog/2015/09/matrix-multiplication.html
|
37
owt5008137 2017-01-03 21:09:19 +08:00 via Android
用矩阵,斐波那契的复杂度是 O ( log ( n ))
|
38
ZRS 2017-01-03 21:20:33 +08:00
用通项公式...
|
39
q397064399 2017-01-04 08:15:44 +08:00
@j5shi 我会说很多程序员 并不知道 程序堆栈这回事么?
|
40
longhao 2017-01-04 09:21:56 +08:00 via iPhone
@q397064399 尝试尾递归呢
|
41
q397064399 2017-01-04 09:31:07 +08:00
@longhao 主要看汇编层面的优化吧,毕竟生成机器码,底层是怎么运作的,高级语言很难解释清楚
一般是不推荐使用过深的递归, |
42
MayLava 2017-01-04 11:03:30 +08:00
说到斐波那契数列,大家肯定记得“生兔子问题”。题目很绕。
一只小兔子,出生三个月变大兔子,变成大兔子后每个月生一只小兔子; 小兔子三个月后也能变成大兔子开始生小兔子。 问 n 个月后一共有几只兔子。 我完全被搞蒙了——这尼玛什么鬼。 我还觉得这题目有歧义啊,比如说长成大兔子的当月就能生小兔子吗还是下个月才能生小兔子。 你想啊,这个月长成大兔子,难道不需要怀胎一个月吗? 然后生兔子我们是不是按一半男一半女算?两只兔子一个月生一只才对吧? 然后我还在想兔子真的繁殖能力这么强吗? 然后我画了一下午“生兔子”的图。 然后我还用了各种奇怪的方法模拟兔子成长过程什么的,总之这题没写出来。 后来才知道这就是斐波那契数列。迭代 a, b = b, a + b 就行了。 然后我就觉得,要考斐波那契就老老实实的说你要考斐波那契,我会就是会,不会我就学。 求你不要搞些奇奇怪怪的描述来忽悠人了😂😂😂😂 |
43
bdbai 2017-01-04 18:22:32 +08:00 via Android
@loggerhead 按照阮老师的写法,变换矩阵乘在向量左边的,高中数学书上也这么写......
|
44
loggerhead 2017-01-04 19:58:03 +08:00
@bdbai 没搞懂你什么意思……矩阵乘法不满足交换律的,所以如果我写反了,那么我就写错了,但是我仔细看了看,好像没问题啊……
|
45
bdbai 2017-01-04 20:23:01 +08:00 via Android
@loggerhead 抱歉我看错了,原来是横着写的😂
|
46
loggerhead 2017-01-04 21:44:02 +08:00 1
@bdbai 哈哈😂
|