关于万人开关门

关于万人开关门
原题：
@数学文化：#周末数学题# （转载在美国的一个朋友的电邮）我小孩上初中的第一次数学作业：有1万 个人和1万个关着的门， 第一人把所有的门打开，第二个人把所有的偶数门关上，第三个人把所有三的倍数门打开，第四个人把所有四的倍数门关上，依此类推，1万人都折腾一遍后，哪些门开着？那些门关着？

思考过程：
如果，是按顺序进行，前一人全部做完之后，后一个人才开始做，要做多久啊。
所以，先算出结果，然后，一万人同时做，瞬间解决问题，并且省了无数的无用功。

等等，题目中没说按人的顺序进行的，也就是说，这一万个人，有可能同时开始执行任务的。也有可能，随机开始的。
如果是随机开始，那根本无解。
如果是同时开始的话，全开着。任务同时开始，别人都做完了，第一个人还在做。。。最后，他把所有的门全打开了。

嗯，这就是一道扯蛋的题，所以，只要能解释得通，就算正确吧

评论

26 楼 tiandp007 2011-06-16  

zhangchang 写道

tiandp007 写道

【第N个人把所有的N的倍数门关/开】----注意到【所有的】了没？
第1个门  第1个人 最后一次操作
第2个门  第2个人 最后一次操作
第3个门  第3个人 最后一次操作
第N个门  第N个人 最后一次操作
答案非常明显{1开、2关、3开......10000关}

为什么会有质数、素数、因子、平方数、正则表达式等等高深的讨论？

明显没有看懂题意

哥们，别装那么高深了..说说你的理解和解法。

25 楼 chinaagan 2011-06-16  

第n个人一定会对第n个门操作，如果n为奇数，则打开该门，如果n为偶数，则关闭该门。所以应该是一半打开，一半关闭吧。

24 楼 huoyj 2011-06-15  

我认为最后关闭的门的编号是2^n，n为1，2...m,并且2^m<=10000的。这个得用到素数定理证明。

23 楼 zhangchang 2011-06-15  

tiandp007 写道

【第N个人把所有的N的倍数门关/开】----注意到【所有的】了没？
第1个门  第1个人 最后一次操作
第2个门  第2个人 最后一次操作
第3个门  第3个人 最后一次操作
第N个门  第N个人 最后一次操作
答案非常明显{1开、2关、3开......10000关}

为什么会有质数、素数、因子、平方数、正则表达式等等高深的讨论？

明显没有看懂题意

22 楼 tiandp007 2011-06-15  

【第N个人把所有的N的倍数门关/开】----注意到【所有的】了没？
第1个门  第1个人 最后一次操作
第2个门  第2个人 最后一次操作
第3个门  第3个人 最后一次操作
第N个门  第N个人 最后一次操作
答案非常明显{1开、2关、3开......10000关}

为什么会有质数、素数、因子、平方数、正则表达式等等高深的讨论？

21 楼 zjriso 2011-06-14  

lyw985 写道

Crusader 写道

zhanghh321 写道

1号门有1个人碰过
2号门有2个人碰过
3号门有3个人碰过
4号门有4个人碰过
....
答案很明显  啦

-1

-2

-3

20 楼 suwey 2011-06-14  

lzyzizi 写道

刚才回头看了下问题，发现有个地方很多人都理解错了，除数的奇偶性无法判断门的开关，因为只有奇除数是关门而偶除数是开门。。。
比如:4的除数 1,2,4。按照质因数分解的思路，他应该是关着的，但是仔细看题会发现2和4都是关门，也就是说1开门以后，2关门，4也关门。。。也就是说4根本不会关心当前门的状态，执行他所应该执行的动作，所以其实门开不开只由最后一个开关人的决定。

night_stalker 写道

哦，每个门只受最后一个碰它的人影响，最后一个碰它的人的号码和门相同。
1开2关3开4关5开6关⋯⋯
所以结果就是奇数门开，偶数门关 ⋯⋯

原来正解早就出现。。。

我也觉得这个解释已经对了。。不知道为什么还有那么多复杂的讨论

19 楼 cttnbcj 2011-06-14  

18 楼 诗词吾爱 2011-06-14  

挺有意思哈

17 楼 lzyzizi 2011-06-14  

刚才回头看了下问题，发现有个地方很多人都理解错了，除数的奇偶性无法判断门的开关，因为只有奇除数是关门而偶除数是开门。。。
比如:4的除数 1,2,4。按照质因数分解的思路，他应该是关着的，但是仔细看题会发现2和4都是关门，也就是说1开门以后，2关门，4也关门。。。也就是说4根本不会关心当前门的状态，执行他所应该执行的动作，所以其实门开不开只由最后一个开关人的决定。

night_stalker 写道

哦，每个门只受最后一个碰它的人影响，最后一个碰它的人的号码和门相同。
1开2关3开4关5开6关⋯⋯
所以结果就是奇数门开，偶数门关 ⋯⋯

原来正解早就出现。。。

16 楼 huoyj 2011-06-14  

看来我也理解错了，重新理解一下

15 楼 fivestarwy 2011-06-14  

fivestarwy 写道

lzyzizi 写道

int N = 10000000;
int[] count = new int[N];
 
for (int i =1; i < N; i++)
{
   for (int f = i; f < N; f += i)
   {
      count[f]++;
   }
}

这个算法的复杂度大概是O(NLOG(N))，但是他没有用到除法和乘法所以他要比对于N个数因式分解要快不少。

因式分解时间复杂度O(sqrt(N)),总共复杂度也就是O(N*sqrt(N)),1.5次的多项式复杂度还是很好接受吧，其中质数还可以打表，还有优化的空间

14 楼 fivestarwy 2011-06-14  

lzyzizi 写道

int N = 10000000;
int[] count = new int[N];
 
for (int i =1; i < N; i++)
{
   for (int f = i; f < N; f += i)
   {
      count[f]++;
   }
}

这个算法的复杂度大概是O(NLOG(N))，但是他没有用到除法和乘法所以他要比对于N个数因式分解要快不少。

因式分解时间复杂度O(sqrt(N)),总共复杂度也就是O(N*sqrt(N)),1.5次的多项式复杂度还是很好接受吧

13 楼 lzyzizi 2011-06-14  

Crusader 写道

fivestarwy 写道

初一的因式分解题啊，求一个数因子的个数。
给门从1编号，编号因子个数（包括1）为偶则为开，奇则为关。
M=q1^n1*q2^n2*q3^n3.........
判断(n1+1)*(n2+1)*(n3+1)........的奇偶性即可

+1

每个数都去因式分解效率是很低的~其实这个问题就是在问一个数的除数有多少？对于这个问题，相对较好（应该还有不少优化空间）的解法就是楼主题目描述的方式。不过这个做法有个缺点就是占用空间较大。

int N = 10000000;
int[] count = new int[N];
 
for (int i =1; i < N; i++)
{
   for (int f = i; f < N; f += i)
   {
      count[f]++;
   }
}

这个算法的复杂度大概是O(NLOG(N))，但是他没有用到除法和乘法所以他要比对于N个数因式分解要快不少。

12 楼 shanga 2011-06-14  

shanga 写道

shanga 写道

Crusader 写道

fivestarwy 写道

初一的因式分解题啊，求一个数因子的个数。
给门从1编号，编号因子个数（包括1）为偶则为开，奇则为关。
M=q1^n1*q2^n2*q3^n3.........
判断(n1+1)*(n2+1)*(n3+1)........的奇偶性即可

+1

+1,因子相同的看作一个

仔细想了下，上面的‘因子相同的看作一个’是不对的

11 楼 jsltool 2011-06-14  

n号门是打开还是闭合，应该是看n的最大公约数的奇偶性，是奇数门是开着的，偶数门是关着的。
所以要先把1到10000的所有质数求出来。

10 楼 shanga 2011-06-14  

shanga 写道

Crusader 写道

fivestarwy 写道

初一的因式分解题啊，求一个数因子的个数。
给门从1编号，编号因子个数（包括1）为偶则为开，奇则为关。
M=q1^n1*q2^n2*q3^n3.........
判断(n1+1)*(n2+1)*(n3+1)........的奇偶性即可

+1

+1,因子相同的看作一个

9 楼 shanga 2011-06-14  

Crusader 写道

fivestarwy 写道

初一的因式分解题啊，求一个数因子的个数。
给门从1编号，编号因子个数（包括1）为偶则为开，奇则为关。
M=q1^n1*q2^n2*q3^n3.........
判断(n1+1)*(n2+1)*(n3+1)........的奇偶性即可

+1

+1

8 楼 lyw985 2011-06-14  

Crusader 写道

zhanghh321 写道

1号门有1个人碰过
2号门有2个人碰过
3号门有3个人碰过
4号门有4个人碰过
....
答案很明显  啦

-1

-2

7 楼 Crusader 2011-06-14  

fivestarwy 写道

初一的因式分解题啊，求一个数因子的个数。
给门从1编号，编号因子个数（包括1）为偶则为开，奇则为关。
M=q1^n1*q2^n2*q3^n3.........
判断(n1+1)*(n2+1)*(n3+1)........的奇偶性即可

+1