暴力枚举

复杂枚举

之前的题目都是只枚举了一个变量的解,编程竞赛中,往往需要你枚举的变量不止一个,甚至判断的条件也非常繁琐。

我们从小学数学的寒假作业开始:

  • □+□ = □
  • □-□ = □
  • □ × □ = □
  • □ ÷ □ = □

每个方块代表 1~13 中的一个数字,但不能重复。

例如:

6 + 7 = 13
9 - 8 = 1
3 × 4 = 12
10 ÷ 2 = 5

亦或者:

7 + 6 = 13
9 - 8 = 1
3 × 4 = 12
10 ÷ 2 = 5

这两个算作两种解法。
(交换加法、乘法前后的操作算作不同的方案。)
请你算一算,总共有多少种方案?


枚举范围循环

我们可以发现,这道题目里变量的取值范围只有 [1,13],判断条件也很明显,就是使得题目中的式子全部成立,因此是可以借助枚举算法求解的。

题目中共有 12 个空,如果我们直接枚举这 12 个空的值,程序的运行时间就太长了。事实上,我们只需要枚举等号左面的 8 个空格就可以了,等号右边的我们可以根据左边枚举的结果进行计算。

在程序中,我们可以通过多层 for 循环的方式来实现枚举多个变量。

条件判断

再来看判断条件怎么处理,显而易见,我们可以在最内层 for 里面加上所有的判断条件来检查枚举的这组解的合法性。

但是很有可能,在我们没有进入最内层 for 循环的时候,枚举的这部分解已经不合法了。
举个例子:假设我们枚举的第一个和第二个数是 7 和 8,二者相加等于 15。数的取值最大为 13,因此现在已经可以确定这组解是不合法的了,就不需要继续枚举下去。

为了方便理解,我们把每个空格编号:

c1 + c2 = □
c3 - c4 = □
c5 × c6 = □
c7 ÷ c8 = □

然后用 vis 数组来标记我们是否使用过某一个数字,如果使用过记录为 1,未使用过记录为 0。

这道题来自 蓝桥杯 第六届省赛 A 组第 6 题
试着理解思路,这里有一份可以实现功能的代码样例:

#include <iostream>

using namespace std;
int main()
{
	int c1, c2, c3, c4, c5, c6, c7, c8;
	int vis[14] = {0};
	int bypass = 0;		// 记录合法的方案数量
	
	for(c1 = 1; c1 <= 13; c1++){
		vis[c1] = 1;
		for(c2 = 1; c2 <= 13; c2++){
			if(c1 + c2 > 13 || vis[c2]){
				continue;
			}
			vis[c2] = 1;
			vis[c1 + c2] = 1;
			for(c3 = 1; c3 <= 13; c3++){
				if(vis[c3]){
					continue;
				}
				vis[c3] = 1;
				for(c4 = 1; c4 <= 13; c4++){
					if(c3 - c4 < 0 || c3 - c4 > 14 || vis[c4] || vis[c3 - c4] || c4 == c3 - c4){
						continue; 
					}
					vis[c4] = 1;
					vis[c3 - c4] = 1;
					for(c5 = 1; c5 <= 13; c5++){
						if(vis[c5]){
							continue;
						}
						vis[c5] = 1;
						for(c6 = 1; c6 <= 13; c6++){
							if(c5 * c6 > 13 || vis[c6] || vis[c5 * c6] || c6 == c5 * c6){
								continue;
							}
							vis[c6] = 1;
							vis[c5 * c6] = 1;
							for(c7 = 1; c7 <= 13; c7++){
								if(vis[c7]){
									continue;
								}
								vis[c7] = 1;
								for(c8 = 1; c8 <= 13; c8++){
									if(vis[c8] || c7 < c8 || c7 % c8 != 0 || vis[c7 / c8] || c8 == c7 / c8){
										continue;
									}
									bypass++;
								}
								vis[c7] = 0;
							}
							vis[c6] = 0;
							vis[c5 * c6] = 0;
						}
						vis[c5] = 0;
					}
					vis[c4] = 0;
					vis[c3 - c4] = 0;
				}
				vis[c3] = 0;
			}
			vis[c2] = 0;
			vis[c1 + c2] = 0;
		}
		vis[c1] = 0;
	}
	
	cout << bypass << endl;
	
	return 0;
 }  

啊这,是不是太麻烦了一下子绕不过来?
你可以看一看之后的相对简单的题目,然后再回来看看。

页面: 1 2 3 4 5 6

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注