ALGO-11_蓝桥杯_瓷砖铺放(递归)

时间:2021-07-06 11:01:49
问题描述
  有一长度为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 }