算法与数据结构---2、枚举打赏
目录
一、总结一句话总结：1、枚举法的代码结构？2、枚举算法的常用优化？3、枚举法敲代码技巧？二、枚举一、枚举法的基本思想二、枚举法的框架结构三、枚举法的优缺点四、枚举算法的优化 五、枚举法敲代码技巧（注意）三、百钱买百鸡问题及优化1、问题2、分析及代码实现3、优化一：缩小枚举范围4、优化二：减少枚举变量5、优化三：根据题目关系，进一步减少枚举变量
回到顶部一、总结
一句话总结：
枚举法又称穷举法，它是根据题意，枚举所有可能状态，并用问题给定的条件来约束状态，检验哪些是需要的，哪些是不需要的。
1、枚举法的代码结构？
循环+判断语句，枚举几个变量就循环几次
设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k， ai1≤ai≤aik，
……，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)满足检验条件)
输出问题的解;
2、枚举算法的常用优化？
a、缩小枚举范围
b、减少枚举变量
c、使用其它算法
3、枚举法敲代码技巧？
弄清楚枚举变量、枚举范围、枚举判断条件，敲代码就非常简单，而且不容易出错了
枚举变量：
枚举范围：
枚举判断条件：
1 /
2
3 枚举变量：公鸡
4 枚举范围：公鸡1-14，总计算次数14
5 枚举判断条件：
6 钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
7 小鸡%3==0
8 (100-7x)%4==0
9
10
11 /
12 #include
13 int main()
14 {
15 for (int i = 1; i <= 14; i++)
16 {
17 if ((100 - 7 i) % 4 == 0)
18 {
19 int y = (100 - 7 i) / 4;
20 int z = 100 - i - y;
21 if (5 i + 3 y + z / 3 == 100 && z % 3 == 0)
22 {
23 printf("公鸡 %2d 只，母鸡 %2d 只，小鸡 %2d 只\n", i, y, z);
24 }
25 }
26 }
27
28 return 0;
29 }
回到顶部二、枚举
博客对应课程的视频位置：2、枚举
//代码效果参考： http://www.jhylw.com.cn/551020853.html一、枚举法的基本思想
枚举法又称穷举法，它是根据题意，枚举所有可能状态，并用问题给定的条件来约束状态，
检验哪些是需要的，哪些是不需要的。
枚举结构：循环+判断语句。
二、枚举法的框架结构
设ai1—状态元素ai的最小值；aik—状态元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k， ai1≤ai≤aik，
……，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)满足检验条件)
输出问题的解;
三、枚举法的优缺点
用枚举法解题的最大的缺点是运算量比较大，解题效率不高，如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。
但枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在比赛中，时间是有限的，我们比赛的最终目标是求出问题解，
因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么最好是采用枚举法。
四、枚举算法的优化
a、缩小枚举范围
b、减少枚举变量
c、使用其它算法
五、枚举法敲代码技巧（注意）
弄清楚枚举变量、枚举范围、枚举判断条件，敲代码就非常简单，而且不容易出错了
枚举变量：
枚举范围：
枚举判断条件：
回到顶部三、百钱买百鸡问题及优化
博客对应课程的视频位置：2、枚举
1、问题
百钱买百鸡
公鸡一只五块钱，母鸡一只三块钱，小鸡一块钱三只，
现在要用一百块钱买一百只鸡，每种鸡最少一只，问公鸡、母鸡、小鸡各多少只？
2、分析及代码实现
枚举变量：公鸡、母鸡、小鸡
枚举范围：公鸡、母鸡、小鸡都是1-100次，总计算次数100100100
枚举判断条件：
钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
总鸡数=100：公鸡+母鸡+小鸡 = 100
小鸡%3==0
1 /
2
3 百钱买百鸡
4 公鸡一只五块钱，母鸡一只三块钱，小鸡一块钱三只，
5 现在要用一百块钱买一百只鸡，每种鸡最少一只，问公鸡、母鸡、小鸡各多少只？
6
7
8 枚举变量：公鸡、母鸡、小鸡
9 枚举范围：公鸡、母鸡、小鸡都是1-100次，总计算次数100100100
10 枚举判断条件：
11 钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
12 总鸡数=100：公鸡+母鸡+小鸡 = 100
13 小鸡%3==0
14
15 /
16
17 #include
18 int main()
19 {
20 for (int i = 1; i <= 100; i++)
21 for (int j = 1; j <= 100; j++)
22 for (int k = 1; k <= 100; k++)
23 {
24 if (5 i + 3 j + k / 3 == 100 && k % 3 == 0 && i + j + k == 100)
25 {
26 printf("公鸡 %2d 只，母鸡 %2d 只，小鸡 %2d 只\n", i, j, k);
27 }
28 }
29 return 0;
30 }
3、优化一：缩小枚举范围
百钱百鸡问题优化一：
5公鸡+3母鸡+1/3小鸡 = 100
公鸡+母鸡+小鸡 = 100
缩小枚举范围
枚举变量：公鸡、母鸡、小鸡
枚举范围：公鸡1-18，母鸡1-32 ，小鸡1-98次，总计算次数183298
枚举判断条件：
钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
总鸡数=100：公鸡+母鸡+小鸡 = 100
小鸡%3==0
1 /
2
3 百钱百鸡问题优化一：
4
5 5公鸡+3母鸡+1/3小鸡 = 100
6 公鸡+母鸡+小鸡 = 100
7
8 缩小枚举范围
9
10 枚举变量：公鸡、母鸡、小鸡
11 枚举范围：公鸡1-18，母鸡1-32 ，小鸡1-98次，总计算次数183298
12 枚举判断条件：
13 钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
14 总鸡数=100：公鸡+母鸡+小鸡 = 100
15 小鸡%3==0
16
17
18 /
19
20 #include
21 int main()
22 {
23 for (int i = 1; i <= 18; i++)
24 for (int j = 1; j <= 32; j++)
25 for (int k = 1; k <= 98; k++)
26 {
27 if (5 i + 3 j + k / 3 == 100 && k % 3 == 0 && i + j + k == 100)
28 {
29 printf("公鸡 %2d 只，母鸡 %2d 只，小鸡 %2d 只\n", i, j, k);
30 }
31 }
32 return 0;
33 }
4、优化二：减少枚举变量
1 /
2
3 钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
4 总鸡数=100：公鸡+母鸡+小鸡 = 100
5
6 设公鸡 x 只，母鸡 y 只，小鸡 z 只
7
8 5x+3y+1/3z = 100
9 x+y+z = 100
10
11 枚举了x和y之后，z的值是固定的，z=100-x-y
12 所以这个时候，z就不用枚举了
13
14 枚举变量：公鸡，母鸡
15 枚举范围：公鸡1-18,母鸡1-32，总计算次数 1832
16 枚举判断条件：
17 钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
18 小鸡%3==0
19
20 优化：减少了枚举的变量
21 减少枚举的变量之后，枚举的次数大幅减少
22
23 /
24 #include
25 int main()
26 {
27 for (int i = 1; i <= 18; i++)
28 for (int j = 1; j <= 32; j++)
29 {
30 int z = 100 - i - j;
31 if (5 i + 3 j + z / 3 == 100 && z % 3 == 0)
32 {
33 printf("公鸡 %2d 只，母鸡 %2d 只，小鸡 %2d 只\n", i, j, z);
34 }
35 }
36
37 return 0;
38 }
5、优化三：根据题目关系，进一步减少枚举变量
1 /
2
3 钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
4 总鸡数=100：公鸡+母鸡+小鸡 = 100
5
6 设公鸡 x 只，母鸡 y 只，小鸡 z 只
7
8 5x+3y+1/3z = 100
9 x+y+z = 100
10
11 第一个式子*3
12 15x+9y+z = 300
13 x+y+z = 100
14
15 得：
16 14x+8y=200
17 即
18 7x+4y=100
19 y=(100-7x)/4
20 z=100-x-(100-7x)/4
21
22 根据这个式子，有x之后，我们就可以得到y，从而得到z
23 这里7x小于等于96，x取值为1-14
24
25 枚举变量：公鸡
26 枚举范围：公鸡1-14，总计算次数14
27 枚举判断条件：
28 钱数=100：5公鸡+3母鸡+1/3小鸡 = 100
29 小鸡%3==0
