|
|
|
 [VC++学习]递归
读书笔记
|
| 队伍组织问题 游行的队伍由方阵和花车组成。要求永远不要将一个方阵紧跟在另一个方阵的后面。组织长度为n的游行队伍有多少种方法？ 假设至少有n个行进方阵和n辆花车可供选择。在设计组织游行队伍的方法时，假定方阵-花车和花车-方阵是不同的游行队伍，它们当作两种方法计算。 游行队伍可以花车或方阵结尾。组织队伍的方法数仅仅是各种类型的游行队伍数之和。即令：P(n)是组织长度为n的游行队伍的方法数 F(n)是花车结尾的，长度为n的游行队伍数 B(n)是方阵结尾的，长度为n的游行队伍数则有：P(n) = F(n) + B(n) 首先考虑F(n)。在容许的情况下，在所有长度为n-1的队伍尾部安排一辆花车 就得到了以花车结尾的、长度为n的游行队伍。因此，以花车结尾的、长度为n的队伍数目恰好等于长度为n-1的队伍总数，即：F(n) = P(n - 1) 接下来考虑B(n)。以方阵结尾的唯一方法是此方阵前有一辆花车（如果是一个方阵，则会有两个相邻方针）。因此，组织以方针结尾的、长度为n的游行队伍的唯一方法是首先组织以花车结尾的、长度为n-1的队伍，然后再尾部加上一个方阵。因此，以方针结尾的、长度为n的队伍数恰等于以花车结尾的、长度为n-1的游行队伍数，即：B(n) = F(n-1)使用早先的事实：F(n) = P(n-1)得到：B(n) = P(n-2) 因此，根据较小的子问题F(n-1)和F(n-2)分别解决了B(n)和F(n)。然后使用 P(n) = F(n) + B(n)得到：P(n) = P(n-1) + P(n-2)对于游行队伍问题， P(1) = 2（长度为1的游行队伍是花车或者方阵） P(2) = 3（长度为2的游行队伍是花车-花车、花车-方阵或者方阵-花车）归纳起来这个问题的解决方案是： P(1) = 2 P(2) = 3 P(n) = P(n-1) + P(n-2) n > 2 Spock先生的难题（n件事情中选择k件） U.S.S.Enterprise的任务是在五年中探索未知世界。五年即将过去，但Enterprise刚刚进入未探索过的太阳系，太阳系有n颗行星。不幸的是，由于时间有限，只能访问k颗行星。Spock先生要考虑探索n颗行星中的k颗有多少种可能的选择。因为时间短，他不关心访问k颗行星的顺序。 Spock先生对一个特定的行星X特别着迷。问题是考虑行星X后，如何从n颗行星中选取k颗，“有两种可能：我们或者访问行星Ｘ，或者不访问行星Ｘ；如果访问行星Ｘ，则必须从剩下的n-1颗行星中选择k-1个其他行星；如果不访问行星X，则必须从剩下的n-1颗行星中选择k个其他行星。” Spock先生正在计算从n颗行星中选取k颗的可能组数。令c(n, k)是从n颗行星中选取k颗的组数，则根据行星X，Spock先生归纳出： c(n, k) = 行星X中选取k颗的组数 + 不在行星X中选取k颗的组数 但Spock先生已经推断出包括行星X的组数是c(n-1, k-1)，不包括行星X的组数是c(n-1, k)。Spock先生已经明白，根据两个同类型的较小的问题解决他的问题的方法，也就是：c(n, k) = c(n-1, k-1) + c(n-1, k) n件事情中选择k件的方法数是：n-1件中选择k-1件的方法数与n-1件中选择k件的方法数之和。 Spock先生现在不得不考虑基本事件。他还需要证明两个较小的子问题中的每个最终都能到达基本事件。首先，选择什么问题他立即就可以知道答案？如果Enterprise有时间访问所有的行星（即：如果k = n），则不需要选择，只有所有行星一组。因此，第一种基本事件c(k, k) = 1 如果k < n，很容易看到递归定义中的第二项c(n-1, k)比c(n, k)更接近基本事件c(k, k)，但第一项c(n-1, k-1)并不比c(n, k)更接近基本事件c(k, k)，它们同样不容易计算。当我们通过解决两个（或多个）较小的问题解决一个问题时，两个较小问题中的每一个都必须比原问题更接近基本事件。 Spock先生认识到，第一项事实上接近另一个更小的选择问题。这个问题是与他第1种基本事件的c(k, k)相对应的。正如只有所有行星一组（k=n）一样，也只有0颗行星一组（k=0）。当没有时间访问任何一颗行星时，Enterprise必须返回，不进行任何搜索。因此，第2种基本事件是：c(n, 0) = 1 这种基本事件的确具有这样的性质：c(n-1, k-1)比c(n, k)更接近基本事件。作为另一种选择，可以定义第2种基本事件是c(n, 1) = n。 Spock先生在他的解决方案中添加了最后一部份：c(n, k) = 0 k > n尽管在这个问题中，k不能大于n，但加上这种情况可以使递归解决方案适用面更宽。 概括的讲，如下递归解决方案可以解决n件事情中选择k件的问题： c(n, k) = 1 如果 k = 0，k = n c(n, k) = 0 如果 k > n c(n-1, k-1) + c(n-1, k) 如果 0 < k < n 由此递归定义很容易推导出如下函数： int c(int n, int k) { if ((k == 0) || (k ==n)) return 1; else if (k > n) return 0; else return c(n-1, k-1) + c(n-1, k); }
摘自：《数据结构与C++高级教程》 |
|
|
|
|
