标题:
关于煮鸡蛋问题的广而推之
[打印本页]
作者:
小女秦怜月
时间:
2008-8-4 12:01
标题:
关于煮鸡蛋问题的广而推之
首先是煮鸡蛋问题，这是一道小学一年级的数学题，原帖因为比较搞笑所以在水版：
http://xycq.moddiy.com/forum/thread-174441-1-1.html
为了方便不想看上面这个帖子的人，月月在这里把问题重复一下：煮1个鸡蛋需要6分钟，现在问煮6个鸡蛋要多长时间。
这个题目没有给出锅子的容积，所以我个人认为标准答案是6分钟，也就是假设锅子的容积可以装6个鸡蛋，并且假设不管多少个鸡蛋一起煮，所需时间不变。那么上面这样恶搞完以后，月月开始很严肃地思考：如果
我们把问题推广化：假设我们有
M
个鸡蛋，每个鸡蛋煮
T
分钟后可以熟，而锅的容积是
N
个鸡蛋（
M
≥
N
），问最少多长时间可以煮熟，而且在最短时间内的煮熟方法。
首先还是要定几条前提条件的，这样就杜绝了我这样爱刨根问题钻牛角尖的人。前提条件一是：忽略水越煮越少的问题；前提二：不管是分几次煮的，只要煮够
T
分钟，鸡蛋就可以熟；前提三：忽略把鸡蛋拿进锅子和拿出锅子的时间；前提四：时间可以细分，比如我们可以精确测量出
1/n
这种很细微的时间；前提五：鸡蛋是一模一样的，而且该系统是在完全理想的情况下进行的，忽略诸如大气压变化、空气温度变化、火焰大小变化等影响因素。
那么，第一个问题很好回答，最小时间一定是
t=M*
T
÷
N
。麻烦的是，在
t
时间内，我们如何煮熟
M
个鸡蛋。
首先，我们用
M
除以
N
，假设商是
a
，余数是
b
，也就是说，
M=a*
N+b
。我们把
M
个鸡蛋分成两部分，第一部分是（
a-1
）*
N
个，第二部分是
N+b
个。可见，
N+b
介于
N
和
2N
之间。当然，如果
M
本身就介于
N
和
2N
之间，那就意味着
a=1
，所以第一部分是
0
个鸡蛋，第二部分是
M
个鸡蛋。第一部分的鸡蛋比较好煮，只要
N
个
N
个地煮就可以了，因为锅子被充分应用了，所以热量没有浪费，这样煮出来的时间一定是最短的，最终需要（
a-1
）*
T
分钟。
出于简便，我们把第二部分的鸡蛋数设为
m
。显而易见地，如果锅子里无论什么时候的鸡蛋数都是最大容积数，也就是
N
，那么，所用的时间一定是最短的。也就是说，在
T
分钟内同时煮熟
N
个鸡蛋，是最省时间的（也就是按照第一部分的煮法）。在这种模式下，平均每个鸡蛋煮熟的时间是
T/N
。但是实际上通过常识我们可以知道，煮熟
N
个鸡蛋和煮熟
1
个鸡蛋所用的时间是一样的。之所以一锅只煮
1
个鸡蛋是不经济的，就是因为有部分时间（
T-T/N
）被浪费掉了。
那么就可以知道，实际上，当
N
个鸡蛋充分利用
T
分钟的时候，所需要的时间是最短的。那么具体鸡蛋的煮法呢？
首先，我们把鸡蛋编上号：
1
、
2
、
3
……
N-1
，
N
，
N+1
……
m-1
，
m
，然后把前
N
个鸡蛋放进锅里，等
T/N
分钟后，把
1
拿出来，把
N+1
放进去；再过
T/N
分钟，把
2
拿出来，把
N+2
放进去……这样，每过
T/N
分钟，都把锅里编号最小的放进去，然后把锅外面编号最小的放进去。直到第（
m-N+1
）*
T/N
分钟，这时候最后一个鸡蛋已经在锅里了，这个时候把锅里编号最小的鸡蛋拿出来，把
1
放进去；第（
m-N+2
）*
T/N
分钟，把锅里编号第二小的拿出来（此时编号最小的是
1
，刚刚放进去），把
2
放进去……这样轮换，直到
T
分钟后，所有鸡蛋煮熟。按照这种方法煮，每个鸡蛋被煮了
N
次，每次被煮的时间是
T/N
，因而是最高效的。
之前我们将
M
个鸡蛋进行了分组，实际上，如果不分组的话，按照上述的方法也是可以煮的，所需的总时间也没有变化。但是所有鸡蛋都这么折腾实在是有点累，所以首先我们
N
个
N
个地煮，然后剩下
N+b
个的时候再如上操作（因为仅剩
b
个的时候就只能一锅煮了，肯定是浪费时间的）。
作者:
Maxwell
时间:
2008-8-4 12:09
考虑到一般锅的容积，这是个超流水系统。
作者:
墨叶
时间:
2008-8-4 12:26
“按照这种方法煮，每个鸡蛋被煮了N次，每次被煮的时间是T/N，因而是最高效的。”
这种方法开锅的次数太多了吧。
如何做到开锅的次数最小化才有意义。
作者:
墨叶
时间:
2008-8-4 12:45
当余数为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次。
作者:
小女秦怜月
时间:
2008-8-4 13:07
楼上高人！！
其实另一种情况是这样的：锅的容积和鸡蛋的个数有公因数，也就是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
嗯，我们把问题改一改，改成在最短的时间内，最少换多少次才能煮熟所有的鸡蛋。
顺便得到的结论一：在这种最优策略下，隔多少时间换一次鸡蛋？
顺便得到的结论二：是不是每次更换鸡蛋的间隔都一样？
楼上已经给出了结论二，即不是每次更换鸡蛋的时间间隔都一样。那么还有一个问题：
顺便得到的结论三：在何种情况下，每次更换鸡蛋的时间是不一样的？
作者:
水镜门生
时间:
2008-8-4 17:23
应该发到射虎
作者:
小女秦怜月
时间:
2008-8-4 17:45
QUOTE:
原帖由
水镜门生
于 2008-8-4 17:23 发表
应该发到射虎
之前是觉得那里全是谜语什么的，现在我也觉得应该在那里了。哪位有权限的牛人帮月月挪一下？
作者:
水镜门生
时间:
2008-8-4 18:00
PM本区版主恨地无环即可
作者:
小女秦怜月
时间:
2009-2-26 18:11
老题了，想到现在，依然不明白……
作者:
liduxing
时间:
2009-3-4 13:53
第一次听说这题~孤陋寡闻了~
下午再看 要上班了~
作者:
金圭子
时间:
2009-3-5 16:20
不好意思顶水区的那个帖了，反正是一个作者，就发在这儿了：
『 我想到有人调侃数学家，是用烧开水的例子：说烧开水有这么几步：1、把壶装满凉水；2、把装满水的壶放到炉子上；3、点火，等水开。现在如果有一壶水在炉子上，问怎么样才能把水烧开？一般人会点火，把水烧开。而数学家会把水倒掉，然后从1开始，再把壶装满水，放在炉子上，点火。原因是：数学家的思想是把未知的事物转换成已知的。虽然一壶水放在炉子上该怎么办是未知的，但是，空壶该怎么办是已知的。所以，最符合数学家作风的就是：把水倒掉，这样，未知的事物就变成已知的了。』
这个不是调侃数学家，是指的计算机程序员，而且不是调侃，对于计算机程序员来说，一个已经写成的代码是可以“代码重用”的，所以第一次已经写好了一个“装水、放去炉子、（原来还有步放柴）、点火、等水开”的程序，而第二次有一个接口为“已放在炉子上的水”（我看到的原题是一个有水的水壶）的话，倒掉水只需要一步代码。剩下的代码可以直接重用……
欢迎光临 轩辕春秋文化论坛 (http://xycq.org.cn/forum/)
Powered by Discuz! 5.0.0
