在一无限大的二维平面中，我们做如下假设：
1、 每次只能移动一格；
2、 不能向后走（假设你的目的地是“向上”，那么你可以向左走，可以向右走，也可以向上走，但是不可以向下走）；
3、 走过的格子立即塌陷无法再走第二次；
求走n步不同的方案数（2种走法只要有一步不一样，即被认为是不同的方案）。
这道题的思路需要将向前走和向侧面走分开来讨论，因为前一步是向哪一个方向走的对后一步的方案也有影响作用。
首先，我们假设走n步有f（n）种走法，那么，当在上一步的走法f（n-1）中，有a（n-1）中最后一步是向前的，且b（n-1）种方案最后一步是向侧面的，且有a(n-1)+b(n-1)=f(n-1)，f(n)=a(n)+b(n);无论上一步是向前还是侧面，下一步都可以向前，故a(n)=a(n-1)+b(n-1)；如果上一步是侧面，那么下一步向侧面只能持续一个方向，如果是向上的，那么下一步要想侧面走的话既可以向左，又可以向右，故b(n)=b(n-1)+2a(n-1).
合并：f(n)=a(n)+b(n)=a(n-1)+b(n-1)+b(n-1)+2a(n-1)=3a(n-1)+2b(n-1)。
到此，可以写出相关代码，即先将a(n),b(n)的值都写出，再根据输入的数值输出答案。
也可以继续变换：f(n)=2f(n-1)+a(n-1)=2f(n-1)+(a(n-2)+b(n-2))=2f(n-1)+f(n-2);
#include <stdio.h>
int a[21]={0,3,7};
void main()
{
int i,k,n;
for (i=3;i<=20;i++)
a[i]=2*a[i-1]+a[i-2];
scanf("%d",&n);
while(n--)
{
scanf("%d",&k);
printf("%d\n",a[k]);
}
}
有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.
这道题的难点在于第n个格子的处理，由于需要满足的是第n个和第一个不同，有两种情况
1、n-1和第1个不同，假设第一个是R，那么第n个应为P或G，那么第n-1个一定也为G或P，第n-2个则一定是R；
2、n-1和第1和相同，那么，第n-2个便有两种与第一个不同的情况，而n也会有两种情况。
在这两种情况下，由于涉及到了n-2项，不妨作出如下推断：
假设第n-2项已经确定，那么，n-2项有三种颜色的可能，分为和1相同和不相同。
1、第n-2项与第一项相同，那么，第n-1项有两种选择（不干涉），第n项有1种选择。总有f（n-1）种。
2、若不同，属于上述的第二种情况，n-1便有一种情况，而第n项有两种情况可选择，为2f（n-2）种。
又因为第n-1项的三种可能都包含在f（n-2）中，所以，f（n）=2f（n-2）+f（n-1）；
代码详细如下：
#include <stdio.h>
#include <math.h>
void main()
{
int n,i;
__int64 a[51]={0,3,6,6};
for(i=4;i<=50;i++)
a[i]=2*a[i-2]+a[i-1];
while(scanf("%d",&n)!=EOF)
{
printf("%I64d\n",a[n]);
}
}
