一个读文件的问题

fov22 · 发表于 2012-2-14 10:45:10

磁带上有n个文件，时间长度f1，f2，。。。fn。每个文件被读取的概率分别为p1，p2，。。。pn，读取某一个文件时必须从头读起，所花费的时间则是从磁带头到该文件末。例如，读取第3个文件需要总时间为第1，第2，第3个文件时间长度的和，现在定义读取一个文件的代价为读取的概率p乘以读取该文件需要的总时间。试问：

如何排序这n个文件，使得总代价最小？（有人提出按照笔直fi/pi进行排序，如果赞同，请证明）

本贴由[fov22]最后编辑于：2012-2-15 0:57:16

冷眼看戏的Lili · 发表于 2012-2-14 21:24:11

这是“小题”还是“难题”？有更“难”更“猛”的(楼主自己手里有解的)题吗？

注：引号中为楼主原先用词。

本贴由[冷眼看戏的Lili]最后编辑于：2012-2-14 14:43:44

冷眼看戏的Lili · 发表于 2012-2-14 23:58:20

楼主究竟有没有自己手里有解、但又不“小”的题？

fov22 · 发表于 2012-2-15 01:17:14

你会解了么这题是原创
考虑到3x+1 特别猛你做不成，这次来个简单点的

冷眼看戏的Lili · 发表于 2012-2-15 04:07:30

请注意，俺说的是你自己手里有解的“猛”题“难”题。“3x+1”是著名的冰雹猜想，你会证明吗？你自己不会证，还有脸再次拿出来说事（哦，对不起，俺忘了你早就把脸都丢尽了）？俺以前早已说过，世上俺不会做的题多着呢！你怎么不把哥德巴赫猜想拿出来唬人？

你至今没拿出一个不“小”（按你的定义：凡是Lili能解的题，事后都称为“小”题，所以，.....

）的题来。是你根本就没有不“小”的题吧！

你敢不敢贴出一个你自己手里有解（无论解是不是抄来的、题是不是原创）的题，并当场就宣布这题是不“简单”的、是不“小”的，或是“难”的、“猛”的？不要象以往那样，等别人解完了，再自我解嘲地说这是“小题”，“下回再给个难的”。这不是让人看你笑话吗？

至于你贴在本楼的题，确是十分简单，只是学校课堂上的一个例题或留给学生的一个习题而已，它也可能会出现在趣味数学的小册子里。既然你自己已说它“简单”，那为什么还拿它来问俺“你会解了么”？多么不“过瘾”啊！www.ddhw.com

你说这题是原创，得打个问号！会不会又是从什么地方抄来的？略加篡改解释，改得不伦不类、释得不清不楚。“原创”就创在这改得不伦不类、释得不清不楚。例如，你那“笔直......”是不是应该写成“由小到大的顺序对......”？你贴的问题的表述中还有若干不妥的（是你原创的？）地方。你的那“总代价”是不是某一个随机变量的数学期望？请回答，以便别人答题。

冷眼看戏的Lili · 发表于 2012-2-15 05:12:19

俺一向欢迎新手上脑坛来，您可查查脑坛的历史。但此人可不是一般的“新手”，一上坛来就咬人、就胡搅，您可再看看新新大哥贴出瓶球问题后这“新手”的表演。这些天来，俺曾给他机会下台阶，可他不领情，非得死磕到底。您说的“饶一次”，您得先问问他愿意接受不，这三个字本身，也许他就会认为是对他的侮辱。

都是老朋友了，您知道俺的脾气，谁先对俺不客气，俺也不会对他客气。至于“专家”一说，俺说过不至一次：“世上俺不会做的题多着呢！”，免称“专家”。

朋友告诉俺，楼主此帖贴出同时，他自己还有一个不客气的跟贴，大概是被斑竹删了。那跟帖正好说明他贴此题的目的。他在这楼内，不是还在搅吗！他要是真心实意地跟大家一起贴题解题，俺双手欢迎！

至于您说的“不要说你学好了这呀那呀以后再来挑战我”，俺有些话那是针对那自吹已经在“玩勒贝格积分”的狂妄且以此作为咬人的本钱而说的。既然不客气了，哪还顾绅士风度？不压邪，难道就让邪在脑坛泛滥？

谢谢您的关心，也请谅解！难得有您出来公正一下，建议找准矛盾的首发处，您发贴劝劝他。

冷眼看戏的Lili · 发表于 2012-2-15 07:31:28

“饶一次”兄，看清了没有（http://www.topchinesenews.com/readpost.aspx?topic_id=9&msg_id=8922&level_string=0z04z01z01&page=1 和

http://www.topchinesenews.com/readpost.aspx?topic_id=9&msg_id=8922&level_string=0z04z01z01z01&page=1）？

这位22说的话，哪一句有事实根据？这是位什么样的“新手”？脑坛应该怎么办？请他解释“总代价”是不是某一个随机变量的数学期望，俺有错吗？这位22为什么不敢正面交换意见讨论问题，而只会谩骂和放录音带似的喊我就是对、你就是错！

冷眼看戏的Lili · 发表于 2012-2-15 09:02:12

说得好：“需要彼此尊重”。他连对“中国人”这个整体都不尊重！您看到了没有？您对此感觉如何？反正俺是中国人，不知道您是不是。

冷眼看戏的Lili · 发表于 2012-2-15 09:04:37

请描写（或定义）一下这个随机变量。

fov22 · 发表于 2012-2-15 09:13:44

你看了我的修改没有？

首先我本来就觉得你非要把这个和概率扯上就觉得很牵强。

如果要定义随机变量，那么就是这样，对于一个给定的排列，X是从头到某一文件的长度。以f1=5，f2=10,p1=0.3,p2=0.7为例

对于f1,f2这个排列，X=5 p=0.3, X=15,p=0.7

总代价就是E[X],即X的期望

冷眼看戏的Lili · 发表于 2012-2-15 09:25:26

挺好！随机变量有了，它的分布你也用例子局部地说明了。那回过头来看看原帖。文中“现在定义读取一个文件的代价为读取的概率p乘以读取该文件需要的总时间。”。发现毛病了吗？

本贴由[冷眼看戏的Lili]最后编辑于：2012-2-15 1:26:28

冷眼看戏的Lili · 发表于 2012-2-15 09:48:25

“首先我本来就觉得你非要把这个和概率扯上就觉得很牵强。”??? 你觉得“牵强”正是因为你概念模糊、没有理清楚。一步一步来，就是为了让你清楚起来。要不然，又要把“逆耳”衷言拒之门外。

这是一个随机优化问题，当然跟概率有关，何况是你自己在题中就把它“和概率扯上”的！

冷眼看戏的Lili · 发表于 2012-2-15 09:57:47

为了帮助你思考，再问你一个问题：那“总代价”是阅读几个文件的代价？

fov22 · 发表于 2012-2-15 10:00:56

是在不懂你说的毛病的地方，也不知道你引出数学期望，随机变量的用意。

如果非要咬文嚼字，那就应该是 “读取某一文件的代价为：读取该文件的概率，乘以读取该文件所需要的总时间。 ” 读取一个文件的总时间已经在题中定义了。

lili你扯了大半天还说我“概念不清”，我概念非常清晰，你的问题也逐一回答了，你向来口气傲慢，还找托来说要“尊重”？

你到底觉得那里有毛病，直接把你认为的说法说出来，或者贴出个解法，或者贴出个出处，而不要再节外生枝问一些无关紧要的问题。

fov22 · 发表于 2012-2-15 10:03:31

所有文件的，即n个文件的代价的和

冷眼看戏的Lili · 发表于 2012-2-15 10:19:32

"还找托来说要“尊重”" ____ 啊，天哪！连“饶一回”都成了俺的“托”了。荣幸荣幸，俺“托”满天下。哈哈！

"我概念非常清晰" ____ 请不要过于自信（俺记得，以前曾这样提醒过你），先看看楼下俺的新提问：那“总代价”是阅读几个文件的代价？也许会对你有所帮助。

据说，喝醉了酒的人大多都嘟囔“我~—~没~—~没~醉”。

fov22 · 发表于 2012-2-15 10:21:36

回复过了，这版面设计的回帖多了很难看清。我说了，总代价就是所有文件的代价，即n个文件的代价的和

冷眼看戏的Lili · 发表于 2012-2-15 10:37:27

这就可以找到你出的题有毛病的症结。请不要不高兴，俺说你这里就犯糊涂了！题目问的应该是：“按所给的概率分布，随机地阅读一个文件，所花代价这个随机变量的数学期望是多少？如何排列这些文件，使得这期望值最小？”。你文中“现在定义读取一个文件的代价为读取的概率p乘以读取该文件需要的总时间”也是有毛病的，它应该是“现在定义读取一个文件的代价为读取该文件需要的总时间”，即，去掉那“读取的概率p乘以”（俺已在上面帖中加黑让你重点注意）。最后那“总代价”也应改为“平均代价”，或更确切地，“代价的数学期望”。

本贴由[冷眼看戏的Lili]最后编辑于：2012-2-15 2:52:30

冷眼看戏的Lili · 发表于 2012-2-15 10:41:41

“除非因为某些事情被惹急了”----您是因为哪些事情惹急了他？

本贴由[冷眼看戏的Lili]最后编辑于：2012-2-15 14:22:14

冷眼看戏的Lili · 发表于 2012-2-15 10:43:33

请看底下。

fov22 · 发表于 2012-2-15 10:51:45

你怎么随意篡改题目？我出的题目被你改成个简单题了。你就是要问也问“如何排序，使得读取一个文件的的代价的期望最小”？这个问法和我的题目是一样的。

你到底有没有看我给的例子啊

以f1=5，f2=10,p1=0.3,p2=0.7为例

对于f1,f2这个排列，总代价就是5*0.3+（5+10）0.7

对于f2,f1这个排列，总代价就是10*0.7+（5+10）0.3

于是f2，f1这个排列的总代价最小，所以应该以f2，f1排序。

换乘你的语言，就是按照f2，f1的顺序排列，随机读取一个文件的代价的数学期望最小。请看清楚我的问法，你就是把我的问题翻译了一下而已。

快把你的“寥寥几语”说出来

fov22 · 发表于 2012-2-15 10:58:46

我认为你就是在故意找茬。请再读一遍我给你的f1，f2，p1，p2的具体例子，如果按照f1，f2这个排列，读取f1的代价是5*0.3，根据我的定义，读取的概率是p1=0.3，读取的总时间是5。一点问题都没有，你自己僵化思维，非要翻译成你的概率期望的语言才能理解。让外人来看，肯定都是你在五中挑刺，不知道你是故意还是无意。你快把你的“寥寥几语的”的解答说出来

冷眼看戏的Lili · 发表于 2012-2-15 11:07:52

刚才急于发出去，漏打了一句花。抱歉！现添上了。还有什么问题吗？

表面看，“计算结果”一样，貌似“一样”。所以俺说你的表述有毛病。但若深究，问题还有。例如，你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

冷眼看戏的Lili · 发表于 2012-2-15 11:20:01

至于证明，别着急。你手里有证明吗？要有的话，可以咱们都把证明用电邮发给斑竹。到适当时候一起公布。如何？你要是不信任斑竹的话，俺可先公布证明中关键的两个字。现在还是先把问题理清了，让大家玩几天。俺早就说过，考查Lili智商是件毫无意义的事。发帖解题是为了大家一起增进知识、寻求乐趣。

fov22 · 发表于 2012-2-15 11:20:21

从你问的问题就看出你还是没理解的我题目的意思

我推测你把以下几个概念混淆了：

1.读取一个文件的总时间：从头读到该文件末所需的时间

2.读取一个文件的代价：读取的该去乘以读取的总时间

3.某一排列的总代价 : n个文件的代价的总和。

你问读文件的顺序，就好比是问，3个苹果分别2，3，4元，以什么顺序买最便宜？

注意，对于某一个已定的排列，读取任何一个文件的代价是常数，就好比2元一样。当然，在没定排列的情况下，读取一个文件的代价是变量。

希望你逐字的看我写的题目以及f1，f2的例子。你的概率期望的问法和我的问法是等价的。

冷眼看戏的Lili · 发表于 2012-2-15 11:21:24

你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

fov22 · 发表于 2012-2-15 11:22:50

好啊我也赞同憋几天在说答案。你先说下那个按比值排列是正解么

fov22 · 发表于 2012-2-15 11:28:17

每次读取一个文件，磁带会自动从头开始。所以对已一个给定的排序，什么顺序读总代价都是一样的。假设按次序的文件分别是f1.f2...fn, 那代价就是p1*f1+p2*(f1+f2).....你按什么顺序都是这个值，比如你读完f1,磁带就回到开始的地方，再读f2需要花费的时间是f1+f2, 清楚了么

冷眼看戏的Lili · 发表于 2012-2-15 11:41:35

你怎么转不过弯来呢。请冷静地想一想。在赋予“读取第i个文件”这一事件以概率pi前，一旦排列次序（它跟概率也无关）确定，“读取第i个文件”的代价就已经可以定义了，那就是从头到此文件尾的长度。它跟随后赋予的概率无关！只是在随机抽读一个文件时，这第i个文件可能被抽到阅读，也可能抽到别的文件。这才用一个概率分布来描写各个文件被抽到阅读的机会大小，然后再用这个概率分布来计算“平均”代价。这“平均”代价是指“阅读一个文件”的，而不是什么阅读n个文件的。

冷眼看戏的Lili · 发表于 2012-2-15 11:52:46

是按比例排列。但你的比例有一点不方便（需要多说一、两句话），那就是：当某个概率为零时，处在分母就需特别处理。何不如倒过来，每个文件的长度都不为零（否则，就不成其为文件了），把它放在分母。这样，就按这比例从大到小的顺序来排列这些文件即可。

fov22 · 发表于 2012-2-15 11:53:33

^{你怎么这么老顽固呢，年纪多大了啊。你能不能看看全仔细我的题目。}

^{我是像你这样定义“代价”的么？我的定义代价=总时间乘以概率，}

^{你自己编的“代价=总时间”}

是我在出题还是你在出题？

冷眼看戏的Lili · 发表于 2012-2-15 12:03:22

如果一次要读所有n个文件，那跟你给的概率有什么关系？请想清楚了：这题中要极小化的“代价”，是读n个文件的“总代价”，还是抽读一个文件的“平均代价”。

冷眼看戏的Lili · 发表于 2012-2-15 12:44:58

你表述的不妥之处，恐怕就跟这有关。你的“代价=总时间乘以概率”的定义就是不妥的。读取某个文件的代价是由读取所花时间确定的，跟概率无关。抽到它，读它，就花它的代价。抽不到它，就不花它那代价。抽到哪个就花哪个的代价。抽只抽一个，但不一定抽到哪个。所以，抽读一个文件的代价是随机的，这就是你已经认识到的随机变量。题中需要优化（极小化）的“代价”，就需要按概率分布来算那代价的加权平均，这就是那数学期望。所以，你的表达的不妥，是在于把原本应该在计算加权平均时使用的权（即概率）提前放到“代价”的定义中去了。用你的“定义”，是无法按概率论原理来解释你那“读n个文件”和那“总”字的。

是你出题，你可以杜撰。但别人可以说你的杜撰不符世界公认的概率论。所以，先前俺建议你去读一读经典教科书。当然，你也可以试着去发展你自己的新学说新学科。放在家里自己欣赏，没人会干涉你的自由；但要放到公众场合，就要经得起推敲。

fov22 · 发表于 2012-2-15 13:31:16

要极小化我定义的总代价，这题概率可以换成金钱，比如读某一文件需要总时间单价为 pi元，读第3个文件必须付 p3 乘以前3个文件的时间和。
求排列使得读所有文件花销最小
所以我开始就认为此题与概率无关。

冷眼看戏的Lili · 发表于 2012-2-15 14:45:38

那也可以，把你这新的表达，再在词句上稍作调整，完整地帖出来，供大家考虑。

按你的思路，另外一个办法，也是完全抛开概率：一个群体中有百分之100pi的人调读第i个文件，这部分人的局部总代价为............。这个模型就跟概率无关了。其解法和证明不变。

初学概率的人要注意，一旦用了概率概念和词语，就得遵循概率论的方法和规则。千万不要把一点半点概率论的词语拿到别的类型问题上作装饰品。

俺上面说的这个非概率的模型，也可以随机化，使之成为一个概率论问题。那就是：从这群体中随机地抽取一个人，............。

好啦，俺没说你在这个问题上“错”了，而只是说“表达有毛病”，有所“不妥”。这个问题本身，还是很有意思的，供大家思考把玩吧。如果要俺的证明方法，过几天俺帖出，可让坛上朋友有时间思考。你想什么时候帖你的证明，请便。

顺便说一下：最好加上“pi的总和为1” 的陈述。

husonghu · 发表于 2012-2-16 09:47:13

近来很忙,连和大家打个招呼都少. 本觉坛上一切正常 --- 我一直喜见热闹, 尤其是学术(解题)上的争论. 可是好象这气氛又推动我不得不露个脸. 那好, 我说: 一如既往, 脑坛象是茶馆, "来的都是客", 我无心无能也无权限制任何网友. 更何况我相信人心向善, 误解人冤枉人多不好. 在我看来, 很多不高兴本是可以避免的. 所以, 只要没有脏字骂人字在坛面出现,我一般都不会删贴的. 任何贴, 娱人也好, 让人评判也好, 都有它的价值. 要是大家愿意斗嘴, 我倒是宁愿大家当作我这版主不存在为好, 呵呵.

色盲MM 要回来了, 有她招呼大家,我就更省事了

冷眼看戏的Lili · 发表于 2012-2-16 10:42:02

色盲JJ要回来？

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

冷眼看戏的Lili · 发表于 2012-2-16 11:53:59

“饶一次”兄，不要瞎扣文革帽子好不好，那“与人斗其乐无穷”好像并不是文革遗风（那只是个别人士的多年嗜好，文革中广大老百姓并没有觉得乐），这脑坛也跟政治无关。俺理解您发帖的心情，憋着一口气，出了也就舒坦了。以前俺说话冲了些，多有得罪，俺赔个不是，行了吧。您怕弄得就俺一个人玩脑坛，谢谢您好心劝导，还盼您大力相助。您不陪吵嘴，光陪发帖解题还不成吗？免得坛上人少不热闹。楼顶的题还没有人来给出证明，您大胆试一试、玩一玩。其他空着的题您也做做。脑坛元老了，再为脑坛作点贡献吧。

NN师兄，无论如何，您看俺面上，就别再说什么了，要不然，就都是俺的罪过了。和谐和谐，大家都换拖鞋。

冷眼看戏的Lili · 发表于 2012-2-16 23:43:24

老坛友过于谦虚了！真心想让脑坛兴旺，您就多出题多解题。要是都像您现在这样，潜着水，偶而穿着马甲冒个泡，说点“题目以外的东西”，这脑坛能兴旺吗？

往楼顶看，头三帖都是围绕出题解题，没有出圈。恰恰是第四帖（那是谁的帖？），来了个题外音。要劝架拉偏架，到打着架的地方去劝拉呀。您这不是在让别人“有所困惑”了吗！

俺在明处，您在暗处，虽然不犯版规，但要是脱了马甲直面交流，以老坛友身份说话，您的帖子不就更有说服力吗？

直说了，俺不喜欢那种说话阴阳怪气的。

fov22 · 发表于 2012-2-17 04:49:29

哎竟然没人解，是论坛没人呢还是都不懂数学？我自己解了

按照有按照比值pi/fi的排列。对于任何的其他排列，可以找到存在相邻的2个文件的笔直是反序，可以证明顺序的代价小于乱序。

对于一般的情况，有乱序可以通过逐次调整相邻的2个乱序的文件，最终化为顺序。

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

动态微博

一个读文件的问题

欢迎贴新帖！

回复：一个读文件的问题

回复：一个读文件的问题

回复：回复：一个读文件的问题

回复：Lili是这里的老坛友了，能不能饶人家新朋友一次？

“饶一次”兄，看清了没有?

回复：我都看得清清楚楚

回复：一个读文件的问题

回复：回复：一个读文件的问题

回复：回复：回复：一个读文件的问题

是你自己在题中就把它“和概率扯上”的呀！

回复：是你自己在题中就把它“和概率扯上”的呀！

回复：回复：回复：回复：一个读文件的问题

回复：回复：是你自己在题中就把它“和概率扯上”的呀！

回复：回复：回复：回复：回复：一个读文件的问题

回复：回复：回复：回复：回复：回复：一个读文件的问题

这就可以找到你出的题有毛病的症结。

都看清楚了吧！说您是俺的“托”。[:))]

请看底下。

回复：这就可以找到你出的题有毛病的症结。

回复：回复：这就可以找到你出的题有毛病的症结。

刚才急于发出去，漏打了一句花。抱歉！现添上了。

回复：回复：这就可以找到你出的题有毛病的症结。

回复：刚才急于发出去，漏打了一句花。抱歉！现添上了。

你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

回复：回复：回复：这就可以找到你出的题有毛病的症结。

回复：你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

回复：回复：刚才急于发出去，漏打了一句花。抱歉！现添上了。

回复：回复：回复：回复：这就可以找到你出的题有毛病的症结。

回复：回复：回复：刚才急于发出去，漏打了一句花。抱歉！现添上了。

回复：回复：你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

所以，先前俺建议你去读一读经典教科书.

回复：回复：回复：你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

回复fov22

说几句......

太好了！

和谐和谐，大家都换拖鞋。

回复：回复：和谐和谐，大家都换拖鞋。

回复：一个读文件的问题