Question

一道C++的编程数学题

给定N个各不相同的小球，和M个不同的BOX，有多少种不同的放球方法，使得每个BOX里的小球个数不小于K。N,M,K均小于15。求一个优一点的解决方案
样例输入：3 3 1

样例输出：6

能给出代码更好，可以加悬赏

Answer 1

这可以直接套公式算啊，用不着一个个去试，干嘛要写程序......

首先 N>= M*K
先确定每个 box 里面放几个，我们安排 N 个位置，1~K 是 box 1的，K+1 ~ 2K 是 box2 的....这样前 M*K 个位置分配给了 M 个 box 的固定位置;

然后，剩余 N-M*K 个位置，我们把 M-1 个“隔板”和这些“位置”一同考虑，在 X = (N-M*K) + (M-1) 个空白上，任选 M-1 个空白安排“隔板”，其余安排“位置”，这样共有
C( N-M*k + M-1, M-1) 种组合.....
以上， 第一个" 隔板“前面的“位置”是 box1 的，它后面第二个“隔板”前面的“位置”是box2 的..... 最后一个”隔板“后面的“位置”是 boxM 的

最后，我们把所有 N 个小球做个全排列，P(N, N), 然后依次填入上面的划分，就 ok 了

这样共有: P(N, N) * C(N-M*K + M-1, M-1) 种不同的放置方法.....

可能就不用写程序去硬试了吧.....

computer science 的核心是数学，只有无能的程序员才会不顾算法去穷举.....

追问

感谢！我确实想要一个公式的解法。
但是n=3 m=2 k=0的结果应该是2^3，输出8，你这个式子应该输不出8吧？

追答

oh，我做错了.... 全排列会增加大量的重复....
一时没想到会聚的方式，看来只能是先按后面的办法确定每个box的个数，然后逐次求组合数了

Answer 2

var
factorial:array[0..60] of qword;
k,m,n:longint;
function p(a,b:longint):longint;
begin
p:=factorial[n] div factorial[n-m];
end;
function c(a,b:longint):longint;
begin
c:=factorial[n] div (factorial[(n-m)]*factorial[m]);
end;
procedure init;
var
i:longint;
begin
factorial[0]:=1;
for i:=1 to 20 do
factorial[i]:=factorial[i-1]*i;
end;
begin
init;
while true do
begin
read(n,m,k);
if (n=0)and(m=0)and(k=0) then halt;
write(p(n,n)*c(n-m*k+m-1,m-1));
end;
end.

Answer 3

先用n-m*k 然后把剩下的球 分配方法 C（（n-m*k），k）

追问

谢谢，请问可以说具体一些吗？或者能给出代码最好