学步园

10334 - Ray Through Glasses

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1275

Suppose we put two panes of glass back-to-back. How many ways  are there for light rays to pass through or be reflected after changing direction n times
? Following figure shows the situations when the value of nis 0, 1 and 2. 
                                  

Input 

It is a set of lines with an integer n where 0 <= n <= 1000 in each of them.

Output 

For every one of these integers a line containing  as described above.

Sample Input 

0
1
2

Sample Output 

1
2
3

对于an，如果我们在中间那层玻璃反射，那么后面必须在上面那层反射一次，后面的情况数为a(n-2)；如果我们在下面那层反射，后面的情况数为a(n-1)

所以有an = a(n-1) + a(n-1)

但是n最多为1000，考虑到斐波那契数列是以指数增长的，所以要用高精度来处理。

完整代码：

/*0.022s*/

#include <cstdio>

int F[1005][60];

int main(void)
{
	F[0][0] = 1, F[1][0] = 2;
	for (int i = 2; i <= 1000; ++ i)
	{
		for (int j = 0 ; j < 55 ; ++ j)
			F[i][j] = F[i - 1][j] + F[i - 2][j];
		for (int j = 0; j < 55; ++ j)
		{
			F[i][j + 1] += F[i][j] / 10000;///分离进位
			F[i][j] %= 10000;///截取后4位
		}
	}
	int n;
	while (~scanf("%d", &n))
	{
		int end = 55;
		while (end > 0 && !F[n][end]) --end;
		printf("%d", F[n][end--]);
		while (end >= 0) printf("%04d", F[n][end--]);///逆序输出
		printf("\n");
	}
	return 0;
}

/*0.582s*/

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
	static final int maxn = 1001;
	static Scanner cin = new Scanner(new BufferedInputStream(System.in));

	public static void main(String[] args) {
		BigInteger[] f = new BigInteger[maxn];
		f[0] = BigInteger.ONE;
		f[1] = BigInteger.valueOf(2);
		for (int i = 2; i < maxn; ++i)
			f[i] = f[i - 1].add(f[i - 2]);
		while (cin.hasNextInt())
			System.out.println(f[cin.nextInt()]);
	}
}