C++ 数据结构与算法系列之枚举

目录

1、枚举

1.1 枚举法的基本思想

1.2 枚举结构

1.3 使用例子

（1）不使用优化枚举 1000000次

（2）第一次优化枚举 59976次

（3）第二次优化枚举 576次

（4）第三次优化枚举 14次

1.4 枚举的优缺点

1.5 枚举算法的优化

1.6、枚举法敲代码技巧

1.1 枚举法的基本思想

枚举法又称穷举法，枚举所有可能状态，并用问题给定的条件来约束状态，检验哪些是需要的，哪些是不需要的。

1.2 枚举结构

循环 + 判断语句

设ai1是状态元素ai的最小值，aik是状态元素ai的最大值(1≤i≤n)，

即a11≤a1≤a1k，a21≤a2≤a2k，a31≤a3≤a3k，……，an1≤an≤ank

for(a1=a11;a1≤a1k;a1++)

        for(a2=a21;a2≤a2k;a2++)

        ……

                for(ai=ai1;ai≤aik;ai++)

                ……

                        for(an=an1;an≤ank;an++)

                                if(状态(a1，…，ai，…，an)满足检验条件)

                                                输出问题的解；

1.3 使用例子

百钱买百鸡
公鸡一只五块钱，母鸡一只三块钱，小鸡一块钱三只
现在要用一百块钱买一百只鸡，每种鸡最少一只，问公鸡、母鸡、小鸡各多少只？

（1）不使用优化枚举 1000000次

枚举变量：公鸡、母鸡、小鸡
枚举范围：公鸡、母鸡、小鸡都是1-100次，总计算次数100*100*100
枚举判断条件：
钱数=100：5公鸡+3母鸡+1/3小鸡=100
总鸡数=100：公鸡+母鸡+小鸡=100
小鸡%3==0

#include 
using namespace std;
int main()
{
	for (int i = 1; i <= 100;i++) //公鸡枚举
		for (int j = 1; j <= 100;j++) //母鸡枚举
			for (int k = 1; k <= 100;k++) //小鸡枚举
			{
				if (5*i+3*j+k/3==100&&k%3==0&&i+j+k==100)
				{
					cout << "公鸡" << i << "只，母鸡" << j << "只，小鸡" << k << "只" << endl;
				}
			}
	system("pause");
	return 0;
}

那么是否可以优化呢？上面公鸡母鸡小鸡的数量都选用的1~100，其实不难看出，公鸡一只5块钱，100块钱最多能买20只，母鸡小鸡至少各有一只，所以公鸡至多18只，同样的道理，母鸡一只3块钱，就按多点算100能买34只，去掉公鸡和小鸡，最多32只，至于小鸡，一只公鸡一只母鸡，最多小鸡也就98只，反观上面的枚举次数：100*100*100=1000000次，而优化后的枚举次数：18*34*98=59976次，肉眼可见优化后的次数更少，所以下面把枚举范围缩小。

当然这个结果是不会变的，就不再详细演示。

（2）第一次优化枚举 59976次

枚举变量：公鸡、母鸡、小鸡
枚举范围：公鸡18次、母鸡32次、小鸡98次，总计算次数18*132*98
枚举判断条件：
钱数=100：5公鸡+3母鸡+1/3小鸡=100
总鸡数=100：公鸡+母鸡+小鸡=100
小鸡%3==0 

#include 
using namespace std;
int main()
{
	for (int i = 1; i <= 18;i++) //公鸡枚举
		for (int j = 1; j <= 32;j++) //母鸡枚举
			for (int k = 1; k <= 98;k++) //小鸡枚举
			{
				if (5*i+3*j+k/3==100&&k%3==0&&i+j+k==100)
				{
					cout << "公鸡" << i << "只，母鸡" << j << "只，小鸡" << k << "只" << endl;
				}
			}
	system("pause");
	return 0;
}

那么还能接着优化吗？

公鸡+母鸡+小鸡=100，三个枚举变量

那我们知道公鸡和母鸡的数量后，小鸡的数量不就是100减去公鸡和母鸡的数量吗！

这样不就可以省掉一个枚举变量了嘛！

（3）第二次优化枚举 576次

枚举变量：公鸡、母鸡
枚举范围：公鸡18次、母鸡32次，总计算次数 18*32
枚举判断条件：
钱数=100：5公鸡+3母鸡+1/3小鸡=100
小鸡%3==0

#include 
using namespace std;
int main()
{
	for (int i = 1; i <= 18;i++) //公鸡枚举
		for (int j = 1; j <= 32;j++) //母鸡枚举
                int z=100-i-j;
				if (5*i+3*j+z/3==100&&z%3==0)
				{
					cout << "公鸡" << i << "只，母鸡" << j << "只，小鸡" << z << "只" << endl;
				}
			}
	system("pause");
	return 0;
}

到这里了还能优化吗？

之前列的式子 5i+3j+1/3k=100

把这个式子*3 

15i+9j+k=300   ①  

i+j+k=100         ②

 发挥聪明才智的时候，列方程式！

14i+8j=200，即7i+4j=100

j=(100-7i)/4

k=100-i-j=100-i-(100-7i)/4

根据这个式子，有了公鸡的只数后就可以得到母鸡和小鸡的数量

前面知道j是大于等于1的，利用这个条件计算(100-7i)/4≥1

得到7i小于等于96,i≤14

（4）第三次优化枚举 14次

枚举变量：公鸡

枚举范围：公鸡1-14，总计算次数14

枚举判断条件：

钱数=100：5公鸡+3母鸡+1/3小鸡=100

小鸡%3==0

（100-7i)%4==0

#include 
using namespace std;
int main()
{
	for (int i = 1; i <= 14;i++) //公鸡枚举
    {
        if((100-7*i)%4==0)
        {
            int y=(100-7*i)/4;
            int z=100-i-j;
			if (5*i+3*y+z/3==100&&z%3==0)
			{
				cout << "公鸡" << i << "只，母鸡" << y << "只，小鸡" << z << "只" << endl;
			}
		}
    }
	system("pause");
	return 0;
}

看吧看吧，通过一次次的优化，把最开始需要1000000次枚举优化成14次枚举。

1.4 枚举的优缺点

用枚举法解题的最大缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。

但枚举算法思路简单，程序编写和调试方便，如果是在规定的时间和空间限制内能够求出解，那最好用枚举法。

1.5 枚举算法的优化

a、缩小枚举范围

b、减少枚举变量

c、使用其它算法

1.6、枚举法敲代码技巧

枚举变量：

枚举范围：

枚举判断条件：