100盏灯开关的问题

未分类

      房间里有100盏电灯，编号为1，2，3……100，每盏灯上有一个按钮，初始时灯全都是关的。编好号的100位同学由房间外依次走进去，将自己编号的倍数的灯的按钮全部按一次，例如第一位同学把编号是1的倍数的灯的按钮按一下（此时100盏灯全亮），第二位同学把编号是2的倍数的灯的按钮按一下（此时只有50盏灯亮着，50盏被这个人按灭了）……第100位同学把编号是100的倍数的灯（即编号为100的灯）的按钮按一下，请问依次走完后，还有多少盏灯亮着？

方法一.通过模拟同学进出场开关灯实现

/**
 *100盏灯开关的问题通过模拟同学进出实现
 *1为开，0为关
 * @author Zodiac
 *
 */
public class Demo04 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		/*模拟100盏灯，1表示开，0表示关*/
		byte light[]=new byte[100];
		/*最后灯开着的数量*/
		int result=0;
		
		/*将灯初始化为全关*/
		for(int i=0;i

方法二.通过以上进出场开关流程分析，我们可以通过对灯编号进行约数计数来降低复杂度，约数个数为奇数的灯最后是开着的，约数为偶数的灯是关着的。 

/**
 *100盏灯开关的问题通过计算约数个数实现
 * @author Zodiac
 */
public class Demo05 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		/*保存开灯数量*/
		int result=0;
		/*保存约数个数*/
		int num[]=new int[100];
		/*将数组初始化为0*/
		for(int i=0;i

方法三.进一步分析，约数是成对出现的，因此只有完全平方数约数个数为奇数，其他数的约数个数都为偶数，因此本题实际上可以转换为求100内完全平方数的个数。当然答案为10。我们在上面两个代码中将开灯编号打出来，结果如下：

1 4 9 16 25 36 49 64 81 100 
10

结果验证了求100内完全平方数的个数。

该题，我是永循序渐进的的思想去解决的，可能一开始不能想到将问题转换为求100以内完全平方数的个数，但是通过模拟实现，再一步步抽象分析优化得到了最简单的模型，当然中间过程并不一定要去代码实现，我这里只是为了做比较。因此给我的启发是遇到问题要分步分析去优化。

问题延伸：如果是n盏灯，k个人呢

这里给出复杂度为O(k*n)的约数个数算法，这里的约数个数是指ni在1-k之间的约数个数，方法一复杂度也为O(k*n)。还没想到怎么优化，读者如果有想法，希望给点指点。

代码：

public class Demo05 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
       Light light=new Light(10,5);
       light.calculate();
	   System.out.println("Number of Lights that are open:\t"+light.getResult());
		
	   Light light2=new Light(100,100);
	   light2.calculate();
	   System.out.println("Number of Lights that are open:\t"+light2.getResult());
	}
	
}

class Light{
	private int lightNum;   //灯数
	private int personNum;  //人数
	private int result=0;   //保存开灯数量
	
	/**
	 * @param lightNum
	 * @param personNum
	 */
	public Light(int lightNum, int personNum) {
		this.lightNum = lightNum;
		this.personNum = personNum;
	}
	
	/*返回开灯数*/
	public int getResult(){
		return this.result;
	}
	
	public void calculate(){
		/*保存约数个数*/
		int num[]=new int[this.lightNum];
		/*将数组初始化为0*/
		for(int i=0;i

结果： 

Lights that are open:1 4 6 7 8 10 
Number of Lights that are open:	6
Lights that are open:1 4 9 16 25 36 49 64 81 100 
Number of Lights that are open:	10