質問する

右図に示すように、三角形は螺旋状に並んでいます.最初の三角形は正の三角形で、辺の長さは1です.次に、次の手順で正三角形を追加します.スパイラル上の最長エッジの長さがkの場合、そのエッジにkの長さの正三角形を追加します.

波数の半数列P(N)は螺旋上の正三角形の辺の長さである.P(1)からP(10)までの最初の10の数字は、1、1、2、2、3、4、5、7、9である.
Nが与えられた場合、P(N)を求めるプログラムを作成してください.

入力

第1行は、試験例の個数Tを与える.各試験例は1行からなり、Nが与えられる.(1 ≤ N ≤ 100)

しゅつりょく

各テストボックスはP(N)を出力する.

に答える

この問題にはフィボナッチ数列に似た規則がある.問題は、1、1、1、2、2、3、4、5、7、9の順で値を求める順序を示している.だからこの順番でルールを探せばいいのです.
1番+2番=4番(1+1=2)
2番+3番=5番(1+1=2)
3番+4番=6番(1+2=3)
4番+5番=7番(2+2=4)
...
i-3番+i-2番=i番
このことから、点火式はp(n)=p(n−2)+p(n−3)であることがわかる.
また、この問題では、nは100以下であり、n=100の場合の値がかなり大きいため、intタイプではなくlongタイプを使用すべきである.

ソース

import java.util.*;

public class Main {
	public static int t, n;
	public static long[] d = new long[101];

	public static long p(int x) {
		if (x == 0) {
			return 0;
		}

		if (x == 1 || x == 2 || x == 3) {
			return 1;
		}

		if (d[x] != 0) {
			return d[x];
		}

		return d[x] = p(x - 2) + p(x - 3);
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		t = sc.nextInt();

		while (t-- > 0) {
			n = sc.nextInt();

			System.out.println(p(n));
		}
	}

}