Question

用c语言实现排列组合问题（华为软件面试试题之一）

有m个篮子，每个篮子可以装n个球，现在共有x个球，球是完全相同的。问有多少种放法？（用c语言编程实现,只要做出数学揭发就可给分）
（我觉得应该分x<n和大于等于n讨论）

Answer 1

/* 算法 */
// 从剩余的nM个篮子里空出nX = m*n - x;个球
int GetBall(int nX, int nM, int n) {
  int nA;
  int nS = 0;
/* 如果这次情况里确定从一个篮子里空出球 */
  // 如果nM等于1 返回 1;
  if (nX <= n) {
/* 最少从一个篮子里拿走，最多必须从 nM 与 n 中 较少个数的篮子里拿走 */
    // 当nA从 1 增加到 nX，循环执行下行语句
      nS += GetBall(nA,1,n) + GetBall(nX-nA,nM-1,n);
    // 返回 nS;
  } else if (nX > n) {
/* 1. 知道剩下的篮子数目nM，2. 可以保证nX-nA <= nM*n */
    // 当nA从 n 减少到 nX-n*nM，循环执行下行语句
      nS += GetBall(nA,1,n) + GetBall(nX-nA,nM-1,n);
    // 返回 nS;
  }
}

int main() {
  int m,n,x;
  m = 5; n = 6; x = 22;
  printf("%d\n",GetBall(m*n-x, m, n));
  return 0;
}

Answer 2

这里把所有的篮子当作是等价的，也就是 一个球放在哪个篮子都是同一种放法。 如果不是这样的话就麻烦了。。

int Situations(int m, int n, int x)
{
if (x < 0) return 0;
if (x == 0) return 1;
if (n*m == 0) return 0;
return Situations(m-1,n,x) + Situations(m, n-1, x-m);
}

int main()
{
int m, n, x;
scanf("%d %d %d", &m, &n, &x);
printf("%d\n", Situations(m,n,x));
}

Answer 3

过来看看。。。

Answer 4

篮子一样?？？

Answer 5

/*
算法
*/
//
从剩余的nM个篮子里空出nX
=
m*n
-
x;个球
int
GetBall(int
nX,
int
nM,
int
n)
{
  int
nA;
  int
nS
=
0;
/*
如果这次情况里确定从一个篮子里空出球
*/
  //
如果nM等于1
返回
1;
  if
(nX
<=
n)
{
/*
最少从一个篮子里拿走，最多必须从
nM
与
n
中
较少个数的篮子里拿走
*/
    //
当nA从
1
增加到
nX，循环执行下行语句
      nS
+=
GetBall(nA,1,n)
+
GetBall(nX-nA,nM-1,n);
    //
返回
nS;
  }
else
if
(nX
>
n)
{
/*
1.
知道剩下的篮子数目nM，2.
可以保证nX-nA
<=
nM*n
*/
    //
当nA从
n
减少到
nX-n*nM，循环执行下行语句
      nS
+=
GetBall(nA,1,n)
+
GetBall(nX-nA,nM-1,n);
    //
返回
nS;
  }
}
int
main()
{
  int
m,n,x;
  m
=
5;
n
=
6;
x
=
22;
  printf("%d\n",GetBall(m*n-x,
m,
n));
  return
0;
}