首页 > 代码库 > 从150盏灯这道奥数题说起......
从150盏灯这道奥数题说起......
前段时间，成都9岁学生纠错奥赛名题这篇文章在网上爆红。
本文不关注神童之类的新闻，仅仅从计算机实现的角度来验证题目正确性。
题目描述(需求描述):
150盏亮着的电灯，各有一个拉线开关控制，按顺序编号为1，2，3，…，150。将编号为3的倍数的灯的拉线各拉一下，再将编号为5的倍数的灯的拉线各拉一下，拉完后亮着的灯数为__盏。
使用暴力穷举法来获得正确答案:
为了简单期间，我们可以将150盏灯缩小10倍，变为15盏灯，这样就很容易用暴力穷举法来标记出灯的最终结果:
答案:
第一遍拉灭3的倍数，15÷3=5个
第二遍拉灭5的倍数，15÷5=3个
重点！！！
问题就出在第二遍上，第二遍真的拉灭3个灯吗，不对！！！
算出3和5的公倍数有15÷(3×5)=1个，就是说第二次的时候，有1盏(15号)灯是第一次拉灭的，第二次再拉是不是又亮了呢？
那么第二次实际上是拉灭了2盏灯(5号灯,10号灯)，同时拉亮了1盏(15号灯)，那么最后是多少灯亮着呢?
15-5-2+1=9盏
通过上面的缩小10倍，暴力穷举后，你会发现正确的答案！
然后再扩大10，就知道90是正确答案！
这道题目，目的是考察公倍数相关知识，只是饶了几个圈。
提炼关键点(需求分析)
150盏灯，按顺序1-150编号，初始处于亮着的状态，每个灯有两种状态变化:亮/暗(开关变量)。
由上面这句话，我们可以提炼出一个数据结构 Light，具有两个关键的属性,具体见下面代码:struct Light { int index; //第一个属性，index表示当前灯的编号 int isOn; //第二个属性，isOn表示当前灯是不是亮着 //构造函数 Light() { index = 0; //初始化时候，编号为0，后面代码会设置到底是哪个编号 isOn = 1; //根据题意，初始化时候，所有灯是属于亮着状态，因此设置为1,表示灯亮着，如果isOn为0，表示灯暗着 } };将编号为3的倍数的灯的拉线各拉一下，再将编号为5的倍数的灯的拉线各拉一下。
1) 在计算机代码中，我们如何来表示整除这个概念呢?
很简单，用c语系的%符号，该符号表示取模操作(或叫取余操作)。例如: 15%5 = (15-3*5) = 0 表示余数为0,则15被5整除，而15整除5。 15%4 = (15-3*4)=3 表示余数为3,有余数情况下，就没有整除和被正处的概念
所以，使用计算机代码表示整除，我们可以使用条件语句加取模操作来表示:
int x = 15; //int 是c关键词，表示整数(包括自然数和负数) if((x % 5) == 0) //如果 x%5 的结果为0 { //则说明x能被5整除 //下面就进行结果处理 } else { //否者不能被5整除 //你可以处理不能被5整除的情况，也可以不处理 //如果不处理else状态，那么你可以将else{}这段代码全部不写，就当作什么都不发生 }2) 在计算机代码中，我们如何表示开关状态?
两种方式://条件语句，繁琐 int onoff = 1; //0表示关，1表示开，初始化，onoff = 1表示开 //markA: if(onoff == 1) //如果onoff ==1 ，说明是开的情况下 { onoff = 0; //则把他关闭 } else //否则onoff == 0,说明是关的情况 { onoff = 1; //则把他打开 }你会发现使用条件判断方式，很繁琐，而且不高效。这时候我们可以引入c语系的一个经典的操作符^(异或操作)
由于开关操作表示的状态就是0(关)/1(开),那么我们很容易使用异或来表示开关int onoff = 1; //0表示关，1表示开，初始化，onoff = 1表示开 onoff ^= 1; // 表示如果onoff=1,则变为0, 如果onoff=0,则变为1 //只要这么一句话，就相当于上面的markA下所有条件判断代码，你会发现，真是少写了很多代码，而且相当具有美感
有了上面这些基础知识，我们就很容易写出代码来通过计算机程序进行验证
代码实现:
#define LIGHTCOUNT 150
int main()
{
//分配150个灯的内存，初始化时候，isOn为true，说明灯是亮着
Light lights[LIGHTCOUNT];
//将150个灯进行编号，index = [1-150]
for (int i = 0; i < LIGHTCOUNT; i++)
{
lights[i].index = i+1;
}
//遍历150个灯，凡是能被3整除的(%取模操作=0),则将标记变量进行异或操作(x^1表示，如果x为0,则变为1，如果x为1,则变为0,经典的开关变量)
for (int i = 0; i < LIGHTCOUNT; i++)
{
if ((lights[i].index) % 3 == 0)
{
lights[i].isOn ^= 1; //由于初始化都是亮着，所以能被3整除的灯，异或后，变为关状态
}
}
//遍历150个灯，凡是能被5整除的(%取模操作=0),则将标记变量进行异或操作(x^1表示，如果x为0,则变为1，如果x为1,则变为0,经典的开关变量)
for (int i = 0; i < LIGHTCOUNT; i++)
{
if ((lights[i].index) % 5 == 0)
{
lights[i].isOn ^= 1;
}
}
//到上面代码，凡是inOn = 1的，表示灯开着，否者关闭，我们来输出计数器，看看有多少灯是亮着的
int count = 0; //计数器初始化为0个
//遍历150个灯，凡是isOn = 1的话，则计数器加1，并且打印出亮着的灯的索引号以及isOn状态(此时，肯定isOn = 1)
for (int i = 0; i < LIGHTCOUNT; i++)
{
if (lights[i].isOn)
{
count++;
if(count % 3 == 0)
printf("亮着的灯的索引号:%03d 状态:%d\n", lights[i].index, lights[i].isOn);
else
printf("亮着的灯的索引号:%03d 状态:%d ", lights[i].index, lights[i].isOn);
}
}
//最后打印出到底还有多少灯亮着
printf("一共有多少个灯亮呢? 答案是:%d\n", count);
getchar();
return 0;
}运行一下代码:
我们将150盏灯:
#define LIGHTCOUNT 150
改为15盏灯:
#define LIGHTCOUNT 15
运行一下代码:
由此，我们用c语言验证了这道题目。
在这段简单的代码中，涉及了c语言程序的大部分基本核心要素:
struct定义了数据结构Light以及两个属性(成员变量)
任何程序语言，总归能用三种类型的语句来解决任何编程问题: for ---> 循环语句 if ---> 条件语句 除此之外的语句，称为顺序语句 天道循环，不出这三种语句。上亿行的操作系统，几十行的简单程序，都是由这三种语句组合而成。
由此可见，c语言是简单，强大的语言，特别适合三年级及以上的学生学习
由:
1、例如 struct/for/if/int 等32个固定的关键词 2、3大语句(循环语句，条件语句以及顺序语句) 3、例如 + - * / % > == < ^... 几十个操作符
组合而成。
c语言绝对是开拓思维的好工具。
当思维练习在纸上做的时候， 那叫奥林匹克数学！
当思维联系用计算机做的时候， 那叫信息奥林匹克！
拿了奥数杯赛好名次，小升初有加分
拿了信息奥林匹克，清华北大就直接抢，最后都成了微软，谷歌，facebook的菜。
本文出自 “随风而行之青衫磊落险峰行” 博客，转载请与作者联系！
从150盏灯这道奥数题说起......