我是这么实现斐波那契数列的

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2868 天前的主题，其中的信息可能已经有所发展或是发生改变。

实习时面试面到这个问题，当时还不知道斐波那契数列，讲给同学听时，他说，这不就是斐波那契数列吗？！ (尴尬脸）

然后这是我面试的回答:

$total = [0, 1];

for ($i = 2; $i < 100; $i++)
{
	$total[] = $total[$i - 1] + $total[$i - 2];
}

今天看到别人（书本）的实现，需要定义几个变量来交换当前值、上一个值，感觉好麻烦。

还有我的代码应该没啥问题吧

第 1 条附言 · 2017-01-03 19:51:17 +08:00

感谢大家提供的不同的思路和看法，本来只是一个秀代码的帖子，竟然引发了诸多讨论。

我没有怎么在意内存消耗、时间复杂度的问题，看来这方面确实还需要学习一个啊。

@loggerhead 的文章让我大开眼界，谢谢！

total

斐波那契

面试

PHP

48 条回复 • 2017-01-05 11:24:28 +08:00

laoyuan

2017-01-03 16:30:47 +08:00

新年刚开始又来黑 PHP 。。总之不用递归都是好的

superYy

2017-01-03 16:35:04 +08:00

性能低！应该创建一个缓冲数组存贮之前的值

misaka19000

2017-01-03 16:36:05 +08:00 via Android

还行，不过不是非得用数组吧

GPIO

2017-01-03 16:45:20 +08:00

中学学数列的时候都会讲到斐波那契数列的啊，你是不是当时没好好听课。。。

superYy

2017-01-03 16:48:49 +08:00

@superYy 没仔细看，之前说错了

gisonrg

2017-01-03 17:02:00 +08:00 via iPhone

不用数组只用两个变量可以省空间→_→

mrgeneral

2017-01-03 17:17:06 +08:00

算法没啥问题啊。

前面的存下来没啥意义， echo 输出了吧，换成俩变量，节省空间。

SteveLee

2017-01-03 17:26:25 +08:00 via iPhone

矩阵快速 mi

dtfm

2017-01-03 17:46:16 +08:00 via Android

fib 不应该这样么？ a, b = b , a+b

em2046

2017-01-03 17:49:34 +08:00

没毛病
为啥不用递归呢
PS ：递归也可以不是 O(2^n)

akira

2017-01-03 18:04:57 +08:00

没问题。只是当 N 比较大的时候，会略尴尬

q397064399

2017-01-03 18:09:32 +08:00

@em2046 空间复杂度为 O(2^n) 递归过深，直接爆栈，所以才有了 stackoverflow.com

q397064399

2017-01-03 18:12:10 +08:00

@em2046 递归调用每一次 call ，按照计算机的函数堆栈模型，栈帧要向下延伸，然后栈容量不够用的时候，就直接爆了

q397064399

2017-01-03 18:13:45 +08:00

一般问菲波那切数列的话，都会接着问栈溢出的问题，
如果不知道函数递归调用过深导致的爆栈问题，就会略显尴尬了

loggerhead

2017-01-03 18:18:16 +08:00

可以看看我这篇文章——求 Fibonacci 数列的 N 种算法： https://loggerhead.me/posts/qiu-fibonacci-shu-lie-de-n-chong-suan-fa.html

xjp

2017-01-03 18:25:44 +08:00 via iPhone

没有问题

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)]

Kilerd

2017-01-03 18:35:11 +08:00

@loggerhead

> 重复平方技术也可以用在求 Fibonacci 数上。

可行吗？？我想了一下，好像没有什么思路。求指点。

loggerhead

2017-01-03 18:39:55 +08:00

@Kilerd 文章中有写。比如： 2^8 = 2^4 * 2^4 就只用算一次 2^4 和一次乘法，时间复杂度降到了 O(logn)

Contextualist

2017-01-03 18:43:08 +08:00 via iPad

@Kilerd 文章中下面的矩阵乘法和代数方法就是“重复平方”（其实就是乘法结合律）的具体实现

raysonx

2017-01-03 18:45:21 +08:00

话说如果只是要求求出某一个 Fibonacci 数而不是整个数列的话，可以直接用公式在 O(1)的时间内求得。

xiaopc

2017-01-03 18:58:05 +08:00 via Android

@Kilerd 线性递推先构造出矩阵，然后用矩阵乘法结合律降次

SplendentDraco

2017-01-03 19:00:09 +08:00 via Android

我记得高一时上课时无聊吧这玩意儿通项公式求出来了。。😂

choury

2017-01-03 19:02:57 +08:00

@raysonx 公式里面全是无理数，计算机直接算不好吧

Kilerd

2017-01-03 19:06:41 +08:00

@loggerhead 重复平方，我懂。

@Contextualist @xiaopc GET 到了。矩阵方法确实神奇。至于代数方法，感觉是像是把矩阵方法拆开些而已。

完蛋了，现在看博客都专心不了了。

chuanqirenwu

2017-01-03 19:09:52 +08:00

这个面试比较蛋疼，他是要考察你什么呢？斐波拉契数列的定义？还是高效的代码实现？

Cbdy

2017-01-03 19:15:37 +08:00

@raysonx 我想了一下没想出来怎么在 O(1)时间内求出来。通项是无理数，比如 n 很大，算出来的精度就很可疑了。有什么好方法吗？ O(1)

blackjar

2017-01-03 19:15:38 +08:00

@q397064399 尾递归打开优化没区别

Jakesoft

2017-01-03 19:38:30 +08:00

@GPIO 可能是忘记了吧，不过大学确实很少上课。。。

h4x3rotab

2017-01-03 19:40:01 +08:00 via iPhone

@Cbdy 快速矩阵幂， O(logn)

Jakesoft

2017-01-03 19:42:18 +08:00

@chuanqirenwu 应该是如何实现“后面一个数等于前两个数之和”吧，至于如何高效实现我还需要花点功夫。

manongvpn

2017-01-03 19:45:22 +08:00

会 Google ，你就离大牛近了一步。

bdbai

2017-01-03 20:06:04 +08:00 via Android

@loggerhead 弱弱问一下，你的博客文章中矩阵为什么乘在向量的右边？

CFM880

2017-01-03 20:17:51 +08:00

看下 sicp 里面就有，树形递归和线性迭代，书上讲两种过程的优缺点说的很清楚

j5shi

2017-01-03 20:21:53 +08:00 via iPhone

@q397064399 这么浅显的问题要是面试官顺着你的思路真的问了那只能恭喜你局面被你控制了😄

loggerhead

2017-01-03 20:35:47 +08:00

@bdbai 这不是矩阵乘法吗？ 1x2 乘以 2x2 的矩阵 = 1x2 的矩阵。你可以看看这个： http://www.ruanyifeng.com/blog/2015/09/matrix-multiplication.html

owt5008137

2017-01-03 21:09:19 +08:00 via Android

用矩阵，斐波那契的复杂度是 O （ log （ n ））

ZRS

2017-01-03 21:20:33 +08:00

用通项公式...

q397064399

2017-01-04 08:15:44 +08:00

@j5shi 我会说很多程序员并不知道程序堆栈这回事么？

longhao

2017-01-04 09:21:56 +08:00 via iPhone

@q397064399 尝试尾递归呢

q397064399

2017-01-04 09:31:07 +08:00

@longhao 主要看汇编层面的优化吧，毕竟生成机器码，底层是怎么运作的，高级语言很难解释清楚
一般是不推荐使用过深的递归，

MayLava

2017-01-04 11:03:30 +08:00

说到斐波那契数列，大家肯定记得“生兔子问题”。题目很绕。

一只小兔子，出生三个月变大兔子，变成大兔子后每个月生一只小兔子；
小兔子三个月后也能变成大兔子开始生小兔子。
问 n 个月后一共有几只兔子。

我完全被搞蒙了——这尼玛什么鬼。
我还觉得这题目有歧义啊，比如说长成大兔子的当月就能生小兔子吗还是下个月才能生小兔子。
你想啊，这个月长成大兔子，难道不需要怀胎一个月吗？
然后生兔子我们是不是按一半男一半女算？两只兔子一个月生一只才对吧？
然后我还在想兔子真的繁殖能力这么强吗？

然后我画了一下午“生兔子”的图。
然后我还用了各种奇怪的方法模拟兔子成长过程什么的，总之这题没写出来。

后来才知道这就是斐波那契数列。迭代 a, b = b, a + b 就行了。
然后我就觉得，要考斐波那契就老老实实的说你要考斐波那契，我会就是会，不会我就学。
求你不要搞些奇奇怪怪的描述来忽悠人了😂😂😂😂

bdbai

2017-01-04 18:22:32 +08:00 via Android

@loggerhead 按照阮老师的写法，变换矩阵乘在向量左边的，高中数学书上也这么写......

loggerhead

2017-01-04 19:58:03 +08:00

@bdbai 没搞懂你什么意思……矩阵乘法不满足交换律的，所以如果我写反了，那么我就写错了，但是我仔细看了看，好像没问题啊……

bdbai

2017-01-04 20:23:01 +08:00 via Android

@loggerhead 抱歉我看错了，原来是横着写的😂

loggerhead

2017-01-04 21:44:02 +08:00

@bdbai 哈哈😂

yzhen123

2017-01-05 08:53:53 +08:00

@MayLava 这种题目考察的是语言理解能力，这么简单的描述都没看懂，以后读产品经理的需求怎么办？（手动滑稽

ryd994

2017-01-05 11:24:28 +08:00

@blackjar fib 要求 n-1 和 n-2 ，不是尾递归
如果是存在尾递归，则必然可以重写为循环，因为编译器就是这么干的