poj 2506 Tiling 递推
题目描述: http://poj.org/problem?id=2506
题目大意: 使用2 * 1 和 2 * 2 的矩形铺砌2 * n 的矩形, 共有多少种方法?
分析:
假设f ( n ) 为铺砌 2 * ｎ 的矩形的方法种数， 参见下图：
http://dl.iteye.com/upload/attachment/481504/bd66df29-3f6f-37a6-b26a-1923be04dfee.png
易得 f ( n ) = f ( n - 1 ) + 2 * f ( n - 2 );
f ( 1 ) = 1; f ( 2 ) = 3;
又因为本体要求处理的n 很大, 需要大数处理, 故用Java 的BigInteger 类, 免去用c++ 实现大数加法, 代价是牺牲一部分的性能...
注意f ( 0 ) 的取值, 参见代码
import java.math.BigInteger;import java.util.Scanner;public class Main {public static void main(String[] args) {int n;//2 * n 的 nBigInteger[] a = new BigInteger;a = BigInteger.ONE;//令人上火的是a 为 1,??????//刚开始写a 为0,WAa = BigInteger.ONE;a = new BigInteger("3");for(int i = 3; i <= 250; i++) {a = a.add(a.add(a));}Scanner in = new Scanner(System.in);while(in.hasNext()) {n = in.nextInt();System.out.println(a);}}}
页:
[1]