算法训练 瓷砖铺放
时间限制:1.0s 内存限制:512.0MB
锦囊1
锦囊2
锦囊3
问题描述
有一长度为N(1<=N<=10)的地板,给定两种不同瓷砖:一种长度为1,另一种长度为2,数目不限。要将这个长度为N的地板铺满,一共有多少种不同的铺法?
例如,长度为4的地面一共有如下5种铺法:
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
编程用递归的方法求解上述问题。
例如,长度为4的地面一共有如下5种铺法:
4=1+1+1+1
4=2+1+1
4=1+2+1
4=1+1+2
4=2+2
编程用递归的方法求解上述问题。
输入格式
只有一个数N,代表地板的长度
输出格式
输出一个数,代表所有不同的瓷砖铺放方法的总数
样例输入
4
样例输出
5
思路分析:
一开始这个题我想用递归去往一个数组中添加一和二,看是否在某一个时刻,数组内的和为N。这个思路并没有做出来。
参考了网上的代码,发现自己真的很菜。。。 由于这个题不需要输出组成的序列,只输出总的数目即可,所以每次递归是的变量加一或者加二,然后根据回溯法的思想,如果加上一小于等于N则调用pudiban(val+1),如果加上二小于等于N则调用pudiban(val+2),实际上不用判断val是否会超出N,因为在调用这一层函数的时候已经判断过了。
代码:
import java.util.Scanner;
public class Main瓷砖铺法 {
static Scanner scan = new Scanner(System.in);
static int N;
static int count = 0;
public static void main(String[] args) {
N = scan.nextInt();
pudiban(0);
System.out.println(count);
}
private static void pudiban(int val) {
if (val == N) {
count++;
return;
}
if (val + 1 <= N) {
pudiban(val + 1);
}
if (val + 2 <= N) {
pudiban(val + 2);
}
}
}