一道阿里巴巴笔试题目与卡特兰数
先来一道阿里巴巴的笔试题目：
说16个人按顺序去买烧饼，其中8个人每人身上只有一张5块钱，另外8个人每人身上只有一张10块钱。
烧饼5块一个，开始时烧饼店老板身上没有钱。
16个顾客互相不通气，每人只买一个。
问这16个人共有多少种排列方法能避免找不开钱的情况出现。
在兵马俑bbs的算法版上看到，第一直觉是用排列组合的办法，只要确保已付5块钱的人始终大于等于已付10块钱的人就可以了。不过具体的算法没有想到，看了回帖，safari的“卡特兰数”让我蛮好奇。就去百度了一下。这个题目就是一道典型的卡特兰数的变种题目，简单在这里说明一下：
假设付5块钱的人都是1，付10块钱的人都是0，则排队顺序可能为1111111100000000或各种1与0的排列组合，那么总共的排列顺序就是C（16，8）。但是为了避免找不开钱，则从左到右时，不能有0的数目小于1的数目的情况出现。如果出现这种情况，则必然存在第2m+1个数目时（即某个奇数数目），前2m+1个数目中有m+1个0，m个1。那么在剩余的16-2m-1个数目中，即15-2m个数目中，必然存在着8-m-1个0，8-m个1，即7-m个0，8-m个1。现在再把剩余的16-2m-1个数目中的0与1互换，则为8-m个0，7-m个1，这个时候，整个数列就变为了9个0，7个1。所以一个不符合要求的数目为9个0和7个1组成。这样的数目，0比1多两个，则必然在某一个位数出现0的个数比1多的情况，再把后面的位数中0和1对换，则这个数列又变成了8个0和8个1组成的数字。
因此，结果为C（16，8）-C（16，9）即可~~。
这道题目的关键就是后面一步的确定，这种思路好像在高中的时候上奥数的时候学过。唉，把奥数啊、算法什么的几乎都还给老师了。最近看看，补一补。
阳光真好
今天阳光真好。打扫屋子后光脚坐在阳台上，和我的两只小乌龟一起晒着暖洋洋的太阳。嘿嘿。
周四的站庆晚会圆满的结束，那天晚上引着郑南宁校长往其坐席入座的时候，满场的同学欢呼，不自觉的微笑。真好。齐老师说，郑老师从来不参与宪梓堂的文艺活动，这次，算是先例。
dianfeng师兄9月份找我的时候我就答应了，我欠他人情，该给他好好的帮忙，做一台大家满意的晚会。很幸运，晚会从最初的策划，到最后一天的顺利举行，我都全程参与，和dianfeng、lulu、杨钰一起把晚会撑了起来。也算体会了一下学校里面办事的“风土人情”，也成为了我最终坚决不留校的导火索吧。我一直都觉得自己足够的幸运，机缘巧合的过程中得到了那么多的机会，这里要感谢dianfeng始终站在我这边，给我的支持和指导。他曾经说，无论我是否留校，他都会给我推一把。感谢师兄一直以来的照顾。
周五去西工大新校区看了弟弟，一天坐了4个小时的车+西工大新校区2个小时的转悠+一周以来都没有的良好睡眠，终于让我在周五回校的路上累的一塌糊涂。。欣喜的是，弟弟越发懂事。下下周他排球比赛结束就会回家一趟，到时候给他做好吃的，(*^__^*) 嘻嘻。
还有最近的360和qq事件。发现很多人很无谓的一边倒支持360，其实只要看看新浪微薄或者腾讯微薄就可以看出来，支持360了都是满嘴的脏话，一看就是缺乏教养的人。支持腾讯的基本上都是在讲道理。这次真是感慨360的公关确实做得好，十万水有暗香盈袖军果然不是盖得。那些喊叫着不用qq的人，殊不知大洋彼岸的微软看着几天内飙升的装机量举杯庆祝。
一开始的时候就觉得360为什么这么敢和qq死磕，如果说腾讯肯定有良好的政府关系，难道说360的政府关系更硬？我一直和bf说这个事情背后一定有阴谋一定有阴谋，最终看到360的“扣扣保镖”的四大后门，我就只觉得360的悲哀了。这样的险恶用心，这样的流氓行径，就用无耻的公关和浩荡的水有暗香盈袖军让大家蒙蔽双眼。我知道很多人不喜欢qq，但实际上纯粹是 ** 与内心抗拒。这次事件，不管是腾讯现在的员工，还是从腾讯离职的员工——例如“糗事百科”的创办者王坚，还是在那里实习过的同学——例如我-。-。凡是真正了解这家公司的理念的人，都站在了腾讯一边。看着微薄上那些脏话，真是像骂一句“你大爷的敢不敢有点脑子”。但我们选择的仍然是理性的解释。
百度的同学给我留言“人们总是听到"QQ"和"窥探隐私"在一起提，时间长了，品牌效应就降了”。我深以为意，这次腾讯这招确实是被逼无奈，是360逼人太甚。
支持腾讯，支持qq。
嗯，继续华丽丽晒太阳。呼呼。
告一段落
我发现我好久没写东西。
Farewell, live space.
看到好友的签名：Xmarks要关闭了，Live Space要转WordPress了，业界的新闻都很伤感，也到了深秋。
纠结纠结纠结纠结纠结纠结。。
《Grey's anatomy》新的一集看的我唏嘘不已。所谓告别过去，是否真的就可以享受新生。我们或固执或被推动着去成为了这样或者那样的人，你说服我，抑或迁就我。我顾忌着些许，又迷茫着别样。
2010.9.24
这次的中秋假期过得特别的快。
送走了弟弟。给他包了顿饺子，做了几餐饭。心里仍是欢喜。有个亲生的兄弟姐妹，那份感觉，果然分外亲近。
外面的天突然又好冷好冷，出门的时候里里外外也套了好几件。秋天以至，明年今日，我会在做什么呢？
豆瓣上有个活动，给明年此刻的自己发条短信。想象一下，那会儿的自己，是在干什么？如果让我现在给那时的自己发条短信，我一定会说：别想太多，好好充实自己，好好干！但，也要好好过自己的日子！^_^
人生的境遇，越发发现不是人力可以控制，努力去把控好，却也仍然有可能在错失许多的同时，又得到许多。和朋友们聊及将来，感觉，就是在过一个又一个的坎。不同的岔路，就是不同的风景。无论如何，找准自己的方向，好好做，就好。
我喜欢问题简单化。讨厌层层叠叠的人际关系与欲说还休的你猜我猜。但似乎，这个世道，必须具备看透这些的本事。比较悲哀，我一点都不是这样，吃过亏，也被人耳提面命过。希望以后自己能在这方面少栽跟头吧。
明天假期就结束了。十一前还有6天，仍然有好几件事。都记到了小本子上。嗯，一个一个走吧。按照schedule来~
p.s 有道词典用起来还是挺快挺方便的。在不想装个单机灵格斯的情况下~~~很okay~~~~顺道也试用了下有道的其他产品，发现蛮惊喜。今后可以多体验体验~~~
内心强大才是真的强大
时间过得真快。9月了。8月底，匆匆离开腾讯。不仅仅是因为即将到来的中期答辩，也是因为弟弟和妈妈都在西安。要送弟弟去学校，赶他上大学之前好好沟通一次。要陪陪妈妈，大半年没有见。
弟弟一直和妈妈一起生活，不像我，初中就稀里糊涂的开始了在别人家的求学生涯。妈妈那几天尤其的唠叨与不舍，老弟一个鬼脸：终于解放了。。。我笑他，你十一回家再跟我说同样的话？这几天开始军训，少不得嘱咐。妈妈下周一回北京，那时，我更要承担起第一年照顾好老弟的责任。>.< 貌似任重而道远啊。。。不过老弟，老姐相信你哈。
回来以后见了朱老师。他老人家一直十分关心我。每次见我都问我论文进度-。- 和他聊起写论文的方式，他说我paper读的太少，不利于写论文，直接撇给我一本去年的工学论文——回去好好研究研究。嗯。。确实是要好好研究研究。写论文和之前写项目报告太不一样了。要抽象抽象再抽象。学问学问，好好读paper。
bbs上的气氛越发浮躁。也许不只是bbs，整个社会现在都浮躁的很。许多的信息在充斥，别管是真的是假的，别管是否代表着大多数，都在刺激着人们的神经，让整个时代都弥漫着一种物欲横流的信息。昨天版上十大一个帖子，说曾经的一个专科同学现在如何如何有钱，说那个人赶上了保险不规范的时期，和车主一起骗保险公司的钱。大家没有谴责之声，却仅仅是说些什么“你过几年也会好的”、“啊，好羡慕”之类的话。包括现在对公务员、“稳拿”、“高薪”的趋之若鹜。大家都想一步登天。却越发不知道自己欠缺的究竟是什么。
我自问做的也不是很好，内心也总是有点浅浅的“追名逐利”，但总是笃定把事情要做就做好做的漂亮的原则。追求事情的完满，在不完满之时，内心那种忧伤，又是无论如何都轻易抹杀不掉。其实，自己仍然是内心，不够强大。
回来天天晚上回家，陪妈妈一起看电视、逛街。《婚姻保卫战》看了最后几集，深深觉得里面的场景很普遍。如果爱情不完满，家庭不幸福，根本就不会安下心来去实现自我价值。除非彻底被刺激了。。。但有可能走另外一个极端。《实习医生格蕾》里面其实也是一样，事业的成就是一方面，家庭与爱情，才是一个人幸福的本源。
我仍然每天内心小打鼓自己是否足够优秀，我仍然为些不完满泛起止不住的忧伤。可见我需要走的路还是很长。