笔试小技巧--隔板法解排列组合问题（附代码）

引言

各大互联网公司的春季招聘都在如火如荼地进行着，在笔试环节，除了考察应聘者（技术岗）的数据结构、计算机网络等计算机基础知识外，也不乏一些有趣的数学问题，例如：

一道阿里巴巴2017春季实习生招聘笔试选择题，大意是：一名程序员需要在周一至周五5天的工作日里需要提交7次代码，问有多少种提交方案？

针对此类同素分堆问题，我们可以运用隔板法来解决。

理解隔板法

隔板法就是在n个元素间的（n-1）个空中插入k个板，可以把n个元素分成k+1组的方法。　　

应用隔板法必须满足3个条件： 　　
（1） 这n个元素必须互不相异；
（2） 所分成的每一组至少分得1个元素；
（3） 分成的组别彼此相异。

例1. 求方程 x+y+z=10的正整数解的个数。
分析：将10个球排成一排，球与球之间形成9个空隙，将两个隔板插入这些空隙中（每空至多插一块隔板），规定由隔板分成的左、中、右三部分的球数分别为x、y、z之值（如下图）。则隔法与解的个数之间建立了一一对立关系，故解的个数为C（9，2）=36（个）。

例2. 求方程 x+y+z=10的非负整数解的个数。（添加球数用隔板法）
分析：注意到x、y、z可以为零，故例1解法中的限定“每空至多插一块隔板”就不成立了，怎么办呢？只要添加三个球，给x、y、z各添加一个球，这样原问题就转化为求 x+y+z=13的正整数解的个数了，易得解的个数为C（12，2）=66（个）。

例3. 将20个相同的小球放入编号分别为1，2，3，4的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放法总数。（减少球数用隔板法）
分析：先在编号1，2，3，4的四个盒子内分别放0，1，2，3个球，剩下14个球，有1种方法；再把剩下的球分成4组，每组至少1个，由例1知方法有C（13，3）=286（种）。

可见，利用隔板法我们可以非常简便地解决此类排列组合问题。

代码实现

以上问题可以抽象为：将n个相同的球放入m个盒子中（编号依次为1,2,…,m），盒子中的球数可以为0，输出所有的放置方法及方法数。

思路：

代码如下：

#include <stdio.h>

int count = 0;

void f(int* r, int* p, int n, int m)
{
  if(m == 1)
  {
    ++count;

    for(; r != p; ++r)
    {
      printf("%d", *r);
    }
    printf("%d\n", n);   
  }
  else
  {
    for(*p = 0; *p <= n; ++*p)
    {
      f(r, p + 1, n - *p, m - 1);
    }
  }
} 

void g(int n, int m)
{
  int r[m];
  f(r, r, n, m);
}

int main()
{
  int n, m;
  printf("Please input the number of balls:\n");
  scanf("%d", &n);
  printf("Please input the number of boxes:\n");
  scanf("%d", &m);
  g(n, m);
  printf("The number of solutions:%d\n", count);
  return 0;
}

运行截图：

---

参考资料：
n个球放入m个盒子，使用程序输出所有的放法？ https://www.zhihu.com/question/51448931