与之解法相同的题 POJ1953,http://124654439.iteye.com/admin/blogs/2071845
题目大意:
有一个2*n大小的矩形地板,用2*2和2*1大小的瓷砖方块来填满它。
求一共有多少种放法。
分析:
如图,我们假设先放第一块方块,那么有以下两种放法
设n长度的瓷砖有f(n)块放法,
对于图中上面这种放法,f(n)=f(n-2)
显然中间的也是f(n)=f(n-2)
而下面的则是f(n)=f(n-1)
所以可以得到一个递归公式f(n)=f(n-1)+2*f(n-2).有了递推公式,很容易得到程序,但需要注意的是这道题的输出结果超出基本数据类型能表示的范围,所以需要使用大整数运算,所以这道题用JAVA编写方便一些,因为JAVA中有大整数类
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import com.sun.java_cup.internal.runtime.Scanner; public class Main { public static void main(String[] args) { //BigInteger n=new BigInteger("257"); BigInteger[] f=new BigInteger[257]; int n = 0; String s; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //Scanner cin=new Scanner(System.in); try { int flag=1; s=br.readLine(); while(s.compareTo("\n")!=0) { if(flag==0) s=br.readLine(); n=Integer.parseInt(s); f[0]=new BigInteger("1"); f[1]=new BigInteger("1"); for(int i=2;i<=n;i++) { f[i]=f[i-1].add(f[i-2].multiply(new BigInteger("2"))); } System.out.println(f[n]); flag=0; } } catch (NumberFormatException e) { // TODO Auto-generated catch block e.printStackTrace(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } } }
相关推荐
(poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)……中级有:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,...
递归和分治法 递推 构造法() 模拟法(,,,,) 图算法: 图的深度优先遍历和广度优先遍历 最短路径(dijkstra,bellman-ford,floyd,heap+dijkstra)(,,poj1062,poj2253,poj1125,poj2240) 最小生成树...
POJ 2659 Raid 分治法解决两组点中距离最近的点对
(3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,...
一.基本算法:枚举. (poj1753,poj2965)贪心(poj1328,poj2109,poj2586)递归和分治法
4.6 划分、解决、合并:分治法 4.6.1 数列上的分治法 4.6.2 树上的分治法 4.6.3 平面上的分治法 4.7 华丽地处理字符串 4.7.1 字符串上的动态规划算法 4.7.2 字符串匹配 4.7.3 后缀数组 4.8 一起来挑战GCJ的题目(3)...
1. 最近点对问题的算法实现 2. 利用分治法设计一个计算两个 n 位的大整数相乘的算法,要求计算时间低于 O(n2) 5. Poj1065 Wooden St
分治法 Pow(x,n) Sqrt(x) 贪心法 Jump Game Jump Game II Best Time to Buy and Sell Stock Best Time to Buy and Sell Stock II Longest Substring Without Repeating Characters Container With Most Water ...
在poj上accepted的代码。对大整数进行了封装,能很方便地求而出1000位以内的整数的运算。
2.6 随机素数测试和大数分解 (POJ 1811) . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 欧拉函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.1 分解质因素求...