题目 1125: C语言训练-委派任务*

题目描述

某侦察队接到一项紧急任务，要求在A、B、C、D、E、F六个队员中尽可能多地挑若干人，但有以下限制条件：
1)A和B两人中至少去一人；
2)A和D不能一起去；
3)A、E和F三人中要派两人去；
4)B和C都去或都不去；
5)C和D两人中去一个；
6)若D不去，则E也不去。
问应当让哪几个人去？

输入格式

无

输出格式

要派出的人
若有多个，按字母递增顺序排列，用逗号分开（含末尾逗号）
 

样例输入

复制

无

样例输出

复制

A,B,C,F,

这个鬼题还是第一次做，，一开始毫无头绪啊，还是要借鉴大佬

1.思路，创建变量，初始值为0 ，，逐步增加，1代表去，0 代表不去

然后用for循环遍历，，先上一个可以过的代码

#include<stdio.h>
void print(int a, int b, int c, int d, int e, int f)
{
	if (a == 1)
	{
		printf("A,");
	}
	if (b == 1)
	{
		printf("B,");
	}
	if (c == 1)
	{
		printf("C,");
	}
	if (d == 1)
	{
		printf("D,");
	}
	if (e == 1)
	{
		printf("E,");
	}
	if (f == 1)
	{
		printf("F,");
	}
}

int judg(int a, int b, int c, int d, int e, int f)
//这里我找到了每个要求的反面，，，思路比在一个if里面写一大堆要清晰
{
	if (a == 0 && b == 0)
	{
		return 0;
	}
	if (a == 1 && d == 1)
	{
		return 0;
	}
	if ((b == 0 && c == 1) || (b == 1 && c == 0))
	{
		return 0;
	}
	if ((c == 0 && d == 0) || (c == 1 && d == 1))
	{
		return 0;
	}
	if (d == 0 && e == 1)
	{
		return 0;
	}

	if (a == 0 && e == 0 && f == 0)//去0个
	{
		return 0;
	}
	if ((a == 1 && e == 0 && f == 0) || (a == 0 && e == 1 && f == 0) || (a == 0 && e == 0 && f == 1))
	{
		return 0;
	}
	if (a == 1 && e == 1 && f == 1)
	{
		return 0;
	}

	return 1;
}
int main()
{
	int a = 0; int b = 0; int c = 0;
	int d = 0; int e = 0; int f = 0;

	for (a = 0; a < 2; a++)
	{
		for (b = 0; b < 2; b++)
		{
			for (c = 0; c < 2; c++)
			{
				for (d = 0; d < 2; d++)
				{
					for (e = 0; e < 2; e++)
					{
						for (f = 0; f < 2; f++)
						{
							int k = judg(a, b, c, d, e, f);//判断是否满足条件
							if (k == 1)
							{
								print(a, b, c, d, e, f);//输出函数
								return 0;
							}
						}
					}
				}
			}
		}
	}

	return 0;

}

 然后咱们来改进，这个代码的问题有

1. 如果符合条件就过，无法找到最优解

2.传参麻烦，，要传好几个参数，，懒！

3.在判断过程中还有不同的方法

改进：对于创建6个变量，不如创建一个数组吧，然后对每一种可能取值都进行记录，最后找到满足条件的最优解！！！@#￥%……

#include<stdio.h>
void change(int arr[10], int a, int b, int c, int d, int e, int f)
{
		if (a == 1)
	{
			arr['a' - 'a' + 1]++;
	}
	if (b == 1)
	{
		arr['b' - 'a' + 1]++;
	}
	if (c == 1)
	{
		arr['c' - 'a' + 1]++;
	}
	if (d == 1)
	{
		arr['d' - 'a' + 1]++;
	}
	if (e == 1)
	{
		arr['e' - 'a' + 1]++;
	}
	if (f == 1)
	{
		arr['f' - 'a' + 1]++;
	}
}
void print(int arr[10])
{
	int i = 0;
	for (; i<7; i++)
	{
		if (arr[i] == 1)
		{
			printf("%c,", i + 'A' - 1);
		}
	}
}

int judg(int a, int b, int c, int d, int e, int f)
{
	if (a == 0 && b == 0)
	{
		return 0;
	}
	if (a == 1 && d == 1)
	{
		return 0;
	}
	if ((b == 0 && c == 1) || (b == 1 && c == 0))
	{
		return 0;
	}
	if ((c == 0 && d == 0) || (c == 1 && d == 1))
	{
		return 0;
	}
	if (d == 0 && e == 1)
	{
		return 0;
	}

	if (a == 0 && e == 0 && f == 0)//去0个
	{
		return 0;
	}
	if ((a == 1 && e == 0 && f == 0) || (a == 0 && e == 1 && f == 0) || (a == 0 && e == 0 && f == 1))
	{
		return 0;
	}
	if (a == 1 && e == 1 && f == 1)
	{
		return 0;
	}

	int num = 0;
	if (a == 1) { num++; }
	if (b== 1) { num++; }
	if (c  == 1) { num++; }
	if (d== 1) { num++; }
	if (e  == 1) { num++; }
	if (f== 1) { num++; }
	return num;
}
int main()
{

	//创建一个只有7位的数组，用123来代替abc，
	//
	// 然后为了记录，我想到用个二维数组，或者结构体，
	//有2的6次方中方法，就二的六次方行

	int i = 0;


	int a = 0; int b = 0; int c = 0;
	int d = 0; int e = 0; int f = 0;
	int arr[100][10] = { 0 };
	
		for (a = 0; a < 2; a++)
		{
			for (b = 0; b < 2; b++)
			{
				for (c = 0; c < 2; c++)
				{
					for (d = 0; d < 2; d++)
					{
						for (e = 0; e < 2; e++)
						{
							for (f = 0; f < 2; f++)
							{
								int k = judg(a, b, c, d, e, f);
								if (k!=0)
								{
									arr[i][0] = k;
									change(arr[i], a, b, c, d, e, f);
									i++;
								}
							}
						}
					}
				}
			}
		}
	//

		int max = arr[0][0];
		int max_id = 0;
		int j = 0;
		for (j = 0; j < i; j++)
		{
			if (arr[j][0] > max)
			{
				max = arr[j][0];
				max_id = j;
			}
		}

		print(arr[max_id]);
		return 0;
}

尽力了，这样就可以实现找对最优解