关于煮鸡蛋问题的广而推之 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#1

发表于 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


	代王监管使枢密直学士山南西道节度使 ★

组别	诸侯
级别	征东将军
好贴	4
功绩	1845
帖子	5799
编号	622
注册	2004-7-7

#2

发表于 2008-8-4 12:09 资料文集短消息只看该作者

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

[广告] 《精忠报国岳飞传完整版》火热发布


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#3

发表于 2008-8-4 12:26 资料个人空间短消息只看该作者

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

[广告] 真诚支持说岳，携手共创辉煌


	墨叶


	★★★★ 节度留后虎豹骑

组别	虎豹骑
级别	大将军
功绩	359
帖子	23258
编号	97330
注册	2006-12-26
家族	轩辕少林寺

#4

发表于 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次。

[广告] 《精忠报国岳飞传完整版》火热发布


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#5

发表于 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

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

[广告] 真诚支持说岳，携手共创辉煌


	水镜门生 (虾仁生煎)


	许国公河北东路经略使 ★★★★

组别	经略使
级别	大将军
好贴	6
功绩	2628
帖子	22586
编号	52409
注册	2005-11-4
来自	五谷轮回之所
家族	肉肉门

#6

发表于 2008-8-4 17:23 资料个人空间短消息只看该作者

应该发到射虎

[广告] 真诚支持说岳，携手共创辉煌


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#7

发表于 2008-8-4 17:45 资料文集短消息只看该作者

QUOTE:

原帖由 水镜门生 于 2008-8-4 17:23 发表
应该发到射虎

之前是觉得那里全是谜语什么的，现在我也觉得应该在那里了。哪位有权限的牛人帮月月挪一下？

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	水镜门生 (虾仁生煎)


	许国公河北东路经略使 ★★★★

组别	经略使
级别	大将军
好贴	6
功绩	2628
帖子	22586
编号	52409
注册	2005-11-4
来自	五谷轮回之所
家族	肉肉门

#8

发表于 2008-8-4 18:00 资料个人空间短消息只看该作者

PM本区版主恨地无环即可

[广告] 真诚支持说岳，携手共创辉煌


	小女秦怜月 (~~月月~~)


	★★★

组别	轩辕公主
级别	牙门将军
好贴	6
功绩	163
帖子	593
编号	284977
注册	2008-7-3

#9

发表于 2009-2-26 18:11 资料文集短消息只看该作者

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

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	liduxing

组别	士兵
级别	讨逆将军
功绩	6
帖子	631
编号	248418
注册	2007-12-11
家族	聚贤山庄

#10

发表于 2009-3-4 13:53 资料短消息只看该作者

第一次听说这题~孤陋寡闻了~

下午再看要上班了~

[广告] 《精忠报国岳飞传完整版》火热发布


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#11

发表于 2009-3-5 16:20 资料文集短消息只看该作者

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

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

[广告] 真诚支持说岳，携手共创辉煌