Time Limit: 1s
Memory Limit: 128MB
(피보나치 숫자들) 반복문을 이용하여 18.2에 나열된 메소드를 다시 작성하시오. 즉, 반복문을 이용하여 피보나치 수열을 구하시오.
(Fibonacci numbers) Rewrite the fib method in Listing 18.2 using iterations.
* Line 1 : 테스트 케이스 T (1~1,000)
* Line 2 ~ T+1 : n (1~20)
* Line 1 ~ T : fib(n)
3 2 9 18
1 34 2584
힌트 : 재귀호출 없이 fib(n)를 계산하려면, fib(n-2)와 fib(n-1)을 먼저 계산하여야 한다. f0과 f1을 전전항과 전항의 피보나치 숫자라고 하자. 구하고자 하는 피보나치 숫자는 f0 + f1이 될 것이다. 알고리즘은 다음과 같이 표현될 수 있다:
Hint: To compute fib(n) without recursion, you need to obtain fib(n - 2) and fib(n - 1) first. Let f0 and f1 denote the two previous Fibonacci numbers. The current Fibonacci number would then be f0 + f1. The algorithm can be described as follows:
f0 = 0; // For fib(0)
f1 = 1; // For fib(1)
for (int i = 1; i <= n; i++) {
currentFib = f0 + f1;
f0 = f1;
f1 = currentFib;
}
// After the loop, currentFib is fib(n)
사용자 입력을 받아 피보나치 숫자를 출력하는 프로그램을 작성하시오.
Write a test program that prompts the user to enter an index and displays its
Fibonacci number.
JAVA2015 PE18.2