【算法趣题】Q17 挑战30人31足

引言

【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。

问题描述

30个人排成一行，每个人的两条腿分别和相邻的人绑在一起，只有左右最边上的两个人才有单独的左腿或右腿，29个双足加2个单足，这就是“30人31 足的”来由。多个女生连续排列，体力上会处于劣势，所以原则上是尽量不让女生相邻（男生可以连续排列）。

【问题】求30个人排成一排时，一共有多少种有利的排列方式？假设这里只考虑男女的排列情况，不考虑具体某个人的位置。举个例子，4个人（4人5足）的情况下如图所示，共有8种排列方式。

思路及Python3实现

我们考虑的问题可以转换为在男生中插女生的问题。

在以上4人的情况，可以转化为以下组合数的和，即

当“3人4足”时，则有

通过以上可以发现，组合中的上标数+下标数 = 总人数+1（即足数），而上标数从0开始循环，最大为最多可插入的女生数，且上标数不大于下标数，因此有

import math

from scipy.special import comb, perm

def get_count(n):

    # n为总人数

    # most_girl为女生最多的人数

    most_girl = math.ceil((n+1)/2)

    count = 0

    for i in range(most_girl+1):

        if i > n+1-i:

            continue

        count = count + comb(n+1-i,i)

    return int(count)

即当“30人31足”时，满足条件的共有2178309种。

我觉得这种方式解答是比较快的。书上还有其他思路，可以尝试一下吧。