蓝桥杯抽签

【题目描述 - Problem Description】

X星球要派出一个5人组成的观察团前往W星。其中： A国最多可以派出4人。 B国最多可以派出2人。 C国最多可以派出2人。 ....

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

下面的程序解决了这个问题。数组a[] 中既是每个国家可以派出的最多的名额。程序执行结果为：

DEFFF
CEFFF
CDFFF
CDEFF
CCFFF
CCEFF
CCDFF
CCDEF
BEFFF
BDFFF
BDEFF
BCFFF
BCEFF
BCDFF
BCDEF
....
(以下省略，总共101行)

 1 #include <stdio.h>
 2 #define N 6
 3 #define M 5
 4 #define BUF 1024
 5 
 6 void f(int a[], int k, int m, char b[])
 7 {
 8     int i,j;
 9     
10     if(k==N){ 
11         b[M] = 0;
12         if(m==0) printf("%s
",b);
13         return;
14     }
15     
16     for(i=0; i<=a[k]; i++){
17         for(j=0; j<i; j++) b[M-m+j] = k+'A';
18         _____________;  //填空位置
19     }
20 }
21 int main()
22 {    
23     int  a[N] = {4,2,2,1,1,3};
24     char b[BUF];
25     f(a,0,M,b);
26     return 0;
27 }

填空代码

【题解】
一看到这道题就想起了自己在懒得写for的时候就用DFS代替……

因为里面的两层循环只能为6个数枚举一个，再加上上面的条件输出，f(a, ?, ?, b);基本是钦定的形式。

k == N 推测，k记录当前层数。

b[M - m + j] = k + 'A';和f(a, 0, M, b); 推测m为当前未使用的层数。

【最终结果】

f(a, k + 1, m - i, b)

f(a, k + 1, m - j, b)

f(a, (++k)--, m - i, b)

…………………………随便挑一个

（某人：泥垢了！）

蓝桥杯 抽签

蓝桥杯抽签