用C语言解决一个抽签问题

Question

抽签
X星球要派出一个5人组成的观察团前往W星。

其中：

A国最多可以派出4人。

B国最多可以派出2人。

C国最多可以派出2人。

依次到W
那么最终派往W星的观察团会有多少种国别的不同组合呢？

怎样编写程序

Answer 1

这题目应该是这么个意思：有W个国家，每个国家有a[i] (i=1,...,w)个人，需要选P个人组团，问有多少不同的国家组合方式。

第一种解法是准备一个长度为W的数组，从0000...00开始递增，其中第i 个元素如果增加到a[i]+1则向前进位。等全部递增完了也就有结果了。
需要内存空间W，耗时a[1]a[2]...*a[W]。

第2种解法是用函数f(P,a{n})表示n个国家，每个国家有a[i]个人，共需要抽P个人的不同国家的抽法数量。
则显然有f(0,a{n})=1，f{1,a{n})=n，以及f(P,a{1})=1 (如果a{1}>=P)和f(P,a{1})=0（如果a[1]<P）
然后如果我们已知f(P,a{n})，则在此基础上增加一个国家，有
f(P,a{n+1})=f(P,a{n})+f(P-1,a{n})+f(P-2,a{n})+...+f(P-min(P,a[n+1]), a{n})
所以可以构造一个(W+1)(P+1)的矩阵C[0..W][0..P]，先填好
C[0,1]=1,..., C[0,W]=1，
C[1,1]=1,...,C[1,W]=W,
C[1,0]=0,...C[P,0]=0，
C[1,1]=1,C[2,1]=1,...C[a[1],1]=1,C[a[1]+1,1]=0,...C[P,1]=0
然后用上面的递推公式一列一列的算过去，直到C[P,W]。
需要内存空间WP，耗时PWmax(a[i])