[UVa] 10334 - Ray Through Glasses

題目網址: https://goo.gl/LMEBCP

題意:
(from luckycat)


解法:
直接講的話，他的遞迴式就是跟費波那契數列的關係類似：

f[ n ] = 
{ 1, if n = 0
{ 2, if n = 1
{ f[ n-1 ] + f[ n-2 ], if n > 1

解釋一下的話，當 n > 2 時，可以把當前情況 f[ n ] 分成兩個部分，
就是 由中間那條線反射回來的光線數 與 由另一邊的線反射回來的光線數，
而 前者 其實就是 f[ n-1 ] 的情況加上一次的反射，
而 後者 是 f[ n-2 ] 的情況加上兩次的反射且經由中間那條線。

TAG: BigNum, Math, DP

注意: 要用大數

程式碼:

	/**
	* Tittle: 10334 - Ray Through Glasses
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/29
	*/
	import java.util.*;
	import java.math.*;
	public class Main {
	private static int N = 1005;
	private static BigInteger[] ray = new BigInteger[N];
	public static void main( String[] args ) {
	int n;
	Scanner input = new Scanner(System.in);
	init();
	while( input.hasNext() ) {
	n = input.nextInt();
	System.out.println(ray[n].toString());
	}
	}
	private static void init() {
	ray[0] = BigInteger.ONE;
	ray[1] = BigInteger.valueOf(2);
	for( int i=2; i<=1000; ++i )
	ray[i] = ray[i-1].add(ray[i-2]);
	}
	}

view raw 10334 - Ray Through Glasses.java hosted with ❤ by GitHub