SHUOJ 方格涂色

方格涂色"/>

SHUOJ 方格涂色

描述

有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.

---

输入
有若干行，每行有1个整数n，（n<60）。

---

输出
对每个整数n，一行输出全部的满足要求的涂法。

我的想法

这大名鼎鼎的方格涂色问题在数据较少的时候，我们码农还是能解决的，其思想仍然是递归。让我们把n个格子的涂色方案数目记为f(n)，首先我们简单的按题意画一个树形图就能知道（我就偷懒不画了）

• f(1)=3
• f(2)=6
• f(3)=6

从n>3开始我们分析，在n格涂色中，第n-1个格子与第一格的颜色要么相同，要么不同。

• 若不同，根据涂色方案首尾颜色不同的原则，第n格只能涂上与第一格和第n-1格都不同的唯一一种颜色，即

  f(n)=f(n−1) f ( n ) = f ( n − 1 ) $$f(n)=f(n-1)$$

• 若相同，根据相邻格子和首尾格子颜色不同的原则和简单的概率知识，我们知道:
  f(n) = f(n-2) × 第n-1格涂色方案数目（确定与第一格相同，值等于1） × 第n格涂色方案数目（与第一格颜色不同的两种颜色可供选择，值等于2）,即

f(n)=f(n−2)×2 f ( n ) = f ( n − 2 ) × 2 $$f(n)=f(n-2) × 2$$

综合以上两种情况我们可以得到简单的数量关系

f(n)=f(n−1)+2×f(n−2) f ( n ) = f ( n − 1 ) + 2 × f ( n − 2 ) $$f(n)=f(n-1)+2×f(n-2)$$
知道上述规律那代码就好写了，因为最多只有60格，我们可以一边算一边把 f(n)记录下来，最后按需输出就好。此外值得提醒的一点就是不要使用 int类型让数据爆掉。

代码

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