论文部分内容阅读
算法是程序设计的基础，有一个良好的算法，才能设计出的高效的程序。枚举法是程序设计中最常用的算法之一，它的基本原理是根据已知条件，在给定的范围内，对所有可能的答案按某种顺序逐一枚举和检验，找出符合条件的答案。日常生活中，用枚举法会显得十分笨拙和繁琐。而计算机运算速度快，保证了枚举算法的可行性，而且思路和程序也很简单，容易理解。本文结合笔者的教学经验，谈谈如何进行枚举法的教学。
一、情境导入：猜数游戏
导入新课时，笔者设计了一个猜数字的游戏，先由学生来猜一个0—9之间的数字，如果猜对，显示“恭喜你，答对了！”；如果猜不对，则显示“很遗憾，请重来！”程序代码如下：
If Text1.Text = 8 Then
Label1.Caption = "恭喜你，答对了！"
Else
Label1.Caption = "很遗憾，请重来！"
End If
因为可猜的范围很小，很多同学能很快完成。这时，可把猜数的范围调整为10—99，只需把上面程序中数字8换成任意一个两位数即可。这个程序没有使用枚举法的相关结构，但学生逐个数尝试的过程，就是一个枚举的过程，教师说的数字的范围就是枚举的范围，有助于学生理解枚举法的基本原理。
二、讲授新课：枚举法的应用—— 一题多解
例题：百钱买百鸡问题：公鸡、母鸡分别是五元钱一只和三元钱一只，而小鸡是一元钱三只。现在用一百元钱买一百只鸡。问：一百只鸡中公鸡、母鸡、小鸡各多少只？
1.基本算法：三重循环
设购买的公鸡、母鸡、小鸡数量分别为x、y、z，根据题意，可列出如下方程：
①x+y+z=100 ②5*x+3*y+z/3=100
这个方程组有3个未知数，但只有两个方程，很明显方程的解不唯一。x、y、z的取值范围为0-100，可写出如下程序解决这个问题：
For x：=0 to 100 do
For y：=0 t 100 do
For z：=0 to 100 do
If （x+y+z=100） and （5*x+3*y+z/3=100） then writeln（x：5：0，y：5：0，z：5：0）
2.算法优化一：缩小变量的枚举范围
仍然采用三重循环，只是要缩小变量的枚举范围，以减少循环次数。因为总钱数有限，所以公鸡最多买20只，母鸡最多买33只，小鸡最多买100只，即x的取值范围为0-20，y的取值范围为0-33，z的取值范围为0-100。据此分析，可对上面的程序做出优化：
For x：=0 to 20 do
For y：=0 t 33 do
For z：=0 to 100 do
If （x+y+z=100） and （5*x+3*y+z/3=100） then writeln（x：5：0，y：5：0，z：5：0）
3.算法优化二：两重循环
由方程x+y+z=100，可推出z=100-x-y。这样，可只设x和y两个循环变量，把三重循环变成两重循环，进一步减少循环次数。对上面的程序修改如下：
For x：=0 to 20 do
For y：=0 t 33 do
Begin
z=100-x-y；
If （x+y+z=100） and （5*x+3*y+z/3=100） then writeln（x：5：0，y：5：0，z：5：0）
End；
比较以上的3种方法，方法，1的循环次数101*101*101，方法2
的循环次数为21*34*101，方法3的循环次数为21*34。
可见，枚举法看起来简单，容易掌握。但要做到程序最优化也不容易，必须深入细致地研究问题本身，精益求精地优化算法，才能最大限度地提高程序的效率。
三、拓展训练：用枚举法求解逻辑判断问题
1.枚举思想在逻辑判断时的应用
例题：警察局抓了A、B、C、D四名偷窃嫌疑犯，其中一人是
小偷。审问中A说：“我不是小偷。”B说：“C是小偷。”C说：“小偷肯定是D。”D说：“C在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？
A、B、C、D四人中每人有两种情况，要么是要小偷，要么不是
小偷。可以设两个值0和1， 0代表不是小偷，1代表是小偷。A、B、C、D四个变量的取值范围均为0-1。用枚举思想，把所以可能的情况列举出来，如果符合条件则输出。
For A：=0 to 1 do
For B：=0 to 1 do
For C：=0 to 1 do
For D：=0 to 1 do
if ord（A=0）+ord（C=1）+ord（D=1）+ ord（D=0）=3 then
begin
if A=1 then writeln（”A is a thief”）；
if B=1 then writeln（”B is a thief”）；
if C=1 then writeln（”C is a thief”）；
if D=1 then writeln（”D is a thief”）
end；
2.逻辑判断课后练习题
四个学生上地理课，回答我国四大淡水湖大小时这样说：
甲：“最大洞庭湖，最小洪泽湖，鄱阳湖第三。”
乙：“最大洪泽湖，最小洞庭湖，鄱阳湖第二，太湖第三。”
丙：“最小洪泽湖，洞庭湖第三。”
丁：“最大鄱阳湖，最小太湖，洪泽湖第二，洞庭湖第三。”
对于每个湖的大小，每个学生仅答对一个，请编程确定四个湖的大小。
四、枚举法的优缺点
枚举法虽然本质上属于搜索策略，但是与后面要学习的深度优先搜索和广度优先搜索不同，它是一种“直译”的解题方法，优点和缺点并存。
优点：枚举法一般是现实问题的直译，需要枚举大量的状态，甚至要穷举所有的状态，对其一一进行考查。因此比较直观，易于理解，算法的正确性也比较容易证明。
缺点：枚举法的效率取决于需要枚举的状态数量以及单个状态的工作量，效率一般比较低。
总之，用枚举法解题时，需要认真审题，不疏漏任何信息，根据题意准确地设置枚举对象、范围和约束条件。
一、情境导入：猜数游戏
导入新课时，笔者设计了一个猜数字的游戏，先由学生来猜一个0—9之间的数字，如果猜对，显示“恭喜你，答对了！”；如果猜不对，则显示“很遗憾，请重来！”程序代码如下：
If Text1.Text = 8 Then
Label1.Caption = "恭喜你，答对了！"
Else
Label1.Caption = "很遗憾，请重来！"
End If
因为可猜的范围很小，很多同学能很快完成。这时，可把猜数的范围调整为10—99，只需把上面程序中数字8换成任意一个两位数即可。这个程序没有使用枚举法的相关结构，但学生逐个数尝试的过程，就是一个枚举的过程，教师说的数字的范围就是枚举的范围，有助于学生理解枚举法的基本原理。
二、讲授新课：枚举法的应用—— 一题多解
例题：百钱买百鸡问题：公鸡、母鸡分别是五元钱一只和三元钱一只，而小鸡是一元钱三只。现在用一百元钱买一百只鸡。问：一百只鸡中公鸡、母鸡、小鸡各多少只？
1.基本算法：三重循环
设购买的公鸡、母鸡、小鸡数量分别为x、y、z，根据题意，可列出如下方程：
①x+y+z=100 ②5*x+3*y+z/3=100
这个方程组有3个未知数，但只有两个方程，很明显方程的解不唯一。x、y、z的取值范围为0-100，可写出如下程序解决这个问题：
For x：=0 to 100 do
For y：=0 t 100 do
For z：=0 to 100 do
If （x+y+z=100） and （5*x+3*y+z/3=100） then writeln（x：5：0，y：5：0，z：5：0）
2.算法优化一：缩小变量的枚举范围
仍然采用三重循环，只是要缩小变量的枚举范围，以减少循环次数。因为总钱数有限，所以公鸡最多买20只，母鸡最多买33只，小鸡最多买100只，即x的取值范围为0-20，y的取值范围为0-33，z的取值范围为0-100。据此分析，可对上面的程序做出优化：
For x：=0 to 20 do
For y：=0 t 33 do
For z：=0 to 100 do
If （x+y+z=100） and （5*x+3*y+z/3=100） then writeln（x：5：0，y：5：0，z：5：0）
3.算法优化二：两重循环
由方程x+y+z=100，可推出z=100-x-y。这样，可只设x和y两个循环变量，把三重循环变成两重循环，进一步减少循环次数。对上面的程序修改如下：
For x：=0 to 20 do
For y：=0 t 33 do
Begin
z=100-x-y；
If （x+y+z=100） and （5*x+3*y+z/3=100） then writeln（x：5：0，y：5：0，z：5：0）
End；
比较以上的3种方法，方法，1的循环次数101*101*101，方法2
的循环次数为21*34*101，方法3的循环次数为21*34。
可见，枚举法看起来简单，容易掌握。但要做到程序最优化也不容易，必须深入细致地研究问题本身，精益求精地优化算法，才能最大限度地提高程序的效率。
三、拓展训练：用枚举法求解逻辑判断问题
1.枚举思想在逻辑判断时的应用
例题：警察局抓了A、B、C、D四名偷窃嫌疑犯，其中一人是
小偷。审问中A说：“我不是小偷。”B说：“C是小偷。”C说：“小偷肯定是D。”D说：“C在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？
A、B、C、D四人中每人有两种情况，要么是要小偷，要么不是
小偷。可以设两个值0和1， 0代表不是小偷，1代表是小偷。A、B、C、D四个变量的取值范围均为0-1。用枚举思想，把所以可能的情况列举出来，如果符合条件则输出。
For A：=0 to 1 do
For B：=0 to 1 do
For C：=0 to 1 do
For D：=0 to 1 do
if ord（A=0）+ord（C=1）+ord（D=1）+ ord（D=0）=3 then
begin
if A=1 then writeln（”A is a thief”）；
if B=1 then writeln（”B is a thief”）；
if C=1 then writeln（”C is a thief”）；
if D=1 then writeln（”D is a thief”）
end；
2.逻辑判断课后练习题
四个学生上地理课，回答我国四大淡水湖大小时这样说：
甲：“最大洞庭湖，最小洪泽湖，鄱阳湖第三。”
乙：“最大洪泽湖，最小洞庭湖，鄱阳湖第二，太湖第三。”
丙：“最小洪泽湖，洞庭湖第三。”
丁：“最大鄱阳湖，最小太湖，洪泽湖第二，洞庭湖第三。”
对于每个湖的大小，每个学生仅答对一个，请编程确定四个湖的大小。
四、枚举法的优缺点
枚举法虽然本质上属于搜索策略，但是与后面要学习的深度优先搜索和广度优先搜索不同，它是一种“直译”的解题方法，优点和缺点并存。
优点：枚举法一般是现实问题的直译，需要枚举大量的状态，甚至要穷举所有的状态，对其一一进行考查。因此比较直观，易于理解，算法的正确性也比较容易证明。
缺点：枚举法的效率取决于需要枚举的状态数量以及单个状态的工作量，效率一般比较低。
总之，用枚举法解题时，需要认真审题，不疏漏任何信息，根据题意准确地设置枚举对象、范围和约束条件。