试题 算法训练 瓷砖铺放
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
有一长度为N(1<=Ｎ<=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，代表地板的长度
输出格式
输出一个数，代表所有不同的瓷砖铺放方法的总数
样例输入
<span style="color:#344659"><span style="color:#666666"><span style="color:#666666">4
</span></span></span>
样例输出
<span style="color:#344659"><span style="color:#666666"><span style="color:#666666">5</span></span></span>解题思路：
解法一：双循环解题+全排列判断：两个for循环很容易想到，但本题关键是当瓷砖1和瓷砖2的数目不等时，会出现多种排列方式，这里我用全排列函数+map求出不重复的铺法(详见函数getDiff() )；而当两种瓷砖的数目相同时，只有一种铺法。最后累加两种情况就得出铺法的总数。
解法二：递归法：未完待续。。。
ACcodesV1:
#include <iostream>
#include <algorithm>
#include <map>
#include <sstream>using namespace std;int N;/* 有一长度为N(1<=Ｎ<=10)的地板，给定两种不同瓷砖：一种长度为1，另一种长度为2，数目不限。
要将这个长度为N的地板铺满，一共有多少种不同的铺法？ */string ItoS(int n){stringstream ss;ss<<n;return ss.str();
}int getDiff(int x,int y){int arr[x+y];map<string,bool> existed;for(int i=0;i<x+y;i++){if(i<x)arr[i]=1;elsearr[i]=2;}do{string st="";for(int i=0;i<x+y;i++)st+=ItoS(arr[i]);if(!existed[st])existed[st]=true;}while(next_permutation(arr,arr+x+y));return existed.size();
}int main()
{cin>>N;int a=1,b=2;int cnt=0;for(int i=0;;i++){int sum=0;for(int j=0;;j++){sum=i*a+j*b;//cout<<sum<<endl;if(sum==N){if(i==j)cnt++;elsecnt+=getDiff(i,j);}if(sum>=N)break;}if(i*a>=N)break;}cout <<cnt<< endl;return 0;
}