fibonacci - フィボナッチ数列で、fib(0) は 0 か 1 か?

Question

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

正しい定義は何ですか?

Answer 1

Fib(0) = 1 の定義は組み合わせ定義と呼ばれ、Fib(0) = 0 は古典的な定義です。どちらもFibonacci Quarterlyで使用されていますが、組み合わせ定義を使用する著者は説明文を追加する必要があります。Benjamin と Quinn は、Proofs that Really Count で、n 番目の組み合わせフィボナッチ数に f_n を使用し、n 番目の古典的なフィボナッチ数に F_n を使用します。組合せ論的定義は適切で、「一度に 1 歩または 2 歩ずつ歩いて n 歩の階段を上る方法は何通りあるか」のような質問を数えるのには驚くことではありません。n が 0 の場合、それを行う方法は 1 つであり、方法は 0 ではありません。

Answer 2

あなたは正しいです。フィボナッチ数列は、シード値fib(0) = 0とで正式に定義されますfib(1) = 1。これは、シーケンスの残りの部分が正しい (そして 1 つまたは何かオフセットされない) ための要件です。

数学では、一般に F_n と呼ばれるフィボナッチ数は、フィボナッチ数列と呼ばれる数列を形成します。各数は、0 と 1 から始まる 2 つの前の数の合計です。

数学では、一般に Fn と呼ばれるフィボナッチ数は、フィボナッチ数列と呼ばれる数列を形成し、各数は 0 と 1 から始まる 2 つの前の数の合計になります。

編集：値1と1をシードしてシーケンスを定義する別の（あまり一般的ではなく、通常は非公式な）方法があることを認めなければなりませんが、これは決して従来の方法ではありません。The On-Line Encyclopaedia of Integer Sequences のように、私が見たすべての正式な数学的定義では確かに好まれていません。

Answer 3

ウィキペディアのフィボナッチ数のエントリから:

数学では、フィボナッチ数は次の数列です。

定義により、最初の 2 つのフィボナッチ数は 0 と 1 であり、残りの各数は前の 2 つの合計です。一部のソースでは、最初の 0 が省略され、代わりに 2 つの 1 でシーケンスが開始されます。

数学的に言えば、フィボナッチ数列 Fn は再帰関係によって定義されます。

シード値付き

Answer 4

フィボナッチ数列の定義に基づいて、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.

Answer 5

どちらも正しいです。再帰 G{1} = 3、G{2} = 5、G{n} = G{ n - 1} + G{ n - 2} によってシーケンス G{n} を指定すると、ほとんどの人はそれに同意するでしょう。 「フィボナッチ数列」です。唯一の違いは先頭にあるいくつかの用語ですが、主要な用語はシーケンスに関する興味深い質問にはほとんど関係ありません。フィボナッチ数列の核心は加算規則であり、その規則を使用するすべての数列がフィボナッチ数列です。特定のインデックスについて特定の質問をしたい場合は、シーケンスに 0 が含まれているかどうかを指定するだけで済みます...他のすべてのものはインデックスの単なる翻訳であり、ほとんど無関係です。つまり、問題が「シーケンスの N 番目の値の閉形式解を見つける」である場合、それを G について解くと、F の問題は解の些細なシフトだけで解けます。問題の難しい部分は、両方のシーケンスで同じです。

Answer 6

fib 0 = 0
fib 1 = 1

それがシード値の定義です。