第九届蓝桥杯大赛个人赛决赛（软件类）真题--C大学B组--激光样式题解（C语言）

标题：激光样式

x星球的盛大节日为增加气氛，用30台机光器一字排开，向太空中打出光柱。 安装调试的时候才发现，不知什么原因，相邻的两台激光器不能同时打开！
国王很想知道，在目前这种bug存在的情况下，一共能打出多少种激光效果？

显然，如果只有3台机器，一共可以成5种样式，即：

全都关上（sorry, 此时无声胜有声，这也算一种）

开一台，共3种

开两台，只1种

30台就不好算了，国王只好请你帮忙了。

要求：

提交一个整数，表示30台激光器能形成的样式种数。

注意：

只提交一个整数，不要填写任何多余的内容。

思路：

刚看到这道题就觉得这道题如果手撕，需要DFS+回溯，代码放最后，手稿也是。

我们先说个简单的思路：

1. 0表示关灯，1表示开灯
2. 一台机器有2种效果(0,1)
3. 两台机器有3种效果(00,10,01)
4. 三台机器有5种效果(000,100,010,001,101)
5. 四台机器有8种效果(0000,1000,0100,0010,1010,0001,1001,0101)

由分析得：

1. 每种机器只有开关两种状态，且开灯受前一台机器影响
2. 若当前机器开灯，需要前一台机器是关灯状态
3. 而前一台机器是否是关灯状态，又受前前一台机器影响
4. 故当前机器的开关状态受前两台机器的影响
5. 通俗讲，就是后缀“0”的个数+后缀“1”的个数。

由题意得：

后缀“0”无限制；后缀“1”需要最后一个为“0”，而这恰好就是前前一台机器的效果数量。

故得公式：

当前效果数量=上一个效果数量+上上一个效果数量

//当前效果数量Count=上一个效果数量(second)+上上一个效果数量(first)
#include<stdio.h>
int main()
{
	int first=2, second=3;
	int i, Count=0;
	for(i=2; i<30; i++){
		Count = first + second;
		first = second;
		second = Count;
	}
	
	printf("%d\n", Count);
	return 0;
	
 } 

如果你想不出来上述规律，可以使用dfs+回溯手撕代码。解释下次出：

#include<stdio.h>

long long ans;
int sta[52];

void dfs(int x){
	if(x == 31)
	{
		ans++;
		return ;
	}
	dfs(x+1);
	if(sta[x-1] == 0)
	{
		sta[x] = 1;
		dfs(x+1);
		sta[x] = 0;
	}
}
 
int main()
{
	dfs(1);
	
	printf("%d\n",ans);
	
	return 0;
}