在斐波那契数列中，fib(0)是0还是1？

Question

在斐波那契数列中，fib(0)是0还是1？

53

我正在处理一个题目，其中fib(0)的定义为=1。但那不可能是正确的吧？fib(0)应该是0吧？

Program with fib(0) = 1; spits out fib(4) = 5
Program with fib(0) = 0; spits out fib(3) = 3

正确的定义是什么？

- Algific

这与欧拉计划有关吗？ - oɔɯǝɹ

1

考虑到我们中的任何人都可以更改维基百科页面，我会采用《大英百科全书》上的定义：https://www.britannica.com/science/Fibonacci-number。斐波那契数列从1开始，这是由斐波那契本人定义的。 - Janac Meena

1

你是不是想说“使用 fib(0) = 0 编写的程序输出 fib(4) = 3”？ - Kyle Delaney

10个回答

40

你是正确的。斐波那契数列的正式定义使用种子值fib(0) = 0和fib(1) = 1。这是为了使序列的其余部分正确（而不会偏移一个或其他任何值）。

在数学中，斐波那契数列通常表示为F_n，形成一个序列，称为斐波那契数列，每个数字都是前两个数字的和，从0和1开始。

在数学中，斐波那契数列通常表示为Fn，形成一个序列，称为斐波那契数列，每个数字都是前两个数字的和，从0和1开始。

编辑：我必须承认，还有另一种（非常不常见且通常非正式的）方法通过使用值1和1来定义序列，但这绝不是传统定义中的方式。就像整数序列在线百科全书中所看到的所有正式数学定义一样，它肯定不是首选方法。

- Noldorin

4

换句话说，他的序列偏移了一个索引。 - Markus

@Markus：是的，偏移量非常奇怪。可能只是分配任务的人搞错了（更有可能？）。 - Noldorin

@Sjoerd：我已经做了足够的数学，知道这根本不是标准。 - Noldorin

1

有趣的是，Project Euler 斐波那契数列难题的前提是 fib(0) = 1。 - oɔɯǝɹ

“Incorrect”? 你真的有一套口才，是吗？这是一本百科全书，不管你喜不喜欢。只需检查那里的来源就好了。 - Noldorin

显示剩余3条评论

17

从维基百科的斐波那契数列条目中：

在数学中，斐波那契数列是以下数字序列：

$alt text$

根据定义，斐波那契数列的前两个数字是0和1，而后面每个数字都是前两个数字之和。一些资料省略了最初的0，取而代之的是以两个1开始的序列。

在数学术语中，斐波那契数列Fn由递推关系式定义：

$alt text$

初始值为

$alt text$

- Pascal Thivent

8

强调一下：“某些来源省略了最初的0，而是以两个1开头开始数列”。 - NomeN

在编程中，当进行斐波那契数列的自底向上生成时，f(0)可能会派上用场，因为你需要两个数字来生成第三个数字以及后续的数字。 - Patrick Mutuku

8

http://en.wikipedia.org/wiki/Fibonacci_number

斐波那契本人以1开始序列，而不是0。重要的是要认识到一个人的意见并不是不可改变的事实，考虑到你可能并不比创建这个序列的人更好，这可能是值得的。我认为只要你不像那是唯一绝对正确的做事方式一样，就可以从0开始序列，因为“索引0”处的数字基本上是模棱两可的，并且应该始终明确地传达。

“索引”的问题仅适用于我们，而不适用于斐波那契。因此，如果我们想使用他的起始数字并且我们正在使用基于0的索引，我们将把他的起始数字放在索引0处，或者如果我们正在使用基于1的索引，我们将把他的起始数字放在索引1处。

由于确实可能向左延续序列，因此从0开始也完全是任意的。为什么不从-1开始，然后是-1、1、0、1、1、2……？

- Kyle Delaney

3

我的观点是，如果你认为数字序列的第一项可以是1，并且使用0作为序列的第一个索引，那么说F（0）= 1是有意义的。我还想说的是，有多种方法可以实现这一点，因此最好明确使用哪个版本，而不是坚持只有一种方法。 - Kyle Delaney

1

我怀疑他使用了那些术语。 - Kyle Delaney

1

事情是这样的。 “索引”问题只适用于我们而不适用于他。因此，如果我们想使用他的起始数字并且我们正在使用基于0的索引，我们将把他的起始数字放在索引0处；或者如果我们正在使用基于1的索引，我们将把他的起始数字放在索引1处。 - Kyle Delaney

1

既然你提到了可以继续向左延伸数列，那么从0开始完全是任意的。为什么不从-1开始，然后是-1、1、0、1、1、2……呢？ - Kyle Delaney

1

Kyle，你的回答非常好，你应该将它添加到你上面的回答中。 - codeshot

显示剩余3条评论

7

基于斐波那契数列的定义，可以生成一个封闭的公式来定义第n个元素：

F(n) = ( f^n - (1-f)^n ) / sqrt(5),
where f = (1 + sqrt(5)) / 2 [the golden ratio]

当 n = 0 时，结果显然为 0：

F(0) = (1 - 1) / sqrt(5) = 0.

- Zed

4

那是一个解释，虽然有点绕。实际上，种子才是首要定义它的东西。 - Noldorin

1

无论如何，对于封闭形式肯定没有争议，因此这为问题提供了一个毋庸置疑的答案 =) - Zed

2

@Noldorin 当然你可以定义不同的种子，但是这样很多好的定理就会变成假的了，比如这个。顺便说一下，我的最爱是gcd(F_m, F_n) = F_gcd(m,n)。 - starblue

7

你不能没有兔子而产生一对兔子，原本斐波那契要回答的问题是“从一对兔子开始，在第二个月开始每月繁殖一次，一年可以繁殖多少对兔子”。

- Woody Podgers

这是否意味着fib(0)未定义？清楚地表达这一点会很好。 - codeshot

好知道...谢谢Woody！ - Bravo

我认为其中很大一部分取决于问题的形式。如果你问“第一个斐波那契数是什么fib(1)”，那么你会得到值1。第二个fib(2)是什么，你会得到值1。fib(0)是0，但它不是第一个斐波那契数。这就像问第零个斐波那契数是什么，这基本上是无关紧要的。如果你这样考虑，组合（递归）算法就可以完美地工作了。 C#示例=> int fib(int n){ if (n < 2){ return n; } return fib(n -1) + fib(n-2); } - raddevus

1

踩一下：我同意你不能从空无一物中“生产”兔子（多么丑陋的术语）。但我们在谈论数学，作为一门哲学科学，它是基于想象和定义而非现实的。某些维基百科文章指出：“斐波那契考虑了一个理想化（生物学上不切实际的）兔子种群的增长。”试图将想象中的斐波那契数列与自然动物种群联系起来本来就是冒险的。我猜这只是斐波那契玩的智力游戏。结论：不要试图建立今天仍然存在缺陷的800年前的联系。 - ChristophK

3

他们两个都是正确的。如果你通过递归 G{1}=3，G{2}=5，G{n}=G{n-1}+G{n-2} 指定序列G{n}，那么大多数人都会认为这是“斐波那契数列”。唯一的区别在于前面的几项，但对于任何有趣的关于序列的问题来说，前导项基本上是不相关的。斐波那契数列的核心是加法规则，任何使用该规则的序列都是斐波那契数列。只有在您想要针对特定索引问具体问题时才需要指定是否0在序列中...其他所有内容都只是索引的转换，基本上是不相关的。也就是说，如果问题是“找到序列中第N个值的封闭形式解”，那么用G求解将仅需对解决方案进行微小的移位即可解决F的问题。这个问题的难点对于两个序列都是相同的。

- William Pursell

1

不，这不能被称为斐波那契数列，至少需要加上一个形容词。对于经典或组合斐波那契数列成立的一些恒等式，在一般情况下并不成立。而一些起始条件（例如2 1 3 4 7...卢卡斯序列）则是独立有趣的。 - Dale Gerdemann

0

fib 0 = 0
fib 1 = 1

这是种子值的定义。

- phsiao

6

来源？或者你的声明有其他支持吗？仅仅陈述某件事是如此，并不意味着它就是如此。 - Sjoerd

-1

我的解释是为那些想要简单了解这个系列和零术语的程序员而准备的

从这里开始

first term as    f(1) = 1
second term as   f(2) = f(1)+nothing Available = f(1)+0 = 1+0 =1
third term as    f(3) = f(2)+f(1) = 1+1 = 2

可以合理地认为，负数和零是使用黄金比例的斐波那契公式的结果。

黄金比例（GR）的值为1.618034，公式为f(n) = (GR^n - (1-GR)^n))/sqrt(5)

- aditya vardhan reddy Marreddy

-3

斐波那契数列不是以0开始，而是以1开始。
我们在试图将一个数学概念表示为计算机程序时感到困惑。术语“Fib(0)”是存储第一个斐波那契数（始终为1）的数组索引。我们提出这个问题是因为当有人输入0作为输入时，我们必须从程序中返回一些内容。这个输入实质上意味着生成0个斐波那契数。因此，您可以返回一条消息，说“未生成任何斐波那契数”。

- cavalier

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dale Gerdemann · Accepted Answer

将Fib(0) = 1作为定义称为组合定义，而Fib(0) = 0则是经典定义。这两种定义都在《斐波那契季刊》中使用，不过使用组合定义的作者需要添加一句解释。Benjamin和Quinn在《真正有用的证明》中使用f_n表示第n个组合斐波那契数，F_n表示第n个经典斐波那契数。组合定义对于像“一次可以走一步或者两步，爬上n级台阶有多少种方式”这样的计数问题非常有用。当n为0时，只有一种方法，而不是零种方法。