枚举算法（穷举法）（暴力法）

1.什么是枚举

枚举是指在一定范围内将所有情况一一列举，再通过条件判断得到自己想要的答案；

2.枚举核心

3.使用枚举的基本步骤

 

 4.例题

4.1.我国古代数学家张丘建在他的《算经》一书中提出了著名的“百钱买百鸡”问题:鸡翁一值钱五;鸡母一值钱三;鸡雏三值钱一。百钱买百鸡,问鸡翁、鸡母、鸡雏各几何?

枚举对象：坤翁：x；坤母：y；坤雏：z（100 - x - y）；

枚举范围（最大值为100钱全买同一种的数量）：坤翁0~20；坤母0~33；坤雏0~100（个数上限为100）

判断条件：共一百只且共一百钱

#include<iostream>int main()
{using namespace std;for (int x = 0; x <= 20; x++){for (int y = 0; y <= 33; y++){for (int z = 0; z <= 100; z++){if ((x + y + z == 100) && (x * 5 + y * 3 + z / 3 == 100))cout << x << ' ' << y << ' ' << z << endl;}}}return 0;
}

 但是三层循环效率太低，可以优化成：

#include<iostream>int main()
{using namespace std;for (int x = 0; x <= 20; x++){for (int y = 0; y <= 33; y++){if ((x * 5 + y * 3 + (100 - x - y) / 3 == 100))cout << x << ' ' << y << ' ' << (100 - x - y) << endl;}}return 0;
}

4.2对于长度为5位的一个o1串，每一位都可能是О或1，一共有32种可能。
它们的前几个是:
00000
00001

00010

00011

00100

00101

00110

00111
请按从小到大的顺序输出这32种01串。

#include<iostream>int main()
{using namespace std;int count = 0;for (int a = 0; a <= 1; a++){for (int b = 0; b <= 1; b++){for (int c = 0; c <= 1; c++){for (int d = 0; d <= 1; d++){for (int e = 0; e <= 1; e++){++count;cout << a << b << c << d << e << endl;}}}}}cout << count << endl;return 0;
}

4.3将一个数进行质因数分解并输出

短除法：

 

#include <iostream>int main()
{using namespace std;int n;cin >> n;for (int i = 2; i <= n; i++){while (n % i == 0){cout << i << ' ';n = n / i;}}return 0;
}

由于2是最小的质数，同时2是检验偶数的标准，所以一直除以2直到不能整除时，n就为奇数，

然后就换下一个能够整除的质数继续除，直到n = 1；

4.4有一个n×m方格的棋盘，求其方格包含多少正方形、长方形(不包含正方形)。
输入格式：
一行，两个正整数n,m

输出格式
—行，两个正整数，分别表示方格包含多少正方形、长方形(不包含正方形)。

 

 组合问题：

#include <iostream>int main()
{using namespace std;int n, m;int sum_Cube = 0;int sum_Cuboid = 0;cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (i == j)sum_Cube += (n - i + 1) * (m - j + 1);else{sum_Cuboid += (n - i + 1) * (m - j + 1);}}}cout << sum_Cube << ' ' << sum_Cuboid << endl;return 0;
}