珍珠湾ART

标题: 一个读文件的问题 [打印本页]

作者: fov22 时间: 2012-2-14 10:45
标题: 一个读文件的问题

磁带上有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
标题: 欢迎贴新帖！

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

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-14 23:58
标题: 回复：一个读文件的问题

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

作者: fov22 时间: 2012-2-15 01:17
标题: 回复：一个读文件的问题

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 04:07
标题: 回复：回复：一个读文件的问题

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

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

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

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

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 05:12
标题: 回复：Lili是这里的老坛友了，能不能饶人家新朋友一次？

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

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

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

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 07:31
标题: “饶一次”兄，看清了没有?

“饶一次”兄，看清了没有（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
标题: 回复：我都看得清清楚楚

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 09:04
标题: 回复：一个读文件的问题

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

作者: fov22 时间: 2012-2-15 09:13
标题: 回复：回复：一个读文件的问题

你看了我的修改没有？

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

如果要定义随机变量，那么就是这样，对于一个给定的排列，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
标题: 回复：回复：回复：一个读文件的问题

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 09:48
标题: 是你自己在题中就把它“和概率扯上”的呀！

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 09:57
标题: 回复：是你自己在题中就把它“和概率扯上”的呀！

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

作者: fov22 时间: 2012-2-15 10:00
标题: 回复：回复：回复：回复：一个读文件的问题

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

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

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

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

作者: fov22 时间: 2012-2-15 10:03
标题: 回复：回复：是你自己在题中就把它“和概率扯上”的呀！

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 10:19
标题: 回复：回复：回复：回复：回复：一个读文件的问题

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

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

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

作者: fov22 时间: 2012-2-15 10:21
标题: 回复：回复：回复：回复：回复：回复：一个读文件的问题

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 10:37
标题: 这就可以找到你出的题有毛病的症结。

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 10:41
标题: 都看清楚了吧！说您是俺的“托”。[:))]

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 10:43
标题: 请看底下。

请看底下。

作者: fov22 时间: 2012-2-15 10:51
标题: 回复：这就可以找到你出的题有毛病的症结。

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

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

以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
标题: 回复：回复：这就可以找到你出的题有毛病的症结。

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 11:07
标题: 刚才急于发出去，漏打了一句花。抱歉！现添上了。

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 11:20
标题: 回复：回复：这就可以找到你出的题有毛病的症结。

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

作者: fov22 时间: 2012-2-15 11:20
标题: 回复：刚才急于发出去，漏打了一句花。抱歉！现添上了。

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

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

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

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

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

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

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 11:21
标题: 你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

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

作者: fov22 时间: 2012-2-15 11:22
标题: 回复：回复：回复：这就可以找到你出的题有毛病的症结。

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

作者: fov22 时间: 2012-2-15 11:28
标题: 回复：你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 11:41
标题: 回复：回复：刚才急于发出去，漏打了一句花。抱歉！现添上了。

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 11:52
标题: 回复：回复：回复：回复：这就可以找到你出的题有毛病的症结。

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

作者: fov22 时间: 2012-2-15 11:53
标题: 回复：回复：回复：刚才急于发出去，漏打了一句花。抱歉！现添上了。

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

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

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 12:03
标题: 回复：回复：你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 12:44
标题: 所以，先前俺建议你去读一读经典教科书.

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

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

作者: fov22 时间: 2012-2-15 13:31
标题: 回复：回复：回复：你的读n个文件，是一口气从头连着读下来，还是按别的什么次序读？

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

作者: 冷眼看戏的Lili 时间: 2012-2-15 14:45
标题: 回复fov22

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

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

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

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

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

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

作者: husonghu 时间: 2012-2-16 09:47
标题: 说几句......

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-16 10:42
标题: 太好了！

色盲JJ要回来？

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

作者: 冷眼看戏的Lili 时间: 2012-2-16 11:53
标题: 和谐和谐，大家都换拖鞋。

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-16 23:43
标题: 回复：回复：和谐和谐，大家都换拖鞋。

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

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

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

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

作者: fov22 时间: 2012-2-17 04:49
标题: 回复：一个读文件的问题

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

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

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

作者: 冷眼看戏的Lili 时间: 2012-2-17 05:23
标题: 回复：回复：一个读文件的问题[:-Q]

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

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

，但步数通常会大一些。

作者: 冷眼看戏的Lili 时间: 2012-2-17 22:52
标题: 回复：回复：回复：一个读文件的问题[:-Q]

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

作者: 色盲 时间: 2012-2-18 09:59
标题: [:&][:-K]好热闹啊[:-D]

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

首先感谢楼主出的题，也感谢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
标题: 热烈欢迎色盲jj回脑坛来！[@};-][@};-][@};-]

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

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

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

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

作者: 动脑筋 时间: 2012-2-18 20:06
标题: 色盲MM好 [>:D<][>:D<][>:D<][>:D<]

作者: 冷眼看戏的Lili 时间: 2012-2-19 08:18
标题: 方法与证明

对任一个不符合顺序（按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
标题: Lili动脑筋MM好！大家好！！[>:D<][>:D<][>:D<]

多日不见，想死大家了

www.ddhw.org---

据说这世界是彩色的？

欢迎光临珍珠湾ART (http://zzwav.com/)