“唔……你下午没有课吗？”小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笑道，“当然，我会请你吃顿好的，因为害怕你藏私货，所以我决定下血本请你吃麻辣烫……”
两人一边说笑，一边到隔壁叫上同学，杀出门外……