核电站问题 （C语言代码）

解题思路:

注意事项:

参考代码:

//按树的思路
//连续两个都建站 则第三个不能建
/*       0                                 1
      0     1                           0    1
    0 1  0  1                      0   1  0  1
            */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int a[41];
int n;
int z;  
void glc(int c){
 if(c==n){  //位置排满
  z++;  //每种可能 z+1
  return ;
 }
 else{
  if(a[c-1]==1 && a[c-2]==1){ //如果前面两个位置都有核电站了  那么此处就不能建站
   a[c]=0;
   glc(c+1);
  }
  else{
   int i;
   for(i=0;i<=1;i++){  //0 表示不建站   1表示建站
    a[c]=i;  
    glc(c+1);//递归
   }
  }
 }
}
int main(){
 while(scanf("%d",&n)!=EOF){
  if(n==0){//如果没有坑位的话  直接跳过
   continue;
  }
  int c=0;  //注意初始值设为0  开始有1  0 两种变量
  z=0;
  glc(c);
  printf("%d\n",z);
 }
 return 0;
}