1233 核电站问题

解题思路:

总排列个数-发生爆炸的个数

基于数学推导得出的，当n大于3时可以推出之后的结果与之前有关

例：当n=9时 

1为坑方核物质 0不放

1、111000000   func(-1)*pow(2,6)

2、011100000   func(0)*pow(2,5)

3、001110000   func(1)*pow(2,4)

4、000111000  func(2)*pow(2,3)

5、000011100  func(3)*pow(2,2)  

6、000001110  func(3)*pow(2,1)  

7、000000111  func(5)*pow(2,0)

注意事项:

关键点:递推公式为    1前面的坑不发生爆炸的个数*111后面发生爆炸的个数  =   发生爆炸的个数

例：

（2）011100000前面0为1是与（1）重复 前是个只能是0111

（3）001110000前面00为11和01 与（1）（2）重复 只能是 00 10  即一个坑的不发生爆炸个数

（4）000111000     前三个000只能为 000 010 100 110 

观察可知

若（4）1前面确定紧跟个0  则前二个坑不会与前面的情况重复可以任意填

                即不重复个数即为n=2时发生不爆炸的情况的个数

若（5）1前面确定紧跟个0  则前三个坑与1，2，3，4不重复的个数就为n=3时不发生爆炸的情况的个数  

                因为（5）1前面确定紧跟个0  所以肯定不会与2，3，4重复，若前三个为111 则与（1）重复

                即重复个数为n=3时发生爆炸的情况的个数

若（6）1前面确定紧跟个0   仅仅会与（1）（2）重复，重复个数即为n=4时发生爆炸的情况的个数

                即不重复个数即为n=4时发生不爆炸的情况的个数

参考代码:

#include

#include

long long func(int n){

    int i=0;

    long long sum = 0;

    if(n<0){  //特殊情况

        return 1;

    }

    if(n<=2){

        return pow(2,n);

    }else{

        for(i=0;i<=n-3;i++){

           sum  += func(i-1)*pow(2,n-3-i);

        }

        return pow(2,n)-sum;

    }

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF){

        printf("%lld\n",func(n));

    }

return 0;

}