问题描述 有一长度为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 编程用递归的方法求解上述问题。 输入格式 只有一个数N,代表地板的长度 输出格式 输出一个数,代表所有不同的瓷砖铺放方法的总数 样例输入 4 样例输出 5
AC代码:
1 #include <stdio.h> 2 3 int n; 4 int count = 0; 5 6 void dfs(int step,int sum) 7 { 8 int i; 9 if (sum == n) 10 { 11 count ++; 12 return ; 13 } 14 15 if (step > n) 16 return ; 17 18 for (i = 1 ; i <= 2 ; i ++) 19 { 20 dfs(step+1,sum+i); 21 } 22 23 return ; 24 } 25 26 int main(void) 27 { 28 scanf("%d",&n); 29 dfs(0,0); 30 printf("%d",count); 31 return 0; 32 }