程序员的算法趣题Q17：30人31足游戏

1. 问题描述

本题来自《程序员的算法趣题》中的第17题。

以前有个电视节目，全国各地的小学生在这个节目里参加“30人31足”竞赛。

后来电视剧里也出现过这些小学生练习的场景，

并且全国大赛时小学生们表现出来的速度也曾引人注目。

下面探讨一下什么样的排列顺序在“30人31足”比赛里比较有利。

多个女生连续排列，体力上会处于劣势，所以原则是尽量不让女生相邻（男生可以连续排列）。

求：30 个人排成一排时，一共有多少种有利的排列方式？

假设这里只考虑男女的排列情况，不考虑具体某个人的位置。

本题和31足没啥关系，仅为了引出"不让女生相邻"。

所以题目转化为：30个人排成一排，女生不相邻，有多少种站位方式？

男生和女生一起参加“30人31足”比赛。由于女生体力有劣势，所以两个女生排在一起的话整个队伍就会在体力上处于明显不利地位。所以原则上尽量不让女生相邻排列，称没有女生相邻排列的排列方式为“合理”排列。

请问，当总共N个男生和女生一起排成一排时，一共有多少种合理的排列方式？

假设这里男生之间、女生之间不考虑区分（即不考虑男生之间的相对位置的不同，也不考虑女生之间的相对位置的不同）。举个例子，4个人（4人5足）的情况下共有8种排列方式，如下所示（B表示boy，G表示Girl）：

BBBB, GBBB, BGBB, BBGB, BBBG, GBGB, BGBG, GBBG

2. 解法1—作为计数问题的闭式解

这个问题可以当作一个计数问题来考虑，可以直接通过数学推导得到闭式(closed-form)解。

令男生人数为Nb, 女生认识为Ng，首先它们满足关系：

             (1)

由于不允许两个女生相邻排列，因此必然满足（考虑Nb个男生排成一排，包括两端在内一共有Nb+1个位置可以插入女生，即Nb个男生构成的队列中最多可以插入Nb+1个女生以构成“合理”排列）：

             (2)

结合（1）和（2）可得：

             (3)

接下来，由于男生人数为Nb，包括两端在内一共有Nb+1个空档可以插入女生。同时又由于不允许女生相邻排列，所以不能有两个女生插入同一个空档。在这个条件下，所能构成的合理的排列数的问题就转变成了：Ng个女生放入Nb+1个位置有多少种安排方法？由于女生之间不区分，所以这是一个组合问题，总共有，然后对所有Nf的可能取值进行求和即可得到（将N个人的队伍的合理排列方式数记为）：

             （4）(Nf为Ng的笔误)

3. 解法2—作为计数问题的递推表达式

将N个人的队伍的合理排列方式数记为。

考虑从左往右安排队伍，则最右边的人为最后一个安排的人。最后的人(即第N个人)有男生和女生两种可能性，分别讨论如下：

1. 如果最后一个人为男生，则对前N-1个人的排列方式没有约束条件。即这种情况下的排列方式等于前(N-1)个人的“合理”排列方式，也即是
2. 如果最后一个人为女生，则倒数第二个人必定为男生，进而同理可得对前N-2个人的排列方式没有约束条件。即这种情况下的排列方式等于前(N-2)个人的“合理”排列方式，也即是

基于以上讨论可以得到递推关系式，如下所示：

             (5)

这个递推关系式与斐波那契数列的递推关系式完全相同，但是本问题的解序列的解序列并不构成标准的斐波那契数列，原因在于初始化条件不同。为了利用(5)式解出的具体值，我们需要给出序列的最初几个值作为初始化条件。

N=1：很显然，这里我们假定允许单独一个女生参赛（“1人2足”）

N=2：，“BB”, “BG”, “GB”

N=3：，“BBB”, “MBB”, “BMB”, “BBM” , “MBM”

…

因此，本问题的递推关系式表达的解为：

……………… (6)

有兴趣的读者可以自行验证式(4)表示的解和式(6)表示的解式完全等价的。

以上是从最后一个人倒着往前推，但是从第一个正向地往后推也可以得到相同的递推关系。具体来说就是，假设第一个人为男生，第2个人可以为男生也可以为女生，则其后的排法与N-1的情况相同；假设第一个人为女生，第2个人必然为男生，第3个人可以为男生也可以为女生，则其后的排法与N-2的情况相同。由此可得到与式(6)相同的递推关系。

4.代码及测试

编程计算就是以代码的方式实现式(6)所示的递推关系而已，可以以递归(recursion)的方式外加memoization来实现（代码简洁但是有额外计算代价），另一种方式是以迭代（iteration）的方式计算。递归的方式是从目标值开始从大到小反向回溯的方式进行递推计算，而迭代（iteration）则是前向地从小到大地进行递推计算。

思路1

1.30个人，一个一个增加。如果最右边是男生，则可加男or女；如果最右边是女生，则只可加男。

2.用List<Integer>表示这个队伍

3.用1和0分别表示男生和女生

4.用递归表示每一个位置的所有选择

5.用count统计最终结果

代码1

public static int count = 0; // 统计结果个数

public static void main(String[] args) {
    // 1.队伍 2.人数上限
    add(new LinkedList<Integer>(), 30); // 自定义的方法
    System.out.println("count = " + count);
}

/**
 * 在当前的队伍中加入一个人
 * @param queue     当前的队伍
 * @param maxLimit  最大人数限制
 */
private static void add(LinkedList<Integer> queue, int maxLimit) {
    // 不合法情况
    if (queue == null || queue.size() > maxLimit) return;
    
    // 成功情况
    if (queue.size() == maxLimit) {
        count ++; // 结果数量+1
        System.out.println(queue); // 查看队伍中的排列情况
        return;
    }

    // 如果一个人都没有 or 最后一个是男生
    if (queue.size() == 0 || queue.getLast() == 1) {
        // 加一个男生的情况
        queue.addLast(1);
        add(queue, maxLimit);
        queue.removeLast();

        // 加一个女生的情况
        queue.addLast(0);
        add(queue, maxLimit);
        queue.removeLast();
        
    } else { // 如果最后一个是女生
        // 只能加一个男生
        queue.addLast(1);
        add(queue, maxLimit);
        queue.removeLast();
    }
}

结果1

......省略很多条数据......

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0]

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1]

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1]

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0]

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1]

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0]

[0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

count = 2178309

思路2

上述代码涉及到集合的大量增删，时间效率很低。

如果不在乎具体的排列方式，只需要求得结果，则可以去掉集合

代码2

public static int count = 0; // 统计结果个数

public static void main(String[] args) {
    // 1.当前队伍中的人数 2.最后一个人的性别 3.人数上限
    add(1,1,30); // 第一个是男生的情况
    add(1,0,30); // 第一个是女生的情况
    System.out.println("count = " + count);
}

/**
 * 纯粹用于计算，不需要操作集合，耗时更短
 * @param num      当前的人数
 * @param last     最后一个人是男是女
 * @param maxLimit 总人数
 */
private static void add(int num, int last, int maxLimit) {
    // 不合法情况
    if(num <= 0) return ;
    if (last != 1 && last != 0 ) return;

    // 成功情况
    if (num == maxLimit) {
        count ++;
        return;
    }

    // 如果最后一个是男生
    if (last == 1) {
        // 尝试加一个男生
        add(num + 1, 1, maxLimit);

        // 尝试加一个女生
        add(num + 1, 0, maxLimit);
    } else { // 如果最后一个是女生
        // 只能加一个男生
        add(num + 1, 1, maxLimit);
    }
}

结果2

count = 2178309

思路3

假设目前该加入第n个人

如果第n-1个人是男生，则现在可以加入男生or女生；

如果第n-1个人是女生，则现在只可以加入男生。

换言之：

如果第n个人是男生，则之前的站位方式是f(n-1)种；

如果第n个人是女生，则之前的站位方式是f(n-2)种。因为她前一个人必定是男生

由此可得：f(n) = f(n-1) + f(n-2); // 斐波那契数列的公式

代码3

public static Map<Integer,Integer> hmap = new HashMap<>(); // 内存化提升时间性能，避免重复计算
public static int count = 0; // 统计结果个数
public static void main(String[] args) {
    System.out.println("count = " + f(30));
}

/**
 * n个人站成一排的站法有多少种
 * @param n 当前人数
 * @return  有几种站法
 */
private static int f(int n){
    if(n < 0) reutrn 0;  // 不合法情况

    if(n == 0) return 1; // 0个人的站位只有一种：没有人
    if(n == 1) return 2; // 1个人的站位有两种：男 or 女

    if(! hmap.containsKey(n)){ // 如果没有，则存入
        hmap.put(n, f(n-1) + f(n-2)); // 当前位置站男生的方式 + 当前位置站女生的方法
    }

    return hmap.get(n);
}

结果3

count = 2178309