欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-21 23:05:28
...

引言

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

一道阿里巴巴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