蓝桥杯算法提高VIP-开灯游戏 （C语言代码）

解题思路:

1.9个灯，各有0和1两个状态。对应着二进制的9个0到9个1（0~2^9）

2.遍历0~pow(2,9)，

3.把上述遍历的每个值转换成对应的9位二进制，并用一个数组分别存放各个位数。即代码中的数组a,用函数bin_sep()实现

4.对3中的每个遍历值，从1~9号灯依次用循环遍历操作

5.执行完一次操作，用对n数组求和==4判断是否输出

注意事项:

1.对于解题思路中的3，要注意，每次把对应遍历的值转换成的二进制，操作完相应操作后，都要把九个灯关闭，即把n数组全置零

2.memset（）函数：

   memset(数组名，置的元素，个数）

   包含在头文件<string.h> 中 

参考代码:    

#include<iostream>

#include<string.h>

#include<cmath> 

using namespace std;

#define maxn 10

int a[10];  //a[1]=0表示第1个灯不按开关，反之则按一次开关 

int n[maxn];//表示灯的状态 0为关，1为开 

void bin_sep(int x)

//把十进制的x转化成二进制形式 

//并把这个二进制形式的数按照数位分开放在一个数组中

{

memset(a,0,sizeof(a));

for(int i=9;x!=0&&i>=1;i--){

a[i]=x%2;

x=x/2;

}

}

int sum(int num[])//求和 

{

int sum=0;

for(int i=1;i<=9;i++){

sum+=num[i];

}

return sum;

}

void doit(int k,int w)

{

if(k&&w)

switch(w)

{

case 1: n[2]=!n[2];n[4]=!n[4];break;

case 2: n[1]=!n[1];n[3]=!n[3];n[5]=!n[5];break;

case 3: n[2]=!n[2];n[6]=!n[6];break;

case 4: n[1]=!n[1];n[5]=!n[5];n[7]=!n[7];break;

case 5: n[2]=!n[2];n[4]=!n[4];n[6]=!n[6];n[8]=!n[8];break;

case 6: n[3]=!n[3];n[5]=!n[5];n[9]=!n[9];break;

case 7: n[4]=!n[4];n[8]=!n[8];break;

case 8: n[5]=!n[5];n[7]=!n[7];n[9]=!n[9];break;

case 9: n[6]=!n[6];n[8]=!n[8];break;

}

}

int main()

{

int num=0;

memset(n,0,sizeof(n));

for(int i=0;i<=pow(2,9);i++){  //9个灯，各有0和1两个状态。对应着二进制的9个0到9个1（0~2^9） 

memset(n,0,sizeof(n));

bin_sep(i);                //把当前遍历到的数用9位二进制表示并拆放在a数组中 

for(int j=1;j<=9;j++){    //从1号灯到9号灯，模拟灯的操作 

doit(a[j],j);         //传入对应数组的值，1就操作，0不操作；j是指对第几个灯操作   

    }

    if(sum(n)==4){            //如果对于数值i操作完后，恰有4个亮灯则输出 

for(int i=1;i<=9;i++){

cout<<a[i]; 

if(i==9) {

        memset(a,0,sizeof(a));

    }

}

cout<<endl;

}

}

return 0;

}