蓝桥杯算法提高VIP-开灯游戏
题目描述 有9盏灯与9个开关,编号都是1~9。 每个开关能控制若干盏灯,按下一次会改变其控制的灯的状态(亮的变成不亮,不亮变成亮的)。
具体如下:
第一个开关控制第二,第四盏灯;
第二个开关控制第一,第三,第五盏灯;
第三个开关控制第二,第六盏灯;
第四个开关控制第一,第五,第七盏灯;
第五个开关控制第二,第四,第六,第八盏灯;
第六个开关控制第三,第五,第九盏灯;
第七个开关控制第四,第八盏灯;
第八个开关控制第五,第七,第九盏灯;
第九个开关控制第六,第八盏灯。
开始时所有灯都是熄灭的,开关是关闭着的。要求按下若干开关后,使得只有4盏灯亮着。
输入格式
无
输出格式
输出所有可能的方案,每行一个方案,每一行有9个字符,从左往右第i个字符表示第i个开关的状态(" 0" 表示关闭," 1" 表示打开),按字典序输出。下面的样例输出只是部分方案。
样例输入
无
样例输出
000001011
000001110
000001111
这题解法超级多,这里提供两种新手最能接受的方法
暴力(枚举)和位操作(切换位)的方法
方法一:新手暴力
解题思路:逐一枚举,复杂的问题只需简单的暴力
注意:不用担心时间复杂度高导致超时,因为每个开关和每个灯都只有两种状态
#include <stdio.h>
int main(void)
{
int light[9] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};
int a,b,c,d,e,f,g,h,i;
int k;
int cnt;
for(a=0;a<=1;a++)
for(b=0;b<=1;b++)
for(c=0;c<=1;c++)
for(d=0;d<=1;d++)
for(e=0;e<=1;e++)
for(f=0;f<=1;f++)
for(g=0;g<=1;g++)
for(h=0;h<=1;h++)
for(i=0;i<=1;i++){
if(a==1)
{light[1] = -light[1];light[3] = -light[3];}
if(b==1)
{light[0] = -light[0];light[2] = -light[2];light[4] = -light[4];}
if(c==1)
{light[1] = -light[1];light[5] = -light[5];}
if(d==1)
{light[0] = -light[0];light[4] = -light[4];light[6] = -light[6];}
if(e==1)
{light[1] = -light[1];light[3] = -light[3];light[5] = -light[5];light[7] = -light[7];}
if(f==1)
{light[2] = -light[2];light[4] = -light[4];light[8] = -light[8];}
if(g==1)
{light[3] = -light[3];light[7] = -light[7];}
if(h==1)
{light[4] = -light[4];light[6] = -light[6];light[8] = -light[8];}
if(i==1)
{light[5] = -light[5];light[7] = -light[7];}
cnt = 0;
for(k=0;k<9;k++)
{
if(light[k]==1)
{
cnt++;
}
light[k] = -1;
}
if(cnt==4)
{
printf("%d%d%d%d%d%d%d%d%d\n",a,b,c,d,e,f,g,h,i);
}
}
return 0;
}
方法二:位操作(切换位)
解题思路:利用两个整型数的9个二进制位来分别代表9个开关和9盏灯
学会这种方法,可以解许多同类型的方法,可以节约大量时间,推荐新手多练习此方法
注意事项:
切换位:
整数 8的二进制为 1 0 0 0
整数14的二进制为1 1 1 0
那么 8^14 得到0 1 1 0,即将第四盏灯切换为关闭状态,用这个方法再配合移位操作就可以实现9盏灯的开关了
掩码:
01 & n 就可以查看最低位为1还是为0 , 02 & n 就可以查看第一位,以此类推…
01使用的是1的八进制形式,突出掩码作用,实际可以使用任意进制
#include <stdio.h>
int main(void)
{
int n;
int k;
int cnt,i;
for(n=0;n<512;n++)
{
cnt = 0;
k = 0;
if(1&n) k = k^2^8;
if(2&n) k = k^1^4^16;
if(4&n) k = k^2^32;
if(8&n) k = k^1^16^64;
if(16&n) k = k^2^8^32^128;
if(32&n) k = k^4^16^256;
if(64&n) k = k^8^128;
if(128&n) k = k^16^64^256;
if(256&n) k = k^32^128;
for(i=0;i<9;i++)
{
if(01&k>>i)
{
cnt++;
}
}
if(cnt==4)
{
for(i=0;i<9;i++)
{
printf("%d",(256&n<<i)==256?1:0);
}
putchar('\n');
}
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)