算法入门02

算法入门02

一、将 m ≥ 1 mge 1 m≥1 个同样的红球， n ≥ 1 nge1 n≥1 个同样的兰球排成一行。对排法要求如下：任意某个兰球，其左侧的红球个数大于等于其左侧的兰球个数加1。总共有多少种正确的排列方法（分析递归表达式，要写出分析过程）。

例：下列1的排法合法的排法1中，左起第1个兰球左侧有2个红球，所以满足 2 ≥ 1 2ge 1 2≥1；且左起第2个兰球左侧有2个红球，满足 2 ≥ 2 2ge2 2≥2，所以是正确排列。

例1： 正确的排法： ◯ ◯ ◯ ◯ textcolor{red}{bigcirc} textcolor{red}{bigcirc} textcolor{blue}{bigcirc} textcolor{blue}{bigcirc} ◯◯◯◯

例2： 正确的排法： ◯ ◯ ◯ ◯ textcolor{red}{bigcirc} textcolor{blue}{bigcirc} textcolor{red}{bigcirc} textcolor{blue}{bigcirc} ◯◯◯◯

例3： 错误的排法： ◯ ◯ ◯ ◯ textcolor{red}{bigcirc} textcolor{blue}{bigcirc} textcolor{blue}{bigcirc}textcolor{red}{bigcirc} ◯◯◯◯

解答：

• 递归表达式如下：

f ( m , n ) = { m m ⩾ 1 , n = 1 0 m < n f ( m − 1 , n ) + f ( m , n − 1 ) m ⩾ n > 1 f(m,n)=begin{cases} m & m geqslant 1, n=1 \ 0 & m<n \ f(m-1,n)+f(m,n-1) &m geqslant n>1 end{cases} f(m,n)=⎩⎪⎨⎪⎧​m0f(m−1,n)+f(m,n−1)​m⩾1,n=1m<nm⩾n>1​

• 分析过程如下：

  1. 当 n = 1 n=1 n=1 时，仅有一个兰球，可在红球之间进行插空，但不能放在最前面可以放在最后面，所以一共有 m m m 种插空方式。

  2. 当 m < n m<n m<n 时，无论将球如何摆放，总会出现至少有一个兰球，其左侧的红球个数小于等于其右侧兰球个数的情况，故此时将没有正确的排列方式。

  3. 当 m ⩾ n m geqslant n m⩾n 时，采用递归的思想，即在 ( m + n − 1 ) (m+n-1) (m+n−1) 个球摆放的基础上再添加一个球，此时有两种情况：加上的球为红球或者兰球。但添加球时都只有一种方法，即将添加的红球或兰球放在原有的正确排法的末尾处，所以对于 m m m 个红球， n n n 个兰球的情况，其递归表达式可以写成减去一个红球的情况 f ( m − 1 , n ) f(m-1,n) f(m−1,n) 和减去一个兰球的情况 f ( m , n − 1 ) f(m,n-1) f(m,n−1) 之和。

• 经验与心得：

  ​ 对于递归的想法思路更加清晰了一些。

  ​ 在最开始时，对于从哪里开始递归毫无思路，陷入了分类讨论的思路中，即分别在红球个数和兰球个数的基础上寻找递归的最佳办法，后来发现两者是无法割裂开来进行讨论的，因为添加球的位置不同，会有多种情况，而这时，红球和兰球的情况会有部分重合，并且无法很好地对这些情况进行区分。

  ​ 所以关于递归，很重要的一点是要找到合适的递归的对象，使得其能在递归前和递归后完全分离开来。比如本题是对总的球的个数进行递归，所以我们在计算第 n n n 种情况时，只需要在第 ( n − 1 ) (n-1) (n−1) 种情况的基础上再添加一个球即可。