问题描述
有一长度为 N(1<=Ｎ<=10)的地板，给定三种不同瓷砖：一种长度为 1，一种长度为 2，另一种长度为 3，数目不限。要将这个长度为 N 的地板铺满，
并且要求长度为 1 的瓷砖 不能相邻，一共有多少种不同的铺法？
例如，长度为 4 的地板一共有如下 4 种铺法：
4=1+2+1
4=1+3
4=2+2
4=3+1
编程求解上述问题。
第一种
输入格式
只有一个数 N，代表地板的长度。
输出格式
方案总数。
样例输入
4
样例输出
4
动态规划
n表示长度
| 最后一块不是1 (则是2或3) | 最后一块是1 |
总共 |
| f_not1(1)=0 |
f_1(1)=1 |
f(1) |
| f_not1(2)=1 |
f_1(2)=0 |
f(2) |
| f_not1(3)=2 |
f_1(3)=1 |
f(3) |
|
f_not1(4)=f(1)+f(2) 铺满1块地板的数量（再铺一块3）+ 铺满2块地板的数量（再铺一块2） |
f_1(4)=f_not1(3) 最后一块不是1的f_not1(3) |
f(4) |
|
f_not1(5)=f(2)+f(3) 铺满2块地板的数量（再铺一块3）+ 铺满3块地板的数量（再铺一块2） |
f_1(5)=f_not1(4) 最后一块不是1的f_not1(4) |
f(5) |
|
f_not1(6)=f(3)+f(4) 铺满3块地板的数量（再铺一块3）+ 铺满4块地板的数量（再铺一块2） |
f_1(6)=f_not1(5) | f(6) |
| …… | …… | …… |
|
f_not1(n)=f(n-3)+f(n-2) 铺满n-3块地板的数量（再铺一块3）+ 铺满n-2块地板的数量（再铺一块2） |
f_1(n)=f_not1(n-1) | f(n) |
或者（只是看的方式不一样）
| 第一块不是1 (则是2或3) | 第一块是1 |
总共 |
| f_not1(1)=0 |
f_1(1)=1 |
f(1) |
| f_not1(2)=1 |
f_1(2)=0 |
f(2) |
| f_not1(3)=2 |
f_1(3)=1 |
f(3) |
|
f_not1(4)=f(1)+f(2) 铺满最后1块地板的数量（第一块再铺一块3）+ 铺满最后2块地板的数量（第一块再铺一块2） |
f_1(4)=f_not1(3) 第一块不是1的f_not1(3) |
f(4) |
|
f_not1(5)=f(2)+f(3) 铺满最后2块地板的数量（第一块再铺一块3）+ 铺满最后3块地板的数量（第一块再铺一块2） |
f_1(5)=f_not1(4) 第一块不是1的f_not1(4) |
f(5) |
|
f_not1(6)=f(3)+f(4) 铺满3块地板的数量（第一块再铺一块3）+ 铺满4块地板的数量（第一块再铺一块2） |
f_1(6)=f_not1(5) | f(6) |
| …… | …… | …… |
|
f_not1(n)=f(n-3)+f(n-2) 铺满n-3块地板的数量（第一块再铺一块3）+ 铺满n-2块地板的数量（第一块再铺一块2） |
f_1(n)=f_not1(n-1) | f(n) |
参考代码
#include<stdio.h>
int f_not1(int n){
if(n==1)return 0;
else if(n==2)return 1;
else if(n==3)return 2;
else return f(n-3)+f(n-2);
}
int f_1(int n){
if(n==1)return 1;
else if(n==2)return 0;
else if(n==3)return 1;
else return f_not1(n-1);
}
int f(int n){
return f_not1(n)+f_1(n);
}
int main(){
int result;
int n;
scanf("%d",&n);
result=f(n);
printf("%d",result);
return 0;
}
第一种
输入格式
只有一个数 N，代表地板的长度。
输出格式
每行一个方案，最后一行有一个数，代表方案总数。
样例输入
4
样例输出
4=1+2+1
4=1+3
4=2+2
4=3+1
4
| 第一块不是1 | 第一块是1 | 第一块是2 | 第一块是3 |
| not1(1)=0 | is1(1)=1 | is2(1)=0 |
is3(1)=0 |
| not1(2)=1 |
is1(2)=0=not1(1) 第一块不是1的1 |
is2(2)=1 |
is3(2)=0 |
|
not1(3)=2=is2(3)+is3(3) 第一块不是3， 则是第一块是2和第一块是3的和 |
is1(3)=1=not1(2) 第一块不是1的2 |
is2(3)=1=f(1) 第一块是2，则还需铺满1 |
is3(3)=1 |
| not1(4)=f(1)+f(2)=is2(4)+is3(4) |
is1(4)=not1(3) 第一块不是1的3 |
is2(4)=f(2) 第一块是2，则还需铺满2 |
is3(4)=f(1) 第一块是3，则还需铺满1 |
| not1(5)=f(2)+f(3)=is2(4)+is3(5) |
is1(5)=not1(4) 第一块不是1的4 |
is2(4)=f(3) 第一块是2，则还需铺满3 |
is3(5)=f(2) 第一块是3，则还需铺满2 |
| …… | …… | …… | …… |
| not1(n)=f(n-3)+f(n-2)=is2(n)+is3(n) |
is1(n)=not1(n-1) |
is2(n)=f(n-2) 第一块是2，则还需铺满n-2 |
is3(n)=f(n-3) 第一块是3，则还需铺满n-3 |
输出时：先输出“”1+“”is1(n) 再输出“”2+“”is2(n) 最后输出 “”3+“”is1(3)
比如N=4
输出"1+"is1(4)
is1(4)就是not1(3)、not1(3)就是is2(3)和is3(3)、is2(3)就是2+1 is3(3)就是3 所以输出1+2+1 和1+3
#include<stdio.h>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
vector<string>s[15];
int main(){
s[1].push_back("1");
s[2].push_back("2");
s[3].push_back("1+2");
s[3].push_back("2+1");
s[3].push_back("3");
int N;
scanf("%d",&N);
for(int i=4;i<=N;i++){
for(int j=0;j<s[i-1].size();j++){
if(s[i-1][j][0]!='1') s[i].push_back("1+"+s[i-1][j]);//1+not1(N-1)
}
for(int j=0;j<s[i-2].size();j++){
s[i].push_back("2+"+s[i-2][j]);//2+is2(N-2)
}
for(int j=0;j<s[i-3].size();j++){
s[i].push_back("3+"+s[i-3][j]);//3+is3(N-3)
}
}
for(int i=0;i<s[N].size();i++){
cout<<N<<"="<<s[N][i]<<endl;
}
printf("%d\n",s[N].size());
return 0;
}