登陆注册
9284300000167

第167章 白板编程

“这个问题,需要用到高中数学知识。”

推理过程:忽略一胞多胎、不育夫妇以及还没生下男孩就去世的夫妇。

首先要认识到的是,该国的所有家庭,在停止生育之前,都拥有了或即将拥有一个男孩。为什么呢?因为每对夫妇都会不停生孩子,直到生出一个男孩才罢休。除了多胞胎,“一个男孩”就是“只有一个”的意思。因此,有多少家庭,就有多少男孩。

不过,一个家庭可以有任意数量的女孩。对女孩子做一次想象中的人口调查会是个好办法。

邀请全国所有的母亲集中到大房间,通过公共广播系统询问:“请所有第一胎生女孩的母亲举起手来好吗?”自然,有一半的妇女会举手。

如果母亲总数为N,那么N/2会举手,也就代表第一胎生的女孩有N/2个。请在想象中的标示牌上记下来:N/2。

接着你又问:“请第二胎生女孩的母亲举起手来好吗?第一胎、第二胎都是女孩的请别把手放下哦。”有一半的手会放下去,但不会有新的手举起来。第一个问题时就没举手的母亲,不会生第二个孩子,因为她们第一胎就是男孩。

于是,举起来的手是N/4,这意味着第二胎生出的女孩有N/4个。把它记在标示牌上。“请第三胎是女孩的母亲继续举起手好吗?”你明白了吧。继续这么做,直到最后再也没有还举着的手。每一轮问题,举起的手都会放下去一半。

这就带来了一个我们很熟悉的数列:(1/2+1/4+1/8+1/16+1/32+...)×N这一无穷级数之和为1(×N)。女孩的人数等于家庭数N,也等于男孩的人数(或非常接近)。因此,该国的男女比例是1:1。

至于为什么想当然是错的,固然每个家庭都有男孩,有很多家庭没有女孩;但同时所有家庭只会有一个男孩,却有可能有多个女孩。

这两种情况取得了折中。

“完成了前面的开胃菜,下面我们进行更加传统的项目,现在有N个32位整数,需要完成排序。这道题答对双倍奖励,答错双倍惩罚,不允许跳过。”少女在眼前的全息白板上写着,到了“白板编程”环节。

“总之,冒泡排序是错的。”这个***式的笑话,引来一阵大笑。

“这个N是多少呢,我想不同的N结果差异会很大。”墨出尘一眼就识别出了潜在的陷阱。

“我们不妨让N=150,000。”

“那可是相当多的数字了,我想快速排序是个不错的选择。”墨出尘道。

“OK,sounds great,下一步,钟奇正你负责快速排序算法的实现,墨出尘你需要向初中生水平的我,解释清楚什么是快速排序算法。”少女道。

“我该用什么语言来实现?有什么限制吗?”

“为什么我要向初中水平的人解释什么是快速排序算法?”

“我认为你可以在python、c(c++)、java、swift、perl中选择一个,至于为什么要解释给不懂的人,很简单,这测试的是同理心,这与我们设计产品时,切换到用户角度来思考是一个道理。”

钟奇正拿着一支黑色的马克笔,符号开始在白板上涌现,速度快得让人惊讶。

墨出尘开始解释什么是快速排序,他是这样说的:

“快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。首先从数列中挑出一个元素,称为“基准”(pivot);

“重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

“递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序,就完成了快速排序。”

“听起来像是疯子的喃喃自语,我完全不知你在说什么。”少女反馈道。

“我觉得很清晰啊。”

“上面的纯属废话,能看懂你说的是什么的,本身就懂归并排序;看不懂的,依然学不会。这是我对你说的是废话这一观点的逻辑证明。”

“好吧,我承认上面的很晦涩,毕竟自然语言并不是表述算法的合适载体,自然语言本身的歧义性、模糊性使它不具备这种功能,或许你看看钟奇正写的代码就清晰了。”

少女双手抱头,“我不看代码!我不看代码!我不看代码!”

“墨出尘,我认为你举个例子加以说明会好很多。”钟奇正已经完成了白班编码。

“ah,好主意,正好也给你提供一个测试用例,我们拿15个数举个栗子好了,至于15万个数,在逻辑上是一样的。只是运行时间、内存占用会多很多。”

假设有一组数是3、44、38、6、47、15、36、26、27、2、46、4、19、50、48,现在我们对它进行快速排序。

首先我们挑选3作为基准,在过程中我们对小于3的数,进行标记,并替换到前面,当一圈进行完后(到最后一个数48),我们将小于3的数移动到左侧。

3、2、38、6、47、15、36、26、27、44、46、4、19、50、48(2与44替换)

下面让3就这个基准就处于数列的中间位置,即它左边的都比它小,右边的都比它大。数列变为2、(3)、38、6、47、15、36、26、27、44、46、4、19、50、48。

之后以3为分界线,分别对3左边的数列进行快速排序,右边的数列同样进行快速排序。因为左边只有一个数,至此快速排序结束,不再递归。

右边的38、6、47、15、36、26、27、44、46、4、19、50、48数列,以38基准进行快速排序,结果是38、6、15、36、26、27、4、19、47、44、46、50、48

将38基准位置进行调整,6、15、36、26、27、4、19、38、47、44、46、50、48

将38左侧,右侧分别进行快速排序6、15、36、26、27、4、19以6为基准,6、4、36、26、27、15、19,变为4、6、36、26、27、15、19,将36、26、27、15、19进行快速排序,变为26、27、15、19、36,将26、27、15、19、进行快速排序,26,15,19,27,调整位置,15,19,26,27,将15,19进行快速排序得到15,19

所以38左侧快速排序结果为4、6、15、19、26、27、36

38右则为47、44、46、50、48,快速排序得到44、46、47、50、48,对44、46进行快速排序得到44、46,对50、48进行快速排序得到48、50。所以右边结果为44、46、47、48、50

所以最终结果为2、3、4、6、15、19、26、27、36、(38)、44、46、47、48、50。

“这个过程与我的完全一致,我顺便做了个排序可视化,侧面验证了正确性,如果对排序非常感兴趣,可以看这里,

“见识到了结对编程的重要性了吧,我们深入探讨一下,如果数据本身是基本有序的,快速排序算法还有优势吗?”

同类推荐
  • 三界最强继承人

    三界最强继承人

    听说是您将要继承那一百个亿的家产是吗?哦,我没有继承一百个亿的家产!我只是继承过漫威英雄的能力,萧炎的异火,唐三的秘籍,林叔的道术,哦,还有很多人求着我去继承他们的妞!
  • 我在进化

    我在进化

    外科医生杨立发现自家的衣柜后突然出现了一个陌生的世界。突如其来的死亡袭击让杨立对这个异世界产生了极大的兴趣,在探索之中,越来越多的诡异世界出现在了地球......群号:727197228
  • 快穿之无关风月

    快穿之无关风月

    九天之上,白玉之巅。万仙拜服,众生皆畏。她是世人心中的神祇,掌无限因果,控三千世界,无情无爱,无欲无求,高高在上。她不爱苍生,不曾有丝毫动容,却赢得苍生敬畏;他心系苍生,为此湮灭于天地,却无人知晓。他为苍生利用她一丝悲悯,她入三千红尘品味人生百态。当一切结束,她是沾染尘缘就此沉沦,还是依旧纤尘不染俯看众生?无cp文,番外大多是人物的单相思,不喜可跳过。(不虐女主,女主不喜欢任何人!)
  • 我的掌中宇宙

    我的掌中宇宙

    坐拥一个庞大浩瀚的多元宇宙,财富要多少有多少,神器量产,资源无限,手底下强者多如牛毛,科技胜过地球亿万倍……“我从来都不在乎敌人强不强,因为无论有多强,都一定没我强!”
  • 末世重生之饕餮食皇

    末世重生之饕餮食皇

    陆浩重生回到末世发生前一天,带着前世十年末世生存的记忆,既然上天让他重生一次,那么这一次他一定会有一个不一样的未来,他必将成就饕餮食皇的辉煌
热门推荐
  • 妖火

    妖火

    他妖火转脉之心,他独获剑河九道剑意,他惹得仙宗之女倾心,他害的魔尊之女相思。九曲皓月,逆灵莫测之剑。七道剑意,九诀嗜杀。我非狂傲之人,但求立足世间,人若阻我,我必戮之。天若挡我,我必焚天!天道茫从,妖娆世间,独奏一曲鬼炎妖火乱世之曲。
  • 爆宠小毒妃

    爆宠小毒妃

    那唤作颜蝶陌的女子,正身着红衣跪在殿下。浑身不住发抖,看起来甚是激动。但是,就在她抬起头的时候,她的双眼之中竟然满是病态的癫狂。“朕今日将颜蝶陌赐婚给……”--情节虚构,请勿模仿
  • 吟游刺杀录

    吟游刺杀录

    这是一个剑与魔法的勇者大陆,一个拥有远大志向的吟游诗人。他立志写出最华美篇章,立志将爱与和平传递给世界,将欢笑带给每一个人,他希望那些大剑圣大魔导师一张嘴,都会蹦出他书里的段子。为此他15岁外出游历,10年时间走了半个大陆,却越来越落魄,最终不得不在酒馆讲段子,以维持生计。故事也从这里开始…而至于本书风格……你看封面不就知道了吗?
  • A Bundle of Letters

    A Bundle of Letters

    本书为公版书,为不受著作权法限制的作家、艺术家及其它人士发布的作品,供广大读者阅读交流。汇聚授权电子版权。
  • 甜妞追爱记:误擒霸道总裁

    甜妞追爱记:误擒霸道总裁

    她沦落到无家可归时,遇到他,自此赖上他。一次舍友起哄,对电话那端的他大声喊,“大叔,你们很配!在一起、在一起……”他哼笑一声,问:“你觉得如何?”她窘迫至极,红着脸回他:“是很配啊,的确很配很配很配很配……”舍友逼问:“愿意成为她男朋友吗?三个答案,一愿意,二愿意,三愿意!”他拒绝的干脆:“不愿意!”短暂的静默后……他:“老公的话,我会很愿意!”死寂过后……“啊……”此起彼伏的尖叫!
  • 心中风景

    心中风景

    本书当代名家散文丛书:心中风景内容包括:亚美利加天空的温情;辉煌的震撼;依稀明晰的梦境;在维也纳感到失落;维也纳的“金戒指”;那里的高雅羞辱了我;临近赤道的故乡;拉让江畔的约会;“长屋”的节日;香港的启示;金马伦山麓;“水果刀”的祝福;维多利亚海滨绿意;夜香港的魅力;登太平山看香港夜景;说不尽的西子湖;绍兴的感动;深厚的中原腹地;寻找雨花台;消隐了的桨声灯影;有关北京城墙的话题;被遮蔽的风景;电话亭上的招贴;消失的故乡;崇武半岛。
  • 网游之大神驾到,一剑倾心

    网游之大神驾到,一剑倾心

    自从入了游戏坑之后,总能在身边发现第二大神的踪影,他到底是谁?怎么会给我一种莫名的熟悉感呢?但,怎么可能是他,难道是我的错觉吗?【方阙阁覅】:我的资料看够了吗?我老脸一红,偷看别人资料确实不光明正大,红脸光速逃离现场,没想到对方快速飞到我面前。【方阙阁覅】:有没有兴趣做一个隐藏任务?本以为他是不可一世的高冷腹黑,没想到下一秒竟对我佯装可怜。“我可以找别人,只不过路过这里的女生玩的全是奶妈,根本没有人玩刺客,这个任务可以让你直接再升12级,要知道这个游戏升级很麻烦的。”就这样,我们有了第一次的接触,接下来就自然而然一起游戏,一起任务。
  • 都市错爱

    都市错爱

    懂乌云的密布,懂阳光的温柔,懂狂风的残酷,懂时钟的节奏,但却不懂这世界浓缩的态度。更加不明白青春到底散落在了哪一处……
  • 九命奇冤

    九命奇冤

    本书为公版书,为不受著作权法限制的作家、艺术家及其它人士发布的作品,供广大读者阅读交流。汇聚授权电子版权。
  • 特许连锁经营运作操典

    特许连锁经营运作操典

    《特许连锁经营运作操典》就特许连锁经营概述、特许连锁经营项目开发、特许连锁经营的购买、受许人的评价与招募、特许经营合约的拟订与订立、特许经营双方关系的处理、特许连锁经营的融资、特许连锁经营的法律问题、特许连锁总部的运作、特许连锁分店的运作等方面。作了详细介绍,对特许连锁经营进行了全面的阐述,言简意赅。