白準-フィボナッチ関数[103]


質問する


次のソースはN番目のフィボナッチ数を求めるC++関数である.

fibonacci(3)を呼び出すと、次のことが起こります.
fibonacci(3)はfibonacci(2)とfibonacci(1)(最初の呼び出し)を呼び出す.
fibonacci(2)はfibonacci(1)(2番目の呼び出し)とfibonacci(0)を呼び出す.
2番目に呼び出されたfibonacci(1)は1を出力し、1を返す.
fibonacci(0)は0を出力し、0を返します.
fibonacci(2)は、fibonacci(1)およびfibonacci(0)の結果を得て、1を返す.
最初に呼び出されたfibonacci(1)は1を出力し、1を返します.
fibonacci(3)はfibonacci(2)とfibonacci(1)の結果を得て2を返す.
1出力2回、0出力1回です.nが与えられると、fibonacci(n)が呼び出されると、0と1がそれぞれ何回出力されるかを計算するプログラムが作成される.

入力


第1行は、試験例の個数Tを与える.
各試験例は1行からなり、Nが与えられる.Nは40以下の自然数または0である.

しゅつりょく


各試験例の出力0の回数と出力1の回数は、スペースで区切られている.

に答える


0と1の呼び出し回数を求めるために,2次元配列のdpテーブルを作成する.
d[n][0]は、n値のときに0を呼び出す回数であり、同様に、d[n][1]は1を呼び出す回数である.
ティラ方式でfor文で解けばいいです.
Scanner入力を受け入れ始めたばかりで、java 8は正しいですが、java 11はタイムアウトします.したがって、BufferedReaderを使用して入力時間を短縮して通過することができる.

ソース

import java.io.*;

public class Q1003 {
	public static int n;
	public static int[][] d = new int[41][2];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());

		// d[N][0] : 0 호출 횟수 , d[N][1] : 1 호출 횟수
		d[0][0] = 1;
		d[1][1] = 1;

		while (t-- > 0) {
			n = Integer.parseInt(br.readLine());

			for (int i = 2; i <= n; i++) {
				// 0 과 1
				for (int j = 0; j < 2; j++) {
					d[i][j] = d[i - 1][j] + d[i - 2][j];
				}
			}

			System.out.println(d[n][0] + " " + d[n][1]);
		}
	}

}