穷举法,又称列举法、枚举法,或称为暴力破解法,是蛮力策略的具体体现,是一种简单而直接地解决问题的方法。

经典例题:素数判断,鸡兔同笼,最大连续子序列,火柴棍等式,计算几何距离

穷举法是什么?

穷举法,又称列举法、枚举法,或称为暴力破解法,是蛮力策略的具体体现,是一种简单而直接地解决问题的方法。

穷举法的基本思想是根据题目的部分条件确定答案的大致范围,并在此范围内对所有可能的情况逐一验证,直到全部情况验证完毕。若某个情况验证符合题目的全部条件,则为本问题的一个解;若全部情况验证后都不符合题目的全部条件,则本题无解。

从计算机的有限集合中,对每一个可能解进行判断,直到找到正确的答案。使用穷举法主要是要获取有限集合,然后一一枚举获取需要的答案。

穷举的作用

1.理论上,穷举可以解决可计算领域中的各种问题。尤其处在计算机计算速度非常高的今天,穷举的应用领域是非常广阔的。

2.在实际应用中,通常要解决的问题规模不大,用穷举设计的算法其运算速度是可以接受的。此时,设计一个更高效率的算法代价不值得。

3.穷举可作为某类问题时间性能的底限,用来衡量同样问题的更高效率的算法。

基本思路

穷举法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下:

1.对于一种可能的情况,计算其结果。

2.判断结果是否符合要求,如果不满足则执行第1步来搜索下一个可能的情况;如果符合要求,则表示寻找到一个正确答案。

在使用穷举法时,需要明确问题的答案的范围,这样才可以在指定的范围内搜索答案。指定范围之后,就可以使用循环语句和条件语句逐步验证候选答案的正确性,从而得到需要的正确答案。

经典例题

素数判断

问题:找出一个区间[100,200]内部的素数.

如果一个常数n不能整除任意一个大于2并且小于n的整数,那么这个数就称之为素数。

我们来分析一下这个问题,第一题目已经明确给定了集合区间,第二题目已经给定判定条件,我们只需要遍历集合区间内的所有常数,执行一片判断条件,就能找出所有的素数,求出题目的答案,所以满足使用穷举算法的条件。

穷举法求解素数判断问题C语言实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "stdio.h"

bool checkPrime(int number){
for (int i=2; i<number; i++){
if (number%i == 0){
return false;
}
}
return true;
}

int main() {
int min, max, t;
printf("输入最小数:\n");
scanf("%d", &min);
printf("输入最大数:\n");
scanf("%d", &max);
if (min>max) {
printf("输入数据有误!\n");
return 1;
}

printf("区间范围%d~%d的素数为:\n", min, max);
for (int i=min; i<=max; i++) {
if (checkPrime(i)) {
printf("%d\n", i);
}
}
return 0;
}

鸡兔同笼

鸡兔同笼问题最早记载中1500年前的《孙子算经》,这是我国古代一个非常有名的问题。鸡兔同笼问题的原文如下:今天鸡兔同笼,上有三十五个头,下有九十四足,问鸡兔各几何?这个问题的大致意思是:在一个笼子里关着若干只鸡和若干只兔,从上面看共有35个头,从下面数共有94只脚。问笼中鸡和兔的数量各是多少?

这个问题需要计算鸡的数量和兔的数量,我们通过分析可以知道鸡的数量应该在1~35之间。这样我们可以使用穷举法来逐个判断是否符合,从而搜索答案。

穷举法求解鸡兔同笼问题C语言实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
using namespace std;
/*
输入参数head是笼中头的总数,foot是笼中脚的总数,chicken是鸡的总数,rabbit是兔的总数
返回结果为0,表示没有搜索到符合条件的结果;
返回结果为1,表示搜索到了符合条件的结果
*/
int qiongju(int head, int foot, int *chicken, int *rabbit) {
int re,i,j;
re=0;
for (i=0;i<=head;i++) { //进行循环
j=head-i;
if (i*2+j*4==foot) { //进行判断
re=1; //找到答案
*chicken=i;
*rabbit=j;
}
}
return re;
}

int main() {
int chicken,rabbit,head,foot;
cout<<"穷举法求解鸡兔同笼问题:"<<endl;
cout<<"请输入头数:";
cin>>head;
cout<<"请输入脚数:";
cin>>foot;
int res=qiongju(head,foot,&chicken,&rabbit);
if (res==1) {
cout<<"鸡有"<<chicken<<"只,兔有"<<rabbit<<"只。"<<endl;
} else {
cout<<"无法求解!"<<endl;
}
return 0;
}

最大连续子序列

给定K个整数的序列{ N_1, N_2, …, N_K},其任意连续子序列可表示为{ Ni, Ni+1, …, Nj},其中 1<=i<=j<=K。最大连续子序列是所有连续子序列中元素和最大的一个,例如给定序列{-2, 11, -4, 13, -5, -2 },其最大连续子序列为{11, -4, 13},最大和为20。

Input: 测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数K(<10000),第2行给出K个整数,中间用空格分隔。当K为0时,输入结束,该用例不被处理。

Output: 对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元素,中间用空格分隔。如果最大连续子序列不唯一,则输出序号i和j最小的那个(如输入样例的第2、3组)。若所有K个元素都是负数,则定义其最大和为0,输出整个序列的首尾元素。

穷举法求解最大连续子序列C语言实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;

int main() {
int a[200] = {0}; // 数组a记录整数序列
// count记录负数个数
// max 最大和 max_f 最大和最前端 max_l最大和最后端
int n, i, j, s, count, max, max_f, max_l;

// 以输入作为循环条件实现多组数据的输入
while(cin>>n) {
if ( n == 0 ) return 0;

// 特殊情况的判断
count = 0;
for ( i = 0; i < n; ++i ) {
cin>>a[i];
if ( a[i] < 0 ) count++; //记录负数个数
}

if (count == n) {
max = 0;
max_f = a[0];
max_l = a[n-1];
} else { // 大多数情况的操作
max = a[0];max_f = a[0];max_l = a[0];
for ( i = 0; i < n; ++i ) { // 从a[0]开始计算各情况
s = a[i];
for ( j = i+1; j < n; ++j ) { // 算法 可草稿推演
s += a[j];
if (s>max) { //寻找最大
max = s;
max_f = a[i];
max_l = a[j];
}
}
}
}
// 输出结果
cout<<max<<" "<<max_f<<" "<<max_l<<endl;
}
return 0;
}

火柴棍等式

给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。

用火柴棍拼数字0-9的拼法如图所示:

火柴棍等式

注意

1.加号与等号各自需要两根火柴棍

2.如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C>=0)

3.n根火柴棍必须全部用上

输入格式: 输入共一行,又一个整数n(n<=24)

输出格式: 输出共一行,表示能拼成的不同等式的数目

样例1

输入: 14, 输出: 2

2个等式为:0+1=1和1+0=1。

样例2

输入: 18, 输出: 9

9个等式为:0+4=4, 0+11=11, 1+10=11, 2+2=4, 2+7=9, 4+0=4, 7+2=9, 10+1=11, 11+0=11

其实是一道很简单的枚举题。

首先看范围,火柴棒的个数小于等于24,减去加号、等号后只有二十根。

再看每位数字需要的火柴棒数目,发现1最少,只要两根。

那么尽量多添1使得组成的数尽可能大,发现当填到1111时,火柴棒组成基本超过24,故我们大致找到一个范围小于等于1111。

最后只需在0~1111内枚举两个数字,使得它们和它们的和组成的火柴棒个数为n。

穷举法求解火柴棍等式问题C语言实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int num[100],ans1,i,j,n,l;
int main() {
scanf("%d",&n);
num[0]=6; num[1]=2; num[2]=5; num[3]=5; num[4]=4;
num[5]=5; num[6]=6; num[7]=3; num[8]=7; num[9]=6;
n-=4;

if (n<9) { cout<<"0"<<endl; return 0; }

for (i=0;i<=1001;i++) {
for (j=0;j<=i;j++) {
int x=i-j;
char s1[10],s2[10],s3[10];
sprintf(s1,"%d",i);
sprintf(s2,"%d",j);
sprintf(s3,"%d",x);
int ans=0;
for (l=1;l<=strlen(s1);l++)
ans+=num[s1[l-1]-48];
for (l=1;l<=strlen(s2);l++)
ans+=num[s2[l-1]-48];
for (l=1;l<=strlen(s3);l++)
ans+=num[s3[l-1]-48];
if (ans==n)
ans1++;
}
}
printf("%d",ans1);
return 0;
}

计算几何距离

今天小明考完了期末考试,他在教学楼里闲逛,他看着教学楼里一间间的教室,于是开始思考:如果从一个坐标为 (x1,y1,z1)的教室走到(x2,y2,z2)的距离为 |x1−x2|+|y1−y2|+|z1−z2|,那么有多少对教室之间的距离是不超过R的呢?

输入
第一行是一个整数T(1≤T≤10), 表示有T组数据,接下来是T组数据,对于每组数据: 第一行是两个整数 n,q(1≤n≤5×104,1≤q≤103), 表示有n间教室, q次询问. 接下来是n行, 每行3个整数 xi,yi,zi(0≤xi,yi,zi≤10),表示这间教室的坐标. 最后是q行,每行一个整数R(0≤R≤109).

输出
对于每个询问RR输出一行一个整数,表示有多少对教室满足题目所述的距离关系.

样例输入

1
2
3
4
5
6
1 
3 3
0 0 0
1 1 1
1 1 1
1 2 3

样例输出

1
2
3
1 
1
3

对于样例,1号教室和2号教室之间的距离为3, 1号和3号之间的距离为3, 2号和3号之间的距离为0

题意:在一个三维空间中有N个点,q次查询,每次查询给一距离r,求出三维空间中有多少对点之间的哈密顿距离小于r。

思路:一开始的时候如果按照朴素的想法,先离线处理,两两配对求出每两个点之间的距离,之后输出,但是本题中点的数目n的数据较大,如果要全部处理的话需要109左右的操作数,肯定会超时。那么这个时候我们仔细观察后发现,每一个点的范围很小,0<=x,y,z<=10,如果我们通过坐标来遍历每一个点,那么就只需要10^3的复杂度,显然更合适。所以本题也是如此,通过以坐标为单位的枚举,就可以得到最后的结果.

穷举法求解几何距离问题C语言实现代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int n, q, t, tem;
int a, b, c, x, y, z;
LL aa[35];
LL dex[15][15][15];

int dis(int aa, int bb, int cc, int xx, int yy, int zz) {
return abs(aa-xx)+abs(bb-yy)+abs(cc-zz);
}

int main() {
scanf("%d",&t);
while(t--) {
memset(aa, 0, sizeof(aa));
memset(dex, 0, sizeof(dex));
scanf("%d%d",&n,&q);
while(n--) {
scanf("%d%d%d",&x,&y,&z);
++dex[x][y][z];
}
for (a = 0; a <= 10; ++a)
for (b = 0; b <= 10; ++b)
for (c = 0; c <= 10; ++c)
if (dex[a][b][c])
for (x = 0; x <= 10; ++x)
for (y = 0; y <= 10; ++y)
for (z = 0; z <= 10; ++z)
if (dex[x][y][z]) {
tem = dis(a, b, c, x, y, z);
if (tem == 0)
aa[tem] += (dex[x][y][z])*(dex[x][y][z]-1)/2;
else
aa[tem] += dex[x][y][z]*dex[a][b][c];
}
for (int i = 1; i <= 30; ++i)
aa[i] /= 2;
for (int i = 1; i <= 30; ++i)
aa[i] += aa[i-1];
while(q--) {
scanf("%d",&tem);
if (tem > 30)
tem = 30;
printf("%lld\n",aa[tem]);
}
}
return 0;
}

备选题目

  • 换分币:用一元人民币兑换成1分、2分和5分硬币,有多少种不同的兑换方法?请输出所有可能的方案。
  • 年龄几何:张三、李四、王五、刘六的年龄成一等差数列,他们四人的年龄相加是26,相乘是880,求以他们的年龄为前4项的等差数列的前20项
  • 三色球问题:若一个口袋中放有12个球,其中有3个红的。3个白的和6个黒的,问从中任取8个共有多少种不同的颜色搭配?