输入描述 Input Description
包含一个整数n
输出描述 Output Description
输出一个整数表示方法数。
样例输入 Sample Input
样例1：4
样例2：5
样例输出 Sample Output
样例1：3
样例2：8
数据范围及提示 Data Size & Hint
对于100%的数据（3<=N<=30）
解题思路：
这实际上是编程序解决数学问题，假设把n个盒子放成一行，有cnt(n)种方法,可分两方面来考虑:
1. n个盒子排成一行，如果把第一个盒子拿掉，剩下的n-1个盒子里面满足条件，有cnt(n-1)种，第一个盒子有2种情况：放铀或者铅，因此这种情况共有 2*cnt(n-1) 种。
2. n个盒子排成一行，如果把第一个盒子拿掉，剩下的n-1个盒子不满足条件，那么只有当前三个盒子是铀，第四个盒子是铅才可以。（注：第四个盒子如果是铀，那么234盒子就满足条件了）。pow(2, n-4)是n-4盒子的所有情况，减去cnt(n-4)后n-4盒子满足条件的（因为本部分讨论的是“如果把第一个盒子拿掉，剩下的n-1个盒子不满足条件”）。
cnt(n)=2*cnt(n-1) +pow(2,n-4)-cnt(n-4)；接下来编写程序就可以了。
标准程序：
#include <stdio.h>
#include <math.h>
int cnt(int n);
int main(){
int n;
scanf(“%d”,&n);
printf(“%d\n”,cnt(n));
return 0;
}
int cnt(int n){
if(n<3) return 0;
else if(n==3) return 1;
else if(n==4) return 3;
else
return 2*cnt(n-1)+pow(2,n-4)-cnt(n-4);
}
运行结果：
