Java 프로그래머가 피보나치 수열에 대해 알아야 할 사항

특히 외국계 기업에서는 인터뷰를 할 때 알고리즘에 대한 질문을 받는 경우가 많고, 스트레스가 많은 상황에서 정신없이 무언가를 기억하는 것이 항상 쉬운 것은 아닙니다. 그러므로 준비가 필요합니다. 시작하려면 최소한 기본 알고리즘에 대한 기억을 새로 고치십시오. 오늘 우리는 피보나치 수열과 그와 관련된 문제의 가장 일반적인 변형과 같은 현상을 분석할 것입니다. 피보나치 수열은 숫자 0과 1로 시작하는 자연수 시퀀스이며, 이후의 각 숫자는 이전 두 숫자의 합과 같습니다. 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으로 시작된다는 점은 주목할 가치가 있습니다... 일반적으로 문제 조건에서 계열이 시작하는 처음 두 숫자(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 크기의 배열을 만듭니다. 처음 두 요소는 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 클래스 의 정적 반복 메서드는 초기 배열 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을 얻고 두 번째 요소는 - 1을 얻도록 지정해야 합니다. 실제로 이전 솔루션에서와 마찬가지로 처음 두 요소를 설정해야 합니다. 강요.
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);
  }
}
```
이 경우 두 번째 요소는 동일하고 메서드의 응답도 동일하므로 첫 번째 요소만 1로 설정하면 됩니다.

동시에 메소드의 반응을 0으로 설정합니다. 설정하지 않으면 2가 인수로 올 때 동일한 메소드가 재귀적으로 호출되지만 인수는 0입니다. 다음으로 동일한 메소드가 실행됩니다. , 그러나 음수 등은 음의 무한대까지 계속됩니다. 결과적으로 StackOverflowError 가 발생합니다 .

그러나 선형 O(n) 시간으로 실행되는 이전 방법과 달리 재귀 방법은 완료하는 데 훨씬 더 오랜 시간이 걸릴 수 있으므로 권장되지 않습니다. 왜? 자바 프로그래머가 피보나치 수열에 대해 알아야 할 것 - 3

재귀 방법은 계산 과정에서 동일한 인수에서 함수가 여러 번 호출되므로 시간이 오래 걸릴 수 있습니다. 예를 들어 getFibonacciValue(7)를 평가할 때 함수는 getFibonacciValue(5) 및 getFibonacciValue(6)에 대한 재귀 호출을 수행하고 두 재귀 호출 모두 getFibonacciValue(4))를 호출하므로 동일한 작업이 여러 번 호출됩니다. 인터뷰에서 이 방법을 해결책으로 보여주면서 동시에 단점에 대해 이야기하고 그에 대한 대가로 다른 방법을 제안할 수도 있습니다. 또한 Java의 int 유형을 사용하면 -2147483648에서 2147483647까지 저장할 수 있으므로 처음 46개의 피보나치 수만 계산할 수 있습니다. 다음 47번째를 얻으려고 하면 오버플로가 발생하고 우리는 음수를 얻게 될 것입니다. int 대신 long 데이터 유형을 사용하면 처음 91개의 피보나치 수를 올바르게 계산할 수 있습니다. 후속 피보나치 수를 계산하려면 실제로 큰 숫자의 저장 및 산술 연산을 위한 논리를 구현하는 BigInteger 클래스를 사용해야 합니다.

코멘트

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