Poj 2506 Tiling (Java高精度 + 递推)

分手后的思念是犯贱 2022-08-25 09:13 10阅读 0赞

题意：有2×1和2×2两种规格的地板，现要拼2×n的形状，求共有多少种情况。

数据较大，需要高精度运算。

假设我们已经铺好了2×（n-1）的情形，则要铺到2×n则只能用2×1的地板

假设我们已经铺好了2×（n-2）的情形，则要铺到2×n则可以选择1个2×2或两个2×1，故可能有下列三种铺法

![2011080615045389.png][]![2011080615051645.png][] ![2011080615052834.png][]

其中第三个会与铺好2×（n-1）的情况重复，故可以得到递推式a\[i\]=2\*a\[i-2\]+a\[i-1\];

import java.math.*;
    import java.util.*;
    
    public class Main
    {
    	public static void main (String[] args)
    	{
    		BigInteger [] a=new BigInteger[255]; //大数数组
    		a[0]=BigInteger.ONE;   //初始化
    		a[1]=BigInteger.ONE;
    		a[2]=a[1].add(a[0].add(a[0]));
    		for (int i=3;i<=250;i++)
    			a[i]=a[i-1].add(a[i-2].add(a[i-2]));
    		Scanner cin = new Scanner(System.in); //输入打开
    		
    		while (cin.hasNext())  //判断是否文件结束
    		{
    			int n=cin.nextInt();
    			System.out.println(a[n]); //输出
    		}
    		cin .close();//输入关闭
    	}
    }

[2011080615045389.png]: http://pic002.cnblogs.com/images/2011/315754/2011080615045389.png
[2011080615051645.png]: http://pic002.cnblogs.com/images/2011/315754/2011080615051645.png
[2011080615052834.png]: /images/20220824/24b9ba29113a4c6499e902792189fbd4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2506 Tiling 递推+大数

将答案存在ret数组里面 n=0的时候居然是1 递推关系 ret[i] = ret[i-1] + ret[i-2]2 ; 注意是乘2不是3，当ret\[i

拼搏现实的明天。/ 2023年06月16日 12:56/ 0 赞/ 3 阅读

相关 Poj 2506 Tiling (Java高精度 + 递推)

题意：有2×1和2×2两种规格的地板，现要拼2×n的形状，求共有多少种情况。数据较大，需要高精度运算。假设我们已经铺好了2×（n-1）的情形，则要铺到2×n则只能用2×

分手后的思念是犯贱/ 2022年08月25日 09:13/ 0 赞/ 11 阅读

相关 POJ1019 数学+递推乱搞

有一个字符串的形式是这样的112123123412345123456123456712345678123456789123456789101234567891011123456

╰+攻爆jí腚メ/ 2022年08月22日 15:24/ 0 赞/ 142 阅读

相关 poj2506-Tiling(规律，大数)

Tiling <table style="text-align:center"> <tbody> <tr> <td><strong>Time Limit:<

水深无声/ 2022年08月04日 10:48/ 0 赞/ 137 阅读

相关 POJ1503 Integer Inquiry(高精度加法)

题目大意：输入最多100行数据，每个数据最多100位数字，输入0后结束输入。求和。解题思想：输入为从高位到低位，且数据位数不定，用char型存储。 int型数

缺乏、安全感/ 2022年07月11日 07:55/ 0 赞/ 206 阅读

相关 POJ 1405 Heritage（模拟+高精度乘法）

Your rich uncle died recently, and the heritage needs to be divided among your relatives

末蓝、/ 2022年06月12日 07:12/ 0 赞/ 186 阅读

相关 POJ 3982 序列（高精度加法）

数列A满足An = An-1 + An-2 + An-3, n >= 3 编写程序，给定A0, A1 和 A2, 计算A99 Input 输入包含多行数据

系统管理员/ 2022年06月09日 02:08/ 0 赞/ 203 阅读

相关 UVA - 11375 Matches(高精度，递推)

![Center][] 题意：这道题就是给N个火柴棍，问你用它们最多能组成多少种数，比如说3根火柴棍只能组合成1和7两种，因为1需要两根火柴，7需要三根火柴，其他都需要四根及

矫情吗；*/ 2022年06月09日 00:12/ 0 赞/ 167 阅读

相关 poj 2506 Tiling

Tiling <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

谁借莪１个温暖的怀抱￠/ 2022年05月29日 04:19/ 0 赞/ 110 阅读

相关 POJ 2506 Tiling(递归+高精度)

Tiling <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

男娘i/ 2021年11月02日 06:30/ 0 赞/ 224 阅读