关于煮鸡蛋问题的广而推之

[size=4]    首先是煮鸡蛋问题，这是一道小学一年级的数学题，原帖因为比较搞笑所以在水版：[/size]
[url=http://xycq.moddiy.com/forum/thread-174441-1-1.html][size=4]http://xycq.moddiy.com/forum/thread-174441-1-1.html[/size][/url]
[size=4]为了方便不想看上面这个帖子的人，月月在这里把问题重复一下：煮1个鸡蛋需要6分钟，现在问煮6个鸡蛋要多长时间。[/size]
[size=4]    这个题目没有给出锅子的容积，所以我个人认为标准答案是6分钟，也就是假设锅子的容积可以装6个鸡蛋，并且假设不管多少个鸡蛋一起煮，所需时间不变。那么上面这样恶搞完以后，月月开始很严肃地思考：如果[/size][color=#000000][size=4][font=宋体]我们把问题推广化：假设我们有[/font][font=Times New Roman]M[/font][font=宋体]个鸡蛋，每个鸡蛋煮[/font][font=Times New Roman]T[/font][font=宋体]分钟后可以熟，而锅的容积是[/font][font=Times New Roman]N[/font][font=宋体]个鸡蛋（[/font][font=Times New Roman]M[/font][font=宋体]≥[/font][font=Times New Roman]N[/font][font=宋体]），问最少多长时间可以煮熟，而且在最短时间内的煮熟方法。[/font][/size][/color]
[color=#000000][size=4][font=宋体]    首先还是要定几条前提条件的，这样就杜绝了我这样爱刨根问题钻牛角尖的人。前提条件一是：忽略水越煮越少的问题；前提二：不管是分几次煮的，只要煮够[/font][font=Times New Roman]T[/font][font=宋体]分钟，鸡蛋就可以熟；前提三：忽略把鸡蛋拿进锅子和拿出锅子的时间；前提四：时间可以细分，比如我们可以精确测量出[/font][font=Times New Roman]1/n[/font][font=宋体]这种很细微的时间；前提五：鸡蛋是一模一样的，而且该系统是在完全理想的情况下进行的，忽略诸如大气压变化、空气温度变化、火焰大小变化等影响因素。[/font][/size][/color]
[size=4][color=#000000][font=宋体]    那么，第一个问题很好回答，最小时间一定是[/font][font=Times New Roman]t=M*[/font][/color][color=#000000][font=Times New Roman]T[/font][font=宋体]÷[/font][font=Times New Roman]N[/font][font=宋体]。麻烦的是，在[/font][font=Times New Roman]t[/font][font=宋体]时间内，我们如何煮熟[/font][font=Times New Roman]M[/font][font=宋体]个鸡蛋。[/font][/color][/size]
[size=4][color=#000000][font=宋体]    首先，我们用[/font][font=Times New Roman]M[/font][font=宋体]除以[/font][font=Times New Roman]N[/font][font=宋体]，假设商是[/font][font=Times New Roman]a[/font][font=宋体]，余数是[/font][font=Times New Roman]b[/font][font=宋体]，也就是说，[/font][font=Times New Roman]M=a*[/font][/color][color=#000000][font=Times New Roman]N+b[/font][font=宋体]。我们把[/font][font=Times New Roman]M[/font][font=宋体]个鸡蛋分成两部分，第一部分是（[/font][font=Times New Roman]a-1[/font][font=宋体]）*[/font][font=Times New Roman]N[/font][font=宋体]个，第二部分是[/font][font=Times New Roman]N+b[/font][font=宋体]个。可见，[/font][font=Times New Roman]N+b[/font][font=宋体]介于[/font][font=Times New Roman]N[/font][font=宋体]和[/font][font=Times New Roman]2N[/font][font=宋体]之间。当然，如果[/font][font=Times New Roman]M[/font][font=宋体]本身就介于[/font][font=Times New Roman]N[/font][font=宋体]和[/font][font=Times New Roman]2N[/font][font=宋体]之间，那就意味着[/font][font=Times New Roman]a=1[/font][font=宋体]，所以第一部分是[/font][font=Times New Roman]0[/font][font=宋体]个鸡蛋，第二部分是[/font][font=Times New Roman]M[/font][font=宋体]个鸡蛋。第一部分的鸡蛋比较好煮，只要[/font][font=Times New Roman]N[/font][font=宋体]个[/font][font=Times New Roman]N[/font][font=宋体]个地煮就可以了，因为锅子被充分应用了，所以热量没有浪费，这样煮出来的时间一定是最短的，最终需要（[/font][font=Times New Roman]a-1[/font][font=宋体]）*[/font][font=Times New Roman]T[/font][font=宋体]分钟。[/font][/color][/size]
[color=#000000][size=4][font=宋体]    出于简便，我们把第二部分的鸡蛋数设为[/font][font=Times New Roman]m[/font][font=宋体]。显而易见地，如果锅子里无论什么时候的鸡蛋数都是最大容积数，也就是[/font][font=Times New Roman]N[/font][font=宋体]，那么，所用的时间一定是最短的。也就是说，在[/font][font=Times New Roman]T[/font][font=宋体]分钟内同时煮熟[/font][font=Times New Roman]N[/font][font=宋体]个鸡蛋，是最省时间的（也就是按照第一部分的煮法）。在这种模式下，平均每个鸡蛋煮熟的时间是[/font][font=Times New Roman]T/N[/font][font=宋体]。但是实际上通过常识我们可以知道，煮熟[/font][font=Times New Roman]N[/font][font=宋体]个鸡蛋和煮熟[/font][font=Times New Roman]1[/font][font=宋体]个鸡蛋所用的时间是一样的。之所以一锅只煮[/font][font=Times New Roman]1[/font][font=宋体]个鸡蛋是不经济的，就是因为有部分时间（[/font][font=Times New Roman]T-T/N[/font][font=宋体]）被浪费掉了。[/font][/size][/color]
[color=#000000][size=4][font=宋体]    那么就可以知道，实际上，当[/font][font=Times New Roman]N[/font][font=宋体]个鸡蛋充分利用[/font][font=Times New Roman]T[/font][font=宋体]分钟的时候，所需要的时间是最短的。那么具体鸡蛋的煮法呢？[/font][/size][/color]
[color=#000000][size=4][font=宋体]    首先，我们把鸡蛋编上号：[/font][font=Times New Roman]1[/font][font=宋体]、[/font][font=Times New Roman]2[/font][font=宋体]、[/font][font=Times New Roman]3[/font][font=宋体]……[/font][font=Times New Roman]N-1[/font][font=宋体]，[/font][font=Times New Roman]N[/font][font=宋体]，[/font][font=Times New Roman]N+1[/font][font=宋体]……[/font][font=Times New Roman]m-1[/font][font=宋体]，[/font][font=Times New Roman]m[/font][font=宋体]，然后把前[/font][font=Times New Roman]N[/font][font=宋体]个鸡蛋放进锅里，等[/font][font=Times New Roman]T/N[/font][font=宋体]分钟后，把[/font][font=Times New Roman]1[/font][font=宋体]拿出来，把[/font][font=Times New Roman]N+1[/font][font=宋体]放进去；再过[/font][font=Times New Roman]T/N[/font][font=宋体]分钟，把[/font][font=Times New Roman]2[/font][font=宋体]拿出来，把[/font][font=Times New Roman]N+2[/font][font=宋体]放进去……这样，每过[/font][font=Times New Roman]T/N[/font][font=宋体]分钟，都把锅里编号最小的放进去，然后把锅外面编号最小的放进去。直到第（[/font][font=Times New Roman]m-N+1[/font][font=宋体]）*[/font][font=Times New Roman]T/N[/font][font=宋体]分钟，这时候最后一个鸡蛋已经在锅里了，这个时候把锅里编号最小的鸡蛋拿出来，把[/font][font=Times New Roman]1[/font][font=宋体]放进去；第（[/font][font=Times New Roman]m-N+2[/font][font=宋体]）*[/font][font=Times New Roman]T/N[/font][font=宋体]分钟，把锅里编号第二小的拿出来（此时编号最小的是[/font][font=Times New Roman]1[/font][font=宋体]，刚刚放进去），把[/font][font=Times New Roman]2[/font][font=宋体]放进去……这样轮换，直到[/font][font=Times New Roman]T[/font][font=宋体]分钟后，所有鸡蛋煮熟。按照这种方法煮，每个鸡蛋被煮了[/font][font=Times New Roman]N[/font][font=宋体]次，每次被煮的时间是[/font][font=Times New Roman]T/N[/font][font=宋体]，因而是最高效的。[/font][/size][/color]
[color=#000000][size=4][font=宋体]    之前我们将[/font][font=Times New Roman]M[/font][font=宋体]个鸡蛋进行了分组，实际上，如果不分组的话，按照上述的方法也是可以煮的，所需的总时间也没有变化。但是所有鸡蛋都这么折腾实在是有点累，所以首先我们[/font][font=Times New Roman]N[/font][font=宋体]个[/font][font=Times New Roman]N[/font][font=宋体]个地煮，然后剩下[/font][font=Times New Roman]N+b[/font][font=宋体]个的时候再如上操作（因为仅剩[/font][font=Times New Roman]b[/font][font=宋体]个的时候就只能一锅煮了，肯定是浪费时间的）。[/font][/size][/color]
[size=4][/size]

考虑到一般锅的容积，这是个超流水系统。:lol:

“按照这种方法煮，每个鸡蛋被煮了N次，每次被煮的时间是T/N，因而是最高效的。”
这种方法开锅的次数太多了吧。
如何做到开锅的次数最小化才有意义。

当余数为1时，楼主的方法是最优的（开锅次数及拿蛋次数最小）
未证明。

当余数不为1时，楼主的方法是不是最优的。
如：N=3,M=5.设蛋为A、B、C、D、E。
楼主方法为：（每次花费时间为T的1/3）
A、B、C
D、B、C
D、E、C
D、E、A
B、E、A
开锅4次，换蛋4次。

若改为：
A、B、C
A、B、D
A、B、E
C、D、E
C、D、E
则开锅3次，换蛋4次。

楼上高人！！
其实另一种情况是这样的：锅的容积和鸡蛋的个数有公因数，也就是am和bm，这个时候其实是可以按照a和b的情况来看的，只不过每次换的鸡蛋数是m个而已。
比如锅能装6个鸡蛋，一共9个鸡蛋要煮，这时候的策略其实是：
1、2、3、4、5、6
1、2、3、7、8、9
4、5、6、7、8、9

嗯，我们把问题改一改，改成在最短的时间内，最少换多少次才能煮熟所有的鸡蛋。
顺便得到的结论一：在这种最优策略下，隔多少时间换一次鸡蛋？
顺便得到的结论二：是不是每次更换鸡蛋的间隔都一样？
楼上已经给出了结论二，即不是每次更换鸡蛋的时间间隔都一样。那么还有一个问题：
顺便得到的结论三：在何种情况下，每次更换鸡蛋的时间是不一样的？

应该发到射虎:mellow:

[quote]原帖由 [i]水镜门生[/i] 于 2008-8-4 17:23 发表
应该发到射虎:mellow: [/quote]
之前是觉得那里全是谜语什么的，现在我也觉得应该在那里了。哪位有权限的牛人帮月月挪一下？

PM本区版主恨地无环即可

老题了，想到现在，依然不明白……

第一次听说这题~孤陋寡闻了~:shy:
下午再看 要上班了~

不好意思顶水区的那个帖了，反正是一个作者，就发在这儿了：
『      我想到有人调侃数学家，是用烧开水的例子：说烧开水有这么几步：1、把壶装满凉水；2、把装满水的壶放到炉子上；3、点火，等水开。现在如果有一壶水在炉子上，问怎么样才能把水烧开？一般人会点火，把水烧开。而数学家会把水倒掉，然后从1开始，再把壶装满水，放在炉子上，点火。原因是：数学家的思想是把未知的事物转换成已知的。虽然一壶水放在炉子上该怎么办是未知的，但是，空壶该怎么办是已知的。所以，最符合数学家作风的就是：把水倒掉，这样，未知的事物就变成已知的了。』

这个不是调侃数学家，是指的计算机程序员，而且不是调侃，对于计算机程序员来说，一个已经写成的代码是可以“代码重用”的，所以第一次已经写好了一个“装水、放去炉子、（原来还有步放柴）、点火、等水开”的程序，而第二次有一个接口为“已放在炉子上的水”（我看到的原题是一个有水的水壶）的话，倒掉水只需要一步代码。剩下的代码可以直接重用……