• Tag Archives: 情人节

情人节

O'Reilly情人节福利

oreilly

今年情人节O’Reilly给程序猿们也带来了福利:所有粉红色的电子书半价。FOREVER ALONE!

说到O’Reilly出品的动物丛书,程序猿无人不知。这系列书最显著的特点就是封面上手绘的动物,所以也有动物世界/饲养员指南的别名。考据癖有专门一篇文章解疑了为什么O’Reilly用动物形象做书籍封面,原文可见Origin of Species: A History of O'Reilly Animals

设计者Edie Freedman姐姐在设计动物丛书的第一本书时(上图中间),她接触到UNIX、vi、sed&awk、lex、yacc这些不知所云的词,让她觉得这些词都像来自于当时正流行的游戏“龙与地下城”,于是她心目中UNIX程序员的形象就是一个龙与地下城的玩家。Edie在19世纪的木版画中找到了灵感,画中诡异的动物刚好和那些高深的UNIX术语是绝配。还有一件更严肃的事情,出版动物丛书让Edie更加注意到生态问题。很多封面动物已经濒临灭绝,而在版画绘制的时期,这些动物还是大量存活的。O’Reilly也希望他们使用这些动物做封面能够引起人们对动物保护的关注。

关于O’Reilly动物丛书颜色和内容有没有联系,应该是有,不过没有查到具体说明和相似的问题,不过有所有O’Reilly丛书数据,可以根据颜色然后分析关键词,就先在这挖个坑。FOREVER ALONE!

情人节特别课堂: 稳定婚姻问题

趁着情人节的气氛,给大家介绍一个有趣的问题:稳定婚姻问题,青春期的GGMM一定要看...hehe会有收获的^^
这个问题曾在一个OIER的空间里看到过,他讲得是班级的男女生谈朋友的配对==....其实就是这个问题,可惜现在找不到那个空间了orz...不过这两天发现科学松鼠会的一篇文章我要我们在一起介绍了这个问题,于是自己修改了下,来给GGMM们上课啦,有空还准备编个程玩玩。
(PS:以前还讨论过最佳约会策略(摘取最大麦穗),也推荐青春期的GGMM去受教~~)

稳定婚姻问题The Stable Marriage Problem最早是由两个美国数学家David Gale&Lloyd Shapley于1962年在American Mathematical Monthly上提出的,这个问题和图论有关(求完全二分图的稳定完备匹配,这是一个NP问题)。对于以前没有接触过这个问题的人,这个理论最出人意外的结论是:传统的求爱、结婚过程是male-optimal(男生主动)的,也就是说,男性能够得到尽可能好的心上人,女性却不然。这里我们就不科普了,直接上问题:

给定若干个男生和同样多的女生,他们每个人都对所有的异性有一个心理的偏好次序(无并列)。具体点说就是每个男生都凭自己好恶给MM排个名次:我最爱a,其次爱b,再次爱c...同样,每个MM也同样给每个男生打分。
问题1:是否存在一种男女配对组合构成一种稳定的组合关系? 稳定组合的意思是说,不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。
问题2:在已知每个人对异性的偏好顺序的情况下,怎样求出这种稳定组合方式?(如果它存在的话)

对于以上两个的问题的答案当然是肯定的。Gale 和Shapley不但提出了这个问题本身,而且给出了一种著名的解法Gale-Shapley算法(延迟认可算法)
激动人心求婚过程是这样进行的(如果觉得太快了的话,那就认为是表白吧):
第一天,让这些男生去向他们最心仪的女生表白。等所有男生表白完毕后,所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。没人表白的女生只能暂时等一等了,不要着急,表白会有的。以上过程称为“一轮”。之后的每一轮都按照类似的方式进行。
第二天还处于单身状态的男生们每个人再次向自己还没有表白过的女生中自己最喜欢的人表白(无论人家是否已经有了男朋友),然后,等所有单身男生表白完毕后,所有的收到表白女生们都从自己的表白者中选择自己最喜欢的人接受为男朋友。如果原来有男朋友而表白者中有自己更喜欢的,不要犹豫,换之。等到尘埃落定之后,再开始如上所述的新的一轮表白。
依此类推。可以证明的是,这个过程一定是会终止的,也就是说,不会陷入任何死循环。并且一旦终止,每个人都会找到一个伴侣。更关键的是,这个过程最终得到的一定是如前所述的“稳定组合”。

真正有趣的部分还在后面。 ... Read More

Everyday is Valentine's Day

首先...这是篇无聊的流水帐,传说中的标题党,也不知道什麽時候开始注意起情人节的,难道是写blog开始?就算这篇完全凑数好了...
感觉今年这日子过得真是...无聊。(话说校内上di也是一片抱怨,吃醋者众多。恩..大家都吃饱了,我写这篇水文也吃饱了) 罢了,也算是出去感受过气氛了,我算是情人节加班加点的那种?!去什么区创新大赛的展示,浪费了一个下午,站得我腿都酸死了,体会到站柜台的辛苦了(以前在书店看书的时候也站到腿酸过)。后来我的腰也不行了,"小蛮腰"太脆弱了,获得"花瓶"称号一个,值了值了,感谢cctv,mtv....有人说路上没碰到过一对情侣,这个是很有能力的orz...猜想人民广场有没有鸽子喂撑死的;看到n捧花,没去调查过玫瑰的行情,我玫瑰康乃馨傻傻分不清楚==...
后来喜欢"户口调查"的我妈跟我说原来有个"5年培养5000区明日之星"的指标。我靠...老子就这么成了众多人头中的一个了。老子不干了,消极怠工。
为了摆脱无聊流水帐,发个special数独~~咔咔,这个还算是比较应景(做过,满简单的)。唯心地说: Everyday is Valentine's Day^^...
(PS:排版真痛苦orz...排的比较难看,所以N篇文章没有配图片了;其实觉得自己取的标题也越来越烂了)

close