算法:多少灯亮着,以及约数问题

January 21st 2015  | Tags: 算法

2015-01-20

问题


问题1、房间里有100盏电灯,编号为1, 2, …, 100,每盏灯上有一个按钮,初始时灯全都是关的。有80个同学依次编号为1, 2,…, 80,这些同学依次进入房间,将自己编号的倍数的灯的按钮全部按一次,例如第一位同学(编号是1)把编号是1的倍数的灯的按钮按一下(此时100盏灯全亮),第二位同学(编号是2)把编号是2的倍数的灯的按钮按一下(此时只有50盏灯亮着,50盏被这个人按灭了),……,第80位同学把编号是80的倍数的灯(即编号为80的灯)的按钮按一下,请问依次走完后,还有多少盏灯亮着?

问题2、如何求一个正整数的约数的个数?(本文的约数是正约数)

问题3、如何找一个约束个数为100的数字?

答案


问题1:

(转换思路,找出规律)
被按奇数次的灯在最后会亮着,而偶数次的等是灭的。这就转换成了数字的约数的个数问题。

例如,要判断编号为9的灯在最后是亮还是灭,先求9的小于等于80的所有约数的个数(约数有1,3,9,共3个约数,也意味着编号为1、3、9的同学会按9号灯的按钮)。约数个数为奇数,故9号灯是亮的。

既然,这样如何求约数的个数?

问题2:

要求整数N的约数的个数,最简洁的思路是求出其所有的约数并计数。

N%i==0,那么i就是N的一个约数。

思路一:遍历1…N的所有整数,判断每一个数字是否是N的约数,并计数。

思路二:设n=floor(sqrt(N)),遍历1…n的所有整数,判断每一个数字是否是N的约数,并计数,得到count,若n×n = N,那么N的约数个数为count×2-1,否则为count×2

思路三:也可以用数学上的方法来解决。首先分解质因数,再结合约数个数定理解决。

问题3:

约数个数定理解决。

更机智的解决方法


被按奇数次的灯在最后会亮着,而偶数次的等是灭的。所以只要判断编号为n的灯的约数是奇数个还是偶数个即可。

令k=(int)sqrt(n),若k×k == n,那么编号为n的灯的约数是奇数个。于是,很容易判断,9的约数是奇数个(1、3、9),10的约数是偶数个(1、10、2、5)。

参考


http://www.blogjava.net/amigoxie/archive/2012/10/18/389818.html
http://www.cnblogs.com/yinger/archive/2012/08/14/2639097.html

(完)