第二桶 基于对象的编程 第六碗 哥俩又谈递推模型 小P三解通项公式

 

     “唔……你下午没有课吗?”小P推门走进教研室,他刚刚上完数理统计,又没有约好踢球,于是决定到教研室晃晃,一进门就看到老C趴在桌子上不知在捣鼓什么。

     “嗯,我下午没有课……我在研究怎么破解人类的tower rush……这个真是游戏的bug,暴雪一定会做出平衡的……”老C被小P的tower rush打得很郁闷,于是在网上找找对策。

     “呵呵,呵呵,”小P笑道,“我们总会找到游戏中的不平衡点加以利用的……”他摇摇头,“说到游戏,我突然想到你上次说小朋友吃苹果的游戏,怎么可以用一个循环左移实现呢?”

     “哦,是的是的……”老C关掉那些无聊的网页,“你不提,我还真是险些忘了。”他接着说道,“关于这个问题,它的前提条件是每数到2的小朋友被踢出,这个 会是你在各大面试笔试中会常遇到的……”说完他指挥小P拉过白板,“这样其实相当于求解一个2进制数的循环左移结果。”

     “哦?那么是怎么来的呢?”小P问道。

     “同样,由于我们的智力有限,无法理解过于复杂的问题,所以我们先来看看几个实际的例子。”老C说道,说着他在白板上画了一个圈,然后在上面按顺时针方向从1标到6。“我们来看看会发生什么……”老C说道,然后开始在白板上比划起来。

    

     “看看,我们玩过一轮后,出现了这种情况……”老C把开始的情况和玩过一轮后的情况写了下来。

     “小圆圈内的数字表示座位号,”老C解释。“看看我们可以得到一些什么又用的结果。”看到小P莫名其妙的样子,老C接着说道,“好吧,我们令T(n)表示 n个小朋友结束游戏后,剩下的小朋友的座位号码,我们发现,当6个小朋友玩这个游戏1轮后,还剩下3个小朋友依照同样的方式再继续玩。”老C看到小P还是 懵懂的样子,强调道,“注意,在这里我们发现剩下的3个小朋友需要依照同样的方式继续,这就表明了,其实这个问题是递归的。”

     “唔,的确是这样,这样,求解6个小朋友玩游戏的过程,就变为求解3个小朋友玩游戏的过程了……但是……等等……我发现好像小朋友编号的规则不一样了……”小P道。

     “是么?”老C赞许的点点头,“你发现有什么区别?”

     “嗯,原来的小朋友的编号是依照座位号编号的,但是在进行1轮游戏后,剩下的3个小朋友的编号方式就不是依照座位编号了,好像是(2*座位号-1)?”小P问道。

     “没错,的确是这样,而这个就是这个递归问题的关键……”老C说道,“如果我们令T(n)为n个小朋友束游戏后,剩下的小朋友的座位号码,那么T(n)一定是座位号码吧?”

     “……”小P无语点头。

     “但是剩下的3个小朋友如果继续,是不是需按照新的编号规律进行编码,才符合我们T(n)表示座位号的假定?”老C问道。

     “……”小P摇头。

     “呵呵,”老C笑道,“你可以这样认为。”说完他在白板上写下一行公式。


T(6) = 2 * T(3) – 1


     “如果我们要3个小朋友玩游戏,他们的编号应当是1、2、3才对,但由于实际上他们的编号是1、3、5,所以他们的实际编号是2*T(3)-1。因为 T(3)的假定是小朋友的编号需要从1开始依次为2、3,玩游戏结束剩下的那个小朋友的号码,但是实际上剩下的3个小朋友的编号是1、3、5,所以按照这 样的编号玩游戏,结束时剩下的小朋友的编号就是2*T(3)-1。”老C笑道,“你仔细体会一下就明白了。”

     “哦,有些意思……我再看看。”小P说道。他想了一会儿,觉得也不是很难以想通,于是说道,“好吧,那么然后呢?”

     “然后我们就可以猜测这样的递推公式。”老C说道。


T(n) = 2T(n/2) – 1


     “为了好看起见,我们将上面的公式稍微更改一下。”老C又说道。


T(2n) = 2T(n) - 1


     “这样我们就有了第一个递归公式。”老C说道。

     “哦,看来只对偶数个小朋友起作用……如果小朋友的个数是奇数怎么办?”小P问道。

     “同样,我们也找一个例子来研究一下。”老C说道。

     

     “同样,我们把玩过一轮的情况画下来。”老C说道。

     “与上面分析的道理一样,我们可以得到T(2n+1) = 2T(n)+1”老C说道,“你再仔细看看。”

     小P低头想了一会儿,说道:“嗯,没有什么难的,这个我可以理解。”

     “好的,这样我们得到了递推公式。”老C说道,“你可以假定参加游戏的小朋友是2n和2n+1个,按照类似的办法,画个图,就会得到这样的结论。”说着他在白板上写下如下公式。


T(1) = 1

T(2n) = 2T(n)-1

T(2n+1) = 2T(n)+1


     “但是这组递推公式无法依照我们前面的解法解出来它的通项,因为我们很难将它转换为一个求和的方程。”老C说道,“在不知道更好的解决方法之前,我们只有拼拼人品,使用数学归纳法啦。”

     “唔,你是说要猜测出通项公式,然后使用数学归纳法证明吗?”小P问道。

     “是啊是啊,”老C回答,“你好歹是本科毕业,这个应当难不倒你吧……”

     “切,这个只要高中毕业就会了!”小P不屑。

     “那好吧,刚好我们有一个程序可以很快的算出最后剩下小朋友的号码,我们就来列一组表格,看看有什么规律。”老C说道。

     于是小P打开他的电脑,开始运行前一段时间自己编写的程序,捣鼓出来一个表格,并画到了白板上。

 

n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

T(n)

1

1

3

1

3

5

7

1

3

5

7

9

11

13

15

1

3

5

7

9

 

     “看看,有什么规律啊。”小P自言自语,“唔,好像在n = 2m的时候T(n)=1,而且T(n)会随着2m为模,很有规律的在变化。”

     “没错,根据递推公式,T(2n)=2T(n)-1,可以看出T(2)=1,T(4)=2T(2)-1=1,而T(8)=2T(4)-1=1,以此类推,所以T(2m)=1。”老C补充。

     “好像如果n可以写为n=2m+k的形式,则T(n)=2k+1。”小P经过一段时间的观察,分析道,“这样我们就可以得到通项公式。”说着他在白板上写下通项。


T(2m+k)=2k+1


     “唔,这个结论对不对呢,我来用数学归纳法证明一下。”小P说道。于是他在白板上比划起来。

 

令n = 2m+k,

当n = 1时,m = 0,k = 0

T(1) = 2k + 1 = 1,原式成立。

设当n = 2m + k时,T(n) = 2k + 1

那么当n = 2m + k + 1时,若n是偶数,那么k+1是偶数,有

T(2n) = 2T(n) – 1

T(2(2m-1+(k+1)/2)) = 2T(2m-1+(k+1)/2) – 1 = 2(2(k+1)/2 + 1)-1 = 2(k+1) -1

等式仍然成立。

若n是奇数,那么k是偶数,有

T(2n+1) = 2T(n) + 1

T(2(2m-1+k/2)+1) = 2T(2m-1+k/2) +1 = 2(2k/2+1) +1 = 2k+3 = 2(k+1) + 1

等式仍然成立。

综上,原通项成立。

 

     “嗯,看来我们的猜测是正确的。”小P道,“但是这个与循环左移有什么关系呢?”

     “因为T(n)会以2m为模有规律的变化,这样促使我们使用2进制数看看有什么有趣的规律。”老C说道。

 

设n可以表示为2进制数bmbm-1bm-2…b0,且bk非1即0,则

n = bm2m + bm-12m-1 + bm-22m-2 +…+ b0

且bm = 1

那么

k = bm-12m-1 + bm-22m-2 +…+ b0

2k = bm-12m + bm-22m-1 +…+ 2b0

2k + 1 = bm-12m + bm-22m-1 +…+ 2b0 + 1 = bm-12m + bm-22m-1 +…+ 2b0 + bm

 

 

     “看看,这就相当于对n的2进制数做了循环左移一样!”老C说道。

     “……”小P低着头看了半天,“嗯,没错,好像是这样。我们来带入几个数值看看吧。”小P把上面几个表的数据拿来看看。

 

5 = (101)2

T(5) = 3 = (11)2

 

20 = (10100)2

(1001)2 = 9 = T(20)

 

     “唔,看来确是如此。”小P赞叹道,“这还真是奇妙的事情。”

     “是啊是啊,所以你以后在面试和笔试的时候,碰到相同的问题,就无需写出大堆的代码啦,只要写一个实现循环左移的函数就可以了。”老C回答。

     “嗯……”小P点点头,“既然数到2的小朋友被踢出的结果可以用一个循环左移表示,那么数到3,数到4……数到n被踢出的结果有什么好的方法表示呢?”小P追问。

     “呵呵,”老C笑道,“我看到了你光明的未来……”他点点头,“这些并没有什么现成的结论,你可以根据编写好的程序,自己生成一些数据表格,看看有什么特 殊的规律。我猜如果这些数字以3为模,可能与3进制有关联;如果以4为模,可能和4进制有关……Any way,你可以进行一些尝试,看能否得出一些有趣的结论。等你总结好了,别忘了告诉我……”

     “好啊,不过到时你可得请我吃饭啊!”小P道。

     “那是当然……”老C笑道,“我们关于递推的讨论先暂时告一段落,我觉得你差不多也算上道了,所以我们开始要进行一些更有趣的活动……”

     “……”小P无语,“你又找到什么好馆子了?”

     “……”老C囧,“不是,是我觉得应当可以系统的开始一些工作了。”

     “哦?什么是系统的工作?”小P不解。

     “还记得《Teach Yourself Programming in Ten Years》吗?这本书提到,在项目中学习是很好很强大的。因此……我们现在可以开始一个项目了。”老C回答。

     “哦?什么项目?”小P奇道。

     “先从一个桌面计算器开始吧。”老C说道,“一个自由风格的计算器,可以对数学运算进行计算,并可以进行一些简单的公式计算。”他想想,“就像最简单的matlab。”

     “是吗?”小P兴奋道,“这真是很酷的事情。”

     “既然要做,我们就很正规、正式、正经、正确、正……哦,”看到小P幽怨的眼神,老C赶快打住,“我们就按照正规的、科学的过程来做。”

     “那么怎么才算是正规和科学呢?”小P追问。

     “很好,”老C满意的点头,“希望你保持这种旺盛的求知欲望。”他找到杯子喝了一口水,“所谓正规和科学,是使得我们的开发活动有序、可控和可度量。如何 做到这些,我也无法一时说清楚,等到我们进行一段时间,你可能就会产生一些体会了。你记住现在脑海中产生的问题,让我们在实践中慢慢解答。但是在开始我们 的项目之前,还有一些铺垫的东西必须先进行一下。”

     “哦?有哪些呢?”小P问道。

     “技术和技能可以一边随着项目的进行一边训练,但一些知识性的问题要先来。”老C回答,“第一,我们要先学习一下递归下降语法分析;第二,我们还要学习一 下有限状态机;第三,我们要了解一些配置管理方面的知识;第四,了解一些简单的关于项目方面的概念;当这些问题我们都有过一些简单的讨论后,我们就可以开 始一个简单的关于桌面计算器的小项目啦,而在所有这些过程中,我们都会穿插进行一些数据结构与算法的讨论。”

      “是么?我倒是有些迫不及待啦。”小P应道。看到老C指着肚子,小P笑道,“当然,我会请你吃顿好的,因为害怕你藏私货,所以我决定下血本请你吃麻辣烫……”

     两人一边说笑,一边到隔壁叫上同学,杀出门外……

 




posted on 2009-04-13 16:02 Anderson 阅读(1539) 评论(4)  编辑 收藏 引用

评论

# re: 第二桶 基于对象的编程 第六碗 哥俩又谈递推模型 小P三解通项公式 2009-04-29 23:31 JIN

不错~  回复  更多评论   

# re: 第二桶 基于对象的编程 第六碗 哥俩又谈递推模型 小P三解通项公式[未登录] 2009-05-15 15:52 Anderson

考试临近,停止更新……
6月27日考试……书还没有看完呢……  回复  更多评论   

# re: 第二桶 基于对象的编程 第六碗 哥俩又谈递推模型 小P三解通项公式 2009-05-21 20:30 supersand

兄弟还是在校学生吗?  回复  更多评论   

# re: 第二桶 基于对象的编程 第六碗 哥俩又谈递推模型 小P三解通项公式[未登录] 2009-06-04 15:28 Anderson

已经毕业啦。^_^  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年6月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

导航

统计

常用链接

留言簿(6)

随笔档案(21)

文章档案(1)

搜索

最新评论

阅读排行榜

评论排行榜