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<light.length;i++)
			light[i]=0;
		
		/*模拟同学进场进行开关灯*/
		for(int j=1;j<=100;j++){
			for(int i=1;i<=100;i++){
				if(i%j==0){
					if(light[i-1]==0)
						light[i-1]=1;
					else
						light[i-1]=0;
				}				
			}
		}
		/*统计开灯数*/
		for(int i=0;i<light.length;i++){
			if (light[i]==1){
				result++;
			}			
		}
	
		/*输出开灯的数目*/
		System.out.println(result);
	}

}

/**
 *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<num.length;i++)
			num[i]=0;
		
		/*计算约数个数*/
		for(int i=1;i<=100;i++)
			for(int j=1;j<=i;j++){
				if(i%j==0){
					num[i-1]++;
				}
			}
		
		/*统计开灯数*/
		for(int i=0;i<num.length;i++){
			if (num[i]%2==1){
				result++;
			}			
		}
		
		/*输出开灯的数目*/
		System.out.println(result);
	}
	
}

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

1 4 9 16 25 36 49 64 81 100 
10

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

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

100盏灯开关的问题,布布扣,bubuko.com

100盏灯开关的问题

原文：http://blog.csdn.net/fei_zodiac/article/details/24179477