今天朋友要我帮忙解决个问题，还是蛮有趣的，于是就写了这个
有趣的分组:A Funny Grouping
1.Problem
L班有14名成员，代号分别以英文字母命名（A～N），现在分组完成一件事情，分组要求包括所有成员，一组中最多允许3名成员，有些成员可以一个人一组，同时也允许某些组员兼任在其他小组中，但是根据性格和特长的特点，只能作特定的搭配。搭配被保存在IN.txt中。现要求分组越少越好。求最少应分多少组，该组数下各方案是怎样分的。
2.Input
输入数据包含每一小组成员，一共33个组，组和组之间用一个‘,’或一个转行符隔开，组内成员之间没有间隔。
3.Output
首先按照以下格式输出分组的数目(max)，可行方案数(num)。
The number is (max).
We have find (num) arraies suitable.
然后接下来的每行中，首先输出方案号，然后一个冒号，然后是方案中每一组的编号，编号之间用空格隔开。
4.Sample Input:(IN.txt)
ABC,BCE,FGH,GHI,HIK,HJK
AB,AE,BC,BE,CD,CE,DE,EF,EJ,FG,FH,GH,GI,HI,HJ,HK,IK,IL,JK,JM,KL,KM,LN,MN
B,D,L
5.Sample Output:(OUT.txt)
The number is 6.
We have find 6 arraies suitable.
1 : 1 3 13 24 25 30
2 : 1 6 13 16 24 30
3 : 1 3 6 13 24 30
4 : 1 3 13 23 26 29
5 : 1 5 13 16 26 29
6 : 1 3 5 13 26 29
分析：
这是一道较为简单的题目，意思很明显，要用穷举，把所有的组合都试一遍看他是否包含所有成员。
对于判断某组员是否已包含过，我们可以用一个int型变量的二进制位来表示，每一位表示对应字母，该位为1则存在，该位为0则不存在。
本题的难点恐怕是如何找出一个组合数，其实这也很简单，用递归就可以轻易实现。具体怎么实现的，看一看例程的Search()函数吧。
Sampal Code:
// Save as party.cpp.
// party.cpp : Defines the entry point for the console application.
#include <stdio.h>
#include <stdlib.h>
#define PARTY_NUM 33 // 输入组的个数
#define MAX_NUM 8 // 最大允许选择的组数
#define MAX_RESUALT 100 // 最大允许结果组数
#define LETTER_NONE 0x0000
#define LETTER_A 0x0001
#define LETTER_B 0x0002
#define LETTER_C 0x0004
#define LETTER_D 0x0008
#define LETTER_E 0x0010
#define LETTER_F 0x0020
#define LETTER_G 0x0040
#define LETTER_H 0x0080
#define LETTER_I 0x0100
#define LETTER_J 0x0200
#define LETTER_K 0x0400
#define LETTER_L 0x0800
#define LETTER_M 0x1000
#define LETTER_N 0x2000
#define LETTER_ALL 0x3FFF
int combination[MAX_NUM]; // 存储各种组合
int exist = LETTER_NONE; // 存放已存在过的字母,用来测试
int party[PARTY_NUM]; // 存放各组的成员
int resualts[MAX_RESUALT][MAX_NUM]; // 存放结果
int resualt_num = 0; // 结果的最大数号
int min = 5; // 最小分组数
// 功能—主要涉及参数
void Search(int m,int n); // 递归式地在m个元素中选n个元素的组合—combination[]
bool ReadFile(); // 读取文件，初始化party[]—party[]
void WriteFile(); // 输出结果—min resualt_num resualts
inline void test(); // 测试是否符合条件—exist
int main(int argc, char* argv[])
{
if(!ReadFile()) exit(0);
resualt_num = 0;
min = 4;
do
{
min++;
Search(PARTY_NUM,min);
}while(!resualt_num);
WriteFile();
return 0;
}
void Search(int m,int n)
{
int i;
for(i=0;i<=m-n;i++)
{
combination[n-1]=m-i;
if(n>1) Search(m-i-1,n-1);
else
{
test();
}
}
}
inline void test()
{
int i;
exist = LETTER_NONE;
for(i=0;i<min;i++)
exist |= party[combination[min-i-1]-1];
if(exist == LETTER_ALL)
{
for(i=0;i<min;i++) resualts[resualt_num][i] = combination[i];
if((resualt_num++) >= MAX_RESUALT)
{
printf("Warning, data overflow!\n");
}
}
}
bool ReadFile()
{
FILE *pf;
if(!(pf=fopen("IN.txt","r")))
{
printf("File can not open!\n");
fclose(pf);
return false;
}
char c;
int i;
for(i=0;i<PARTY_NUM;i++) // clear
party[i] = LETTER_NONE;
i=0;
while(!feof(pf))
{
c=fgetc(pf);
switch(c)
{
case 'A':
case 'a':
party[i] |= LETTER_A;
break;
case 'B':
case 'b':
party[i] |= LETTER_B;
break;
case 'C':
case 'c':
party[i] |= LETTER_C;
break;
case 'D':
case 'd':
party[i] |= LETTER_D;
break;
case 'E':
case 'e':
party[i] |= LETTER_E;
break;
case 'F':
case 'f':
party[i] |= LETTER_F;
break;
case 'G':
case 'g':
party[i] |= LETTER_G;
break;
case 'H':
case 'h':
party[i] |= LETTER_H;
break;
case 'I':
case 'i':
party[i] |= LETTER_I;
break;
case 'J':
case 'j':
party[i] |= LETTER_J;
break;
case 'K':
case 'k':
party[i] |= LETTER_K;
break;
case 'L':
case 'l':
party[i] |= LETTER_L;
break;
case 'M':
case 'm':
party[i] |= LETTER_M;
break;
case 'N':
case 'n':
party[i] |= LETTER_N;
break;
case ',':
case '\n':
if((i++) >= PARTY_NUM) return true;
break;
}
}
fclose(pf);
return true;
}
void WriteFile()
{
FILE *pf;
pf = fopen("OUT.txt","w");
fprintf(pf,"The number is %d.\n",min);
printf("The number is %d.\n",min);
if(resualt_num)
{
int i,j;
fprintf(pf,"We have find %d arraies suitable.\n",resualt_num);
printf("We have find %d arraies suitable.\n",resualt_num);
for(i=0;i<resualt_num;i++)
{
fprintf(pf,"%d : ",i+1);
printf("%d : ",i+1);
for(j=0;j<min;j++)
{
fprintf(pf,"%d ",resualts[i][j]);
printf("%d ",resualts[i][j]);
}
fprintf(pf,"\n");
printf("\n");
}
}
else
{
fprintf(pf,"Sorry, we could not find any resault\n");
printf("Sorry, we could not find any resault\n");
}
}
评论