第9章 排列组合与概率

排列组合常用于字符串或序列的排列和组合中，而求解排列组合的方法也比较固定：第一种是类似于动态规划的方法，即保存中间结果，依次附上新元素，产生新的中间结果；第二种是递归法，通常是在递归函数里使用for循环，遍历所有排列或组合的可能，然后在for循环语句内调用递归函数。本章所涉及的排列组合相关的问题很多都采用了上述方法。

概率论是计算机科学非常重要的基础学科之一，因为概率型面试、笔试题可以综合考查求职者的思维能力、应变能力、数学能力，所以概率题也是在程序员求职过程中经常会遇到的考题。

9.1 如何拿到最多金币

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

10个房间里放着随机数量的金币。每个房间只能进入一次，并只能在一个房间中拿金币。一个人采取如下策略：前4个房间只看不拿。随后的房间只要看到比前4个房间都多的金币数，就拿。否则就拿最后一个房间的金币。编程计算这种策略拿到最多金币的概率。

分析与解答：

这道题是一个求概率的问题。由于10个房间里放的金币的数量是随机的，因此在编程实现时首先需要生成10个随机数来模拟10个房间里金币的数量。然后判断通过这种策略是否能拿到最多的金币。如果仅仅通过一次模拟来求拿到最多金币的概率显然是不准确的，那么就需要进行多次模拟，通过记录模拟的次数m，拿到最多金币的次数n，从而可以计算出拿到最多金币的概率n/m。显然这个概率与金币的数量以及模拟的次数有关系。模拟的次数越多越能接近真实值。下面以金币数为1～10的随机数、模拟次数为1000次为例给出实现代码：

程序的运行结果为

运行结果分析：

运行结果与金币个数的选择以及模拟的次数都有关系，而且由于是个随机问题，因此同样的程序每次的运行结果也会不同。

9.2 如何求正整数n所有可能的整数组合

难度系数：★★★★☆

被考查系数：★★★☆☆

题目描述：

给定一个正整数n，求解出所有和为n 的整数组合，要求组合按照递增方式展示，而且唯一。例如，4=1+1+1+1、1+1+2、1+3、2+2、4（即4+0）。

分析与解答：

以数值4为例，和为4的所有的整数组合一定都小于4（1, 2, 3, 4）。首先选择数字1，然后用递归的方法求和为3（即4-1）的组合，一直递归下去直到用递归求和为0的组合时，所选的数字序列就是一个和为4的数字组合。然后第二次选择2，接着用递归求和为2（即4-2）的组合；同理下一次选3，然后用递归求和为1（即4-3）的所有组合。以此类推，直到找出所有的组合为止，实现代码如下：

程序的运行结果为

运行结果分析：

从上面运行结果可以看出，满足条件的组合为：（1, 1, 1, 1），（1, 1, 2），（1, 3），（2, 2）， （4）。其他的为调试信息。从打印出的信息可以看出：在求和为4的组合中，第一步选择了1；然后求3（即4-1）的组合也选了1，求2（即3-1）的组合的第一步也选择了1，依此类推，找出第一个组合为{1, 1, 1, 1}。然后通过count--和i++找出最后两个数字1与1的另外一种组合2，最后三个数字的另外一种组合3；接下来用同样的方法分别选择2、3作为组合的第一个数字，就可以得到以上结果。

代码i=（count==0？1:result[count-1]）用来控制组合中的下一个数字一定不会小于前一个数字，从而保证了组合的递增性。如果不要求递增（如把（1，1，2）和（2，1，1）看作两种组合），那么把上面一行代码改成i=1即可。

9.3 如何用一个随机函数得到另外一个随机函数

难度系数：★★★★☆

被考查系数：★★★☆☆

题目描述：

有一个函数fun1能返回0和1两个值，返回0和1的概率都是1/2，问怎么利用这个函数得到另一个函数fun2，使fun2也只能返回0和1，且返回0的概率为1/4，返回1的概率为3/4。

分析与解答：

fun1得到1与0的概率都为1/2。因此，可以调用两次fun1，分别生成两个值a1与a2，用这两个数组成一个二进制a2a1，它的取值的可能性为00,01,10,11，并且得到每个值的概率都为（1/2）×（1/2）=1/4。因此，如果得到的结果为00，那么返回0（概率为1/4），其他情况则返回1（概率为3/4）。实现代码如下：

程序的运行结果为

由于结果是随机的，调用的次数越大，返回的结果越接近1/4与3/4。

9.4 如何等概率地从大小为n的数组中选取m个整数

难度系数：★★★★☆

被考查系数：★★★☆☆

题目描述：

随机地从大小为n的数组中选取m个整数，要求每个元素被选中的概率相等。

分析与解答：

从n个数中随机选出一个数的概率为1/n，然后在剩下的n-1个数中再随机找出一个数的概率也为1/n（第一次没选中这个数的概率为（n-1）/n，第二次选中这个数的概率为1/（n-1），因此，随机选出第二个数的概率为（（n-1）/n）×（1/（n-1））=1/n）。依此类推，在剩下的k个数中随机选出一个元素的概率都为1/n。这个算法的思路为：首先从有n个元素的数组中随机选出一个元素，然后把这个选中的数字与数组第一个元素交换，接着从数组后面的n-1个数字中随机选出一个数字与数组第二个元素交换。依此类推，直到选出m个数字为止，数组前m个数字就是随机选出来的m个数字，且它们被选中的概率相等。

以数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]为例，实现代码如下：

程序运行后得到的结果是随机的，下面只列出了其中的一种显示情况。

算法性能分析:

这个算法的时间复杂度为O（m）。

9.5 组合1、2、5这三个数使其和为100的组合个数

难度系数：★★★★☆

被考查系数：★★★★☆

题目描述：

求出用1、2、5这三个数不同个数组合的和为100的组合个数。为了更好地理解题目的意思，下面给出几组可能的组合：100个1、0个2、0个5的和为100；50个1、25个2、0个5的和也是100；50个1、20个2、2个5的和也为100。

分析与解答：

方法一：蛮力法

最简单的方法就是对所有的组合进行尝试，然后判断组合的结果是否满足和为100，这些组合有如下限制：1的个数最多为100个，2的个数最多为50个，5的个数最多为20个。实现思路为：遍历所有可能的组合1的个数x（0≤x≤100），2的个数y（0≤y≤50），5的个数z （0≤z≤20），判断x+2y+5z是否等于100，如果等于100，那么满足条件。实现代码如下：

程序的运行结果为

算法性能分析：

这个算法循环的次数为101×51×21。

方法二：数字规律法

针对这种数学公式的运算，一般都可以通过找出运算的规律简化运算的过程。对于本题而言，对x+2y+5z=100进行变换可以得到x+5z=100-2y。从这个表达式可以看出，x+5z是偶数且x+5z≤100。因此，求满足x+2y+5z=100组合的个数就可以转换为求满足“x+5z是偶数且x+5z≤100”的个数。可以通过对z的所有可能的取值（0≤z≤20）进行遍历从而计算满足条件的x的值。

当z=0时，x的取值为0, 2, 4, …, 100（100以内所有的偶数），个数为（100+2）/2。

当z=1时，x的取值为1, 3, 5, …, 95（95以内所有的奇数），个数为（95+2）/2。

当z=2时，x的取值为0, 2, 4, …, 90（90以内所有的偶数），个数为（90+2）/2。

当z=3时，x的取值为1, 3, 5, …, 85（85以内所有的奇数），个数为（85+2）/2。

……

当z=19时，x的取值为5, 3, 1（5以内所有的奇数），个数为（5+2）/2。

当z=20时，x的取值为0（0以内所有的偶数），个数为（0+2）/2。

实现代码如下：

算法性能分析：

这个算法循环的次数为21。

9.6 如何判断有几盏灯泡还亮着

难度系数：★★★★☆

被考查系数：★★★★★

题目描述：

100个灯泡排成一排，第一轮将所有灯泡打开；第二轮每隔一个灯泡关掉一个，即排在偶数的灯泡被关掉，第三轮每隔两个灯泡，将开着的灯泡关掉，关掉的灯泡打开。依此类推，第100轮结束的时候，还有几盏灯泡亮着？

分析与解答：

1）对于每盏灯，当拉动的次数是奇数时，灯就是亮着的；当拉动的次数是偶数时，灯就是关着的。

2）每盏灯拉动的次数与它的编号所含约数的个数有关，它的编号有几个约数，这盏灯就被拉动几次。

3）考虑在1～100这100个数中有哪几个数的约数个数是奇数。

一个数的约数都是成对出现的，只有完全平方数的约数个数才是奇数。所以，这100盏灯中有10盏灯是亮着的，它们的编号分别是：1、4、9、16、25、36、49、64、81、100。实现代码如下：

程序的运行结果为