Java プログラマーがフィボナッチ数について知っておくべきこと

特に外資系企業では、面接中にアルゴリズムについて質問されることがよくありますが、ストレスの多い状況で必死に何かを思い出すのは必ずしも簡単ではありません。したがって、準備する必要があります。まず、少なくとも基本的なアルゴリズムの記憶をリフレッシュしてください。今日は、フィボナッチ数などの現象と、それに関連する問題の最も一般的なバリエーションを分析します。 フィボナッチ数は、 0 と 1 で始まる一連の自然数であり、後続の各数値は前の 2 つの数値の合計に等しくなります。 F = {0、1、1、2、3、5、8、13、21、34、55、...}
F ₀ = 0、F ₁ = 1、F _n = F _{n - 1} + F _{n - 2} ;
n ≥ 0、n ∈ Z

場合によっては 0 が省略され、系列が 1 1 2 3... で始まることに注意してください。原則として、問題の条件では、系列が最初の 2 つの数字 (0.1 または 1.1) で始まることがすぐに指定されます。したがって、両方の場合の解決策をさらに検討していきます。

Javaで最初のn個のフィボナッチ数を取得する

最初の n 個のフィボナッチ数を取得するタスクがあるとします。

ケース0.1:

特定の数 n が得られます。
```
int[] arr = new int[n];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i < arr.length; ++i) {
  arr[i] = arr[i - 1] + arr[i - 2];
}
```
サイズ n の配列を作成します。最初の 2 つの要素は 0 と 1 に等しく、残りの要素はこのループを通過し、配列の前の数値を使用することによって取得されます。

そして、次のように表示します。
```
for (int i = 0; i < arr.length; ++i) {
  System.out.println(arr[i]);
}
```
int n = 10 を設定します。

そして、次の結果が得られます。
```
0
1
1
2
3
5
8
13
21
34
```
ケース 1.1 の場合、解決策は実際には変わりません。
```
int[] arr = new int[n];
arr[0] = 1;
arr[1] = 1;
for (int i = 2; i < arr.length; ++i) {
  arr[i] = arr[i - 1] + arr[i - 2];
}
```
変更する必要があるのは、配列 arr[0]: の最初の要素を 0 から 1 にすることだけです。したがって、最初の 10 要素は次のようになります。
```
1
1
2
3
5
8
13
21
34
55
```

ストリーム経由の最初の n 個のフィボナッチ数

しかし、私たちは自分たちのレベルを示したいと思っています。それでは、 stream を使用してこのソリューションがどのようになるかを見てみましょう。

0.1の場合:
```
Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
   .limit(n)
   .map(y -> y[0])
   .forEach(x -> System.out.println(x));
```
Streamクラスの静的 iterate メソッドは、関数を初期配列 arr に適用することによって作成された無限順序付けストリームを返します。この場合、機能は、前の配列に基づいて、新しい配列をそれぞれ構成するためのルールを設定することです。結果として、配列のストリームを取得します。
```
{0,1}
{1,1}
{1, 2}
{2, 3}
{3, 5}
{5, 8}
{8, 13}
{13, 21}
{21, 34}
{34, 55}
…..
```
しかし、その数は無限であるため、.limit(n) を使用して要素の数を最初の n (この場合は 10) に減らします。

ただし、配列のストリームは必要ないので、 .map(y -> y[0]) を使用して各配列の最初の要素を選択し、必要な数値を含むストリームを取得し、forEach を使用してコンソールに出力します。。

見た目も涼しくなりましたね。
最初の要素が 1,1 である場合、このコードもほぼ同じになります。
```
Stream.iterate(new int[]{1, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(y -> y[0])
     .forEach(x -> System.out.println(x));
```
ここでも、違いは最初の要素にあります。{0, 1} の代わりに {1, 1} を設定します。

実際には、結果は前の例と同じになります。

フィボナッチ数の和

n 番目の要素までのフィボナッチ数の合計を取得するように求められた場合はどうなるでしょうか? これで何の問題も生じるはずはありません。ストリームを使用してソリューションを取得し、forEach を他のいくつかのメソッドに置き換えてみましょう。

0.1の場合:

int n = 10;
int result = Stream.iterate(new int[]{0, 1}, arr -> new int[]{arr[1], arr[0]+ arr[1]})
     .limit(n)
     .map(t -> t[0])
     .mapToInt(Integer::intValue)
     .sum();
System.out.println(result);

.mapToInt(Integer::intValue) を使用してストリームを数値 IntStream に変換し、その .sum() メソッドを使用してすべての要素の合計を取得します。

初期要素が 1,1 の場合、{0, 1} の代わりに {1, 1} を設定します。

フィボナッチ数列の n 番目の数値を取得する

場合によっては、一連の数値ではなく、具体的にはフィボナッチ数列の n 番目の数値を出力するよう求められることがあります。原則として、以前のソリューションを簡単に適用できるため、これによりタスクが簡単になるだけです。では、再帰によって問題を解決するのはどうでしょうか?

0.1の場合:
```
public int getFibonacciValue(int n) {
  if (n <= 1) {
     return 0;
  } else if (n == 2) {
     return 1;
  } else  {
     return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
  }
}
```
0,1 でアルゴリズムを実行するには、最初の要素を取得しようとすると 0 が取得され、2 番目の要素は 1 が取得されるように指定する必要があります。実際、前のソリューションと同様に、最初の 2 つを設定する必要があります。要素。
1.1 の実装は少し異なります。
```
public int getFibonacciValue(int n) {
  if (n == 0) {
     return 0;
  } else if (n == 1) {
     return 1;
  } else  {
     return getFibonacciValue(n - 1) + getFibonacciValue(n - 2);
  }
}
```
この場合、2 番目の要素は同じであり、メソッドの応答も同じであるため、最初の要素を 1 に設定するだけで済みます。

同時に、メソッドの反応を 0 に設定します。これを設定しないと、引数として 2 が来たときに、同じメソッドが再帰的に呼び出されますが、引数は 0 です。次に、同じメソッドが起動されます。ただし、負の数を使用するなど、負の無限大まで続きます。その結果、StackOverflowErrorを受け取ります。

ただし、線形 O(n) 時間で実行される以前の方法とは異なり、再帰的方法は完了までに大幅に時間がかかる可能性があるため、再帰的方法はお勧めできません。なぜ？ Java プログラマーがフィボナッチ数について知っておくべきこと - 3

再帰的方法では、計算プロセス中に同じ引数から関数が何度も呼び出されるため、時間がかかることがあります。たとえば、getFibonacciValue(7) を評価する場合、関数は getFibonacciValue(5) と getFibonacciValue(6) を再帰的に呼び出します。どちらの再帰呼び出しも getFibonacciValue(4) を呼び出します)。これにより、同じ操作が複数回呼び出されることになります。面接では、この方法を解決策として示すことができますが、同時にその欠点について話し、代わりに別の方法を提案することもできます。また、Java の int 型では -2147483648 から 2147483647 までを格納できるため、最初の 46 個のフィボナッチ数のみを計算できることにも注意してください。次の 47 番目を取得しようとすると、オーバーフローが発生し、負の数が得られます。int の代わりに long データ型を使用すると、最初の 91 個のフィボナッチ数を正しく計算できます。後続のフィボナッチ数を計算するには、実際に BIG 数値を格納および算術演算するためのロジックを実装する BigInteger クラスを使用する必要があります。

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION