今天给公司面试iOS,去面的时候,发现公司让面试人做了套题(不知在哪找的这套题,反正我没让人做过题,可能是人事自作主张吧),其中题目里面有个算法题,我看那哥们答的一塌糊涂毫无思路,闲的无事简单的说说这100盏灯
原题是这样的
100盏灯,默认全部关闭,第一个人全部打开(亮),第二个人按照 1 , 3 , 5 ... 的顺序按开关,第三个人按 1 , 4 , 7 ... 的顺序按开关,以此类推,当第100个人按完开关后,哪些灯是亮着的.
我先理解下题目
首先前提虽没说,但灯肯定是按一次开,在按一次关闭,再按一次开.
给的推理太少了,我且按出题人的意思是
1,2,3,4,5,6,7,8,9,10...100 (+1)
1,3,5,7,9,11,13, (+2)
1,4,7,10,13,16, (+3)
1,5,9,13,17,21, (+4)
1,6,11,16,21,26, (+5)
从数字规律大体明白了,第一个人会按的灯的数字是+1,第二个人+2,第三个人+3,第四个人+4;
最后亮着的灯这个需要什么条件呢 (开光开光开光)
那肯定是这个灯被按了奇数次啊
找到这个必要条件就好说了.
说算法
把灯编上号 deng 1,2,3,4,5,6,7,8,9,10...100
把人编上号 people 1,2,3,4,5,6,7,8,9,10...100
人1 会按 所有灯
人2 会按 灯号 = 1 + 2(x - 1) 得出小于等于100以内的 灯号
人3 会按 灯号 = 1 + 3(x - 1) 得出小于等于100以内的 灯号
人4 会按 灯号 = 1 + 4*(x - 1) 得出小于等于100以内的 灯号
可以看出 人1 也满足上面的公式
整个表格图看下
绿的表示亮,红的表示关闭
上代码算法
for (int lamp = 1; lamp <= 100; lamp++) {//循环1-100的灯
for (int people = 1; people <= 100; people++) {//循环1-100的人
/*关键点 如果(灯的编号 减去 1 ) 除以 人的编号 的 余数 等于 0,
则这个灯会被该编号的人按一次 ,这样按得次数加一*/
int remainder = (lamp - 1) % people;
if (remainder == 0) {
NSLog(@"灯号 %d 会被编号为 %d 人按了",lamp,people);
}
}
}
接下来需要加一个变量,统计灯被按了多少次,在被按的时候让这个变量加一;
for (int lamp = 1; lamp <= 100; lamp++) {//循环1-100的灯
int tip_time = 0; //统计该灯被按了多少次
for (int people = 1; people <= 100; people++) {//循环1-100的人
/*关键点 如果(灯的编号 减去 1 ) 除以 人的编号 的 余数 等于 0,
则这个灯会被该编号的人按一次 ,这样按得次数加一*/
int remainder = (lamp - 1) % people;
if (remainder == 0) {
tip_time ++;
// NSLog(@"灯号 %d 会被编号为 %d 人按了",lamp,people);
}
}
NSLog(@"灯号 %d ,按 %d 次",lamp,tip_time);
}
最后在加一个变量,判断被按的次数是不是奇数就完了
for (int lamp = 1; lamp <= 100; lamp++) {//循环1-100的灯
int tip_time = 0; //统计该灯被按了多少次
for (int people = 1; people <= 100; people++) {//循环1-100的人
/*关键点 如果(灯的编号 减去 1 ) 除以 人的编号 的 余数 等于 0,
则这个灯会被该编号的人按一次 ,这样按得次数加一*/
int remainder = (lamp - 1) % people;
if (remainder == 0) {
tip_time ++;
// NSLog(@"灯号 %d 会被编号为 %d 人按了",lamp,people);
}
}
NSLog(@"灯号 %d ,按 %d 次",lamp,tip_time);
if (tip_time % 2 == 1) {//如果这个灯被按了奇数次,则这个灯最后亮着
NSLog(@"灯--%d 亮",lamp);
}
}
结果
2017-05-23 18:34:36.715 Test[11648:625294] 灯--2 亮
2017-05-23 18:34:36.715 Test[11648:625294] 灯--5 亮
2017-05-23 18:34:36.715 Test[11648:625294] 灯--10 亮
2017-05-23 18:34:36.715 Test[11648:625294] 灯--17 亮
2017-05-23 18:34:36.716 Test[11648:625294] 灯--26 亮
2017-05-23 18:34:36.716 Test[11648:625294] 灯--37 亮
2017-05-23 18:34:36.716 Test[11648:625294] 灯--50 亮
2017-05-23 18:34:36.716 Test[11648:625294] 灯--65 亮
2017-05-23 18:34:36.716 Test[11648:625294] 灯--82 亮
还有一种解法;
第一盏灯结果显而易见，所以从第二盏灯开始算；先让100个灯的编号减去一，这样编号为1-99；第一个人打开1-99灯；第二个人打开2，4.......灯；第三个人打开3，6......灯；第四个人打开4，8.....灯；第五个人打开5，10.......灯；第6个人打开6，12.......灯；依次类推；先看第6盏灯被按了4次，因为他的因子为：1，2，3，6；所以因子个数决定了按的次数，比方4的因子为：1，2，4，它就被按了3次；只有平方数的因子为奇数，所以只有平方数的灯为亮着的；因为刚开始我们减去了一，所以亮的灯的编号为平方数+1；
哈哈
仅供参考,分享一下个人解法而已,肯定有更精神简单的解法,欢迎大家分享.
如有错误欢迎指出 谢谢
