因为小蜜蜂的缘故,然后又是一行的问题,自然就想到了递推,于是前四个都直接打表出来了,发现好像规律不那么明显,那么还从斐波拉契数列那来寻找规律,果然

从第四项开始就有一个f[n] = f[n-1] + 2*f[n-2]的规律了,那就打表完成吧。

不过关键是这规律怎么来的才是关键,根据斐波拉契的规律,多从目标的前一个与前两个来找规律。

n>=4时,n-1的颜色只可能有两种情况

因为n-1格颜色肯定与n不同,而n的颜色又与第一个不同

故:要么第n-1格的颜色和第1格的颜色不同(第一种),要么第n-1格的颜色和第1格的颜色相同(第二种)

第一种情况:f[n] = f[n-1](1,n-1,n三者颜色都不同)

第二种情况:f[n-2]*第n个格子的颜色数=f[n-2] * 2(1与n-1相同,与n-2必不同,故有两种颜色可选)

故所有情况之和f[n]=f[n-1] + f[n-2] * 2  n >= 4

 

代码如下

#include<stdio.h>
long long f[51];
void set(){
	int i;
	f[1] = 3;
	f[2] = 6;
	f[3] = 6;
	
	for(i = 4; i < 51; i++)
		f[i] = f[i-1] + 2 * f[i-2];
}
int main()
{
	set();
	int n;
	while(scanf("%d", &n) != EOF)
			printf("%lld\n", f[n]);
	return 0;
}