4436 - Fibonacci numbers

• Submit
• Status
• Discuss
• Summary

Description

(피보나치 숫자들) 반복문을 이용하여 18.2에 나열된 메소드를 다시 작성하시오. 즉, 반복문을 이용하여 피보나치 수열을 구하시오.

(Fibonacci numbers) Rewrite the fib method in Listing 18.2 using iterations.

 

Input

* Line 1 :  테스트 케이스 T (1~1,000)

* Line 2 ~ T+1 : n (1~20)

Output

* Line 1 ~ T : fib(n) 

Sample Input

3
2
9
18

Sample Output

1
34
2584

Hint

힌트 : 재귀호출 없이 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.

 

Source

JAVA2015 PE18.2