斐波那契数列 F(0) =1 还是等于0？

Question

老师你好， 为什么斐波那契数列F(0)在您的教案上面是等于1？实际编程实现却等于0？
在爬楼梯的那道题当中，您说“当有0步台阶时候，我们还有1种可能性，即是没有选择也是一种可能性”？
在您的以下ppt当中，F(0)到底是等于1 还是0？

Answer 1

liuyubobobo 2021-12-22 17:11:50

在这个问题中，F(0) 应该是 1。因为当问到“方法数”的时候，除非不可达，否则永远应该有解（0 表示无法达到。）所以这个 ppt 上的代码不严谨。抱歉。

但实际上，对于这个问题的测试数据，并没有 n = 0 的情况。你可以测试一下，哪怕你的程序中写 n = 0 的时候返回100，也可以得到 ac。或许题目本身也觉得在 0 的地方定义不清，所以在这个地方不做测试。如果是面试的时候遇到这个问题，可以（应该）询问面试官，在 n == 0 的时候是如何定义的（或者没有定义，应该抛异常。）

==========

具体对于数学中的斐波那契数列，f(0) 应该是 0。但这不影响这个问题的解本身依然是斐波那契数列，只不过整个数列向右移了一位。

如果 f(0) = 0, f(1) = 1，则整个数列是：

0 1 1 2 3 5 8 13 21...

如果 f(0) = 1, f(1) = 1，则整个数列是：

1 1 2 3 5 8 21 ....

他们之间就差一个 0。

==========

从更广义的角度讲，只要定义 f(0) = a, f(1) = b，且有 f(n) = f(n - 1) + f(n - 2)，那么我们在交流的时候，就可以说这个数列叫斐波那切数列，只不过起始值不同。

继续加油！：）