枚举算法(穷举法)(暴力法)

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;
}