笔试小技巧

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

一道阿里巴巴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（个）。

例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，输出所有的放置方法及方法数。

思路：

代码如下：