O興~
 
« 上一篇: 最大乘积 下一篇: 求多个字符串的最大公共子串 »
我很懒的 @ 2007-07-18 11:57

    这个问题来自UVA 11109,模型大概是这样的:由于液体对杯壁有一定的附着力,所以既使把杯子倒过来,还是有一定体积(设它为Vr)的液体是流不出来的。因此洗杯子的流程大概是这样(见图1):

一开始杯子里有Vr体积的咖啡,是怎么也倒不出来的。
1. 加入一定量的水,摇荡均匀,成为稀释的咖啡溶液。
2. 尽量倒出咖啡溶液。最后还是有Vr体积的溶液倒不出,但是杯中咖啡的量已经减少了。
3. 反复做步骤1和2,直到咖啡的量足够少。


图1 洗杯子的示意义图

    当然,这只是比较理想化的状态。现实中还有很多别的因素,但是在这里暂时乎略。
    可以想象,在步骤1中加的水越多,溶液的浓度就越小,在步骤2后剩下咖啡量就越少。但是我们要讨论的是水有限的情况,如何用有限的水把杯子洗得最干净。

    假设我们把步骤1和2重复做了3次,也就是加了3次水。设总共只有体积Vw的水,而且它远远装不满3满杯。再设3次分别倒入的水的体积为Vw1、Vw2和Vw3,并且Vw1 + Vw2 + Vw3 = Vw。那么洗完3次后最终的溶液浓度就是:


    所以要使浓度最小,就要使(Vr + Vw1)(Vr + Vw2)(Vr + Vw3)最大。我在这篇文章里已经说过,既然Vr + Vw1、Vr + Vw2和Vr + Vw3的和是不变的,那使要它们的积最大,就要使这3个数相等,即Vw1 = Vw2 = Vw3 = Vw / 3。由此我们得到了第一个结论:

    用有限的水洗n次杯子,每次到入的水量都相同最后洗得才最干净。

    刚才是洗3次的情况。如果洗4次呢,最终的浓度是:



    最小值时Vw1 = Vw2 = Vw3 = Vw4 = Vw / 4。而洗3次就相当于洗4次时最后一次没有倒水,也就是Vw1 = Vw2 = Vw3 = Vw / 3,Vw4 = 0,既然4次的水量不相同,那么最终的浓度肯定没要达到最小。因此我们得到了第二个结论:

    用有限的水洗杯子,洗的次数越多,能够洗得越干净。




评论 / 个人网页 / 扔小纸条
* 昵称

已经注册过? 请登录

新用户请先注册 以便能显示头像及追踪评论回复

Email
网址
* 评论
表情
 


 

分类小组论坛
杂谈 , 娱乐、八卦 , 文学、艺术 , 体育 , 旅游、同城 , 象牙塔 , 情感 , 时尚、生活 , 星座 , 科技

请注意遵守中华人民共和国法律法规, 如威胁到本站生存, 将依法向有关部门报告, 同时本站的相关记录可能成为对您不利的证据.

相关法律法规
全国人大常委会关于维护互联网安全的决定
中华人民共和国计算机信息系统安全保护条例
中华人民共和国计算机信息网络国际联网管理暂行规定
计算机信息网络国际联网安全保护管理办法
计算机信息系统国际联网保密管理规定

日历
网志分类
· 所有网志
· program
· 未分类
站内搜索
友情链接
· 歪酷博客
· 管理我的Blog
· jamie
· feemi
· lyrist
· tata
· allen
· richard

订阅 RSS

0081345

歪酷博客