一个读文件的问题

冷眼看戏的Lili · 发表于 2012-2-17 05:23:04

解法帖得有点早了。俺以为至少要等到周末，好让大家有充分的时间考虑。

俺的解法（包括证明）只需不超过n-1次对换就可调整到按顺序的情况，而每次对换都能降低代价。你的方法可行

，但步数通常会大一些。

冷眼看戏的Lili · 发表于 2012-2-17 22:52:17

朋友们可思考一下这证明方法，俺将在星期日贴出那寥寥数语的答案。

色盲 · 发表于 2012-2-18 09:59:33

大家讨论得好高深，我都不敢吭声了哈

首先感谢楼主出的题，也感谢Lili的idea和contribution. 我数学不好，但是第六感觉这题很好玩，乐见大家讨论出个结果。

我是觉得在讨论问题的时候有理解上的不一致或者观点上不同都很正常，大家不必因为观点不一致陷入人身攻击，那就没意思了。都是人不是神，每个人的见识其实都有限，不必动不动给人盖帽子。多留些精力放在问题本身不是很好么。

一起讨论，相互学习，大家才会有收获，也更有乐趣。

这个题，坦率地讲我不敢解

，只能提一些表浅的意见。我的感觉是，按楼主的意思，每次读文件必须从磁带头开始，那么读一个文件花的时间不仅和该文件的长度相关，而且还和该文件的位置相关，因为读到文件fn的文件尾必须“路过”排在它前面的所有文件。但是如果按照题意求出读所有文件的总代价的话，似乎会遇到理解上的困难。比如，怎样理解读到某文件的概率p？由于磁带机必须从头读的特点，如果要求出读完所有文件的总时间，那么必须每个文件都“读”到，而且除了排在最后的那个文件，所有文件都要被读到不止一次。但题目貌似给出了读到文件fn的概率p……那这个p如何定义呢？总代价又是什么意思呢？是读m次直到所有文件都被至少读到一次花的总代价呢还是随机读m次，无论是否读到所有文件花的总代价呢？或者说所有文件都读一遍（但这似乎就跟概率p无关了）需要花的总代价呢？个人理解，“总代价”作为一个变量，如何定义是出题者的事情，但无论按定义总代价与花费的总时间的关系如何，这里的p和“总代价”都需要有一个严谨的definition。不知我理解的是不是正确，求教。

原贴：

文章来源: 冷眼看戏的Lili® 于 2012-2-16 2:42:2 (北京时间: 2012-2-16 15:42:2)
标题：太好了！

色盲JJ要回来？

太好了！她是到美国来，还是现在从内地能上顶顶了？前不久俺在那边还上不了呢？

www.ddhw.org---

据说这世界是彩色的？

冷眼看戏的Lili · 发表于 2012-2-18 12:25:23

热烈欢迎色盲jj回脑坛来！

这一个多星期来累死俺了。坛上来了这么一个“高手”，让俺费多少口舌、挨多少骂

（貌似Hu大哥已经删了些骂得太难听的帖子了）！俺老师让坚持（老师说，得七个回合），所以耐着性子发了几十上百个帖子，但愿能像以前个别朋友那样，水到渠成，对方能翻然醒悟，俺也就没白费功夫。

那新新大哥，不知道他到哪里去玩儿了，也不对自己贴的瓶球问题作个了结。

动脑筋 · 发表于 2012-2-18 20:06:19

冷眼看戏的Lili · 发表于 2012-2-19 08:18:19

对任一个不符合顺序（按p_i/f_i从大到小）的排列，依1, 2, …, n-1之次序，从第一位起逐位用对换的办法使之到位。至多共需n-1次对换即可全部到位。

“最小代价”的证明. 假设存在一个不符合顺序的排列具“最小代价”。它必至少有一对相邻位逆序，对调这相邻两位必可降低代价（（p_i/f_i）<（p_j/f_j）意味着f_jp_i-f_ip_j<0 ），这与其“最小代价”矛盾。故只有符合顺序的排列才具“最小代价”。

色盲 · 发表于 2012-2-19 10:17:32

多日不见，想死大家了

www.ddhw.org---

据说这世界是彩色的？

		自动登录	找回密码
密码			立即注册

动态微博

一个读文件的问题

回复：回复：一个读文件的问题[:-Q]

回复：回复：回复：一个读文件的问题[:-Q]

[:&][:-K]好热闹啊[:-D]

热烈欢迎色盲jj回脑坛来！[@};-][@};-][@};-]

色盲MM好 [>:D<][>:D<][>:D<][>:D<]

方法与证明

Lili动脑筋MM好！大家好！！[>:D<][>:D<][>:D<]