简单枚举法如何改进

简单枚举

枚举法是一种常见的分析问题、解决问题的方法。一般要根据问题的要求，一一列举问题进行解答。运用枚举法解应用题时，必须注意无重复、无遗漏，因此必须有次序、有规律地进行枚举。

运用枚举法解题的关键是要正确分类，要注意以下两点：一是分类要全，不能造成遗漏；二是枚举要清，要将每一个符合条件的对象都列出来。

例1 从小华家到学校有3条路可以走，从学校到文峰公园有4条路

可以走。从小华家到文峰公园有几种不同的走法？ 练习：

1、从甲地到乙地有3条公路直达，从乙地到丙地有2条铁路直达。从甲地到丙地有多少种不同的走法？

2、新华书店有3种不同的英语书、4种不同的数学书在销售，小明想买一种英语书和一种数学书，共有多少种不同买法？

3、明明有两件不同的上衣、3条不同的裤子、4双不同的鞋子，最多可搭配成多少种不同的装束？

例2 有4个小朋友，寒假中互相通一次电话，他们一共打了多少次

电话？ 练习：

1、6个小队进行排球比赛，每两队比赛一场，共要进行多少场比

赛？

2、小芳出席由19人参加的联欢会，散场后每两人都要握一次手，他们一共握了多少次手？

3、A、B、C、D、E这五个人一起回答一个问题，结果只有两个人答对了，所

简单枚举算法教案朱全民

简单枚举法 枚举法 所谓枚举法,指的是从可能的解集合中一一枚举各元素,用 题目给定的检验条件判定哪些是无用的,哪些是有用的.能 使命题成立,即为其解。一般思路： 对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围(即可能解 的范围); 利用循环语句、条件判断语句逐步求解或证明； 枚举法的特点是算法简单，但有时运算量大。对于可能确 定解的值域又一时找不到其他更好的算法时可以采用枚举 法。

虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚 举法求解的问题必须满足两个条件： ⑴可预先确定每个状态的元素个数n;⑵状态元素a1,a2,…,an的可能值为一个连续的值域。 设 ai1— 状 态 元 素 ai 的 最 小 值 ； aik— 状 态 元 素 ai 的 最 大 值 (1≤i≤n) , 即 a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ai≤aik,……,an1≤an≤ank

for a1←a11 to a1k dofo a2←a21 to a2k do for ai←ai1 to aik do …………………… ……………………

for an←an1 to ank d

简单枚举算法教案朱全民

简单枚举法 枚举法 所谓枚举法,指的是从可能的解集合中一一枚举各元素,用 题目给定的检验条件判定哪些是无用的,哪些是有用的.能 使命题成立,即为其解。一般思路： 对命题建立正确的数学模型； 根据命题确定的数学模型中各变量的变化范围(即可能解 的范围); 利用循环语句、条件判断语句逐步求解或证明； 枚举法的特点是算法简单，但有时运算量大。对于可能确 定解的值域又一时找不到其他更好的算法时可以采用枚举 法。

虽然枚举法本质上属于搜索策略，但是它与回溯法有所不同。因为适用枚 举法求解的问题必须满足两个条件： ⑴可预先确定每个状态的元素个数n;⑵状态元素a1,a2,…,an的可能值为一个连续的值域。 设 ai1— 状 态 元 素 ai 的 最 小 值 ； aik— 状 态 元 素 ai 的 最 大 值 (1≤i≤n) , 即 a11≤a1≤a1k,a21≤a2≤a2k, ai1≤ai≤aik,……,an1≤an≤ank

for a1←a11 to a1k dofo a2←a21 to a2k do for ai←ai1 to aik do …………………… ……………………

for an←an1 to ank d

精品文档

简单枚举

练习一

1、【题目】从甲地到乙地，有3条公路直达，从乙地到丙地有2条铁路直达。从甲地到丙地有多少种不同走法？

【解析】

3×2 = 6（种）

2、【题目】新华书店有3种不同的英语书，4种不同的数学读物销售。小明想买一种英语书和一种数学读物，共有多少种不同买法？

【解析】

英1——数1，英1——数2，英1——数3，英1——数4；

英2——数1，英2——数2，英2——数3，英2——数4；

英3——数1，英3——数2，英3——数3，英3——数4。

3×4 = 12（种）

练习二

1、【题目】用红、黄、蓝三种颜色涂圆圈，每个圆圈涂一种颜色，一共有多少种不同的涂法？

【解析】

红黄蓝、红蓝黄、黄蓝红、黄红蓝、蓝红黄、蓝黄红。

一共6种不同的涂法。

2、【题目】用数字1、2、3，可以组成多少个不同的三位数？分别是哪几个数？

【解析】

6个。

分别是：123、132、213、231、312、321。

3、【题目】用2、3、5、7四个数字，可以组成多少个不同的四位数？

【解析】

精品文档

精品文档

24（种）

分别是：2357、2375、2537、2573、2735、2753；

3257、1275、3527、3572、3725、3752；

5237、5273、5327、5372、5723、57

精品文档

简单枚举

练习一

1、【题目】从甲地到乙地，有3条公路直达，从乙地到丙地有2条铁路直达。从甲地到丙地有多少种不同走法？

【解析】

3×2 = 6（种）

2、【题目】新华书店有3种不同的英语书，4种不同的数学读物销售。小明想买一种英语书和一种数学读物，共有多少种不同买法？

【解析】

英1——数1，英1——数2，英1——数3，英1——数4；

英2——数1，英2——数2，英2——数3，英2——数4；

英3——数1，英3——数2，英3——数3，英3——数4。

3×4 = 12（种）

练习二

1、【题目】用红、黄、蓝三种颜色涂圆圈，每个圆圈涂一种颜色，一共有多少种不同的涂法？

【解析】

红黄蓝、红蓝黄、黄蓝红、黄红蓝、蓝红黄、蓝黄红。

一共6种不同的涂法。

2、【题目】用数字1、2、3，可以组成多少个不同的三位数？分别是哪几个数？

【解析】

6个。

分别是：123、132、213、231、312、321。

3、【题目】用2、3、5、7四个数字，可以组成多少个不同的四位数？

【解析】

精品文档

精品文档

24（种）

分别是：2357、2375、2537、2573、2735、2753；

3257、1275、3527、3572、3725、3752；

5237、5273、5327、5372、5723、57

第7讲 枚举法

1、今年是2002年，把2002年这样的年份称为“对称年”（年份的个位数字和千位数字相同，百位数字和十位数字相同），从2002年到2999年之间共有个“对称年”。

2、在所有的三位数中，满足其数字和等于12的共有个。

3、下边的加法运算，答案824正好和上面的加数428数字顺序相反，如果选出另外一个三位数加上396后，答案也正好和所选的三位数的数字顺序相反的话，可以选出若干个这样的三位数，这样的三位数还有（除去428外）个。

4、从1、2、3、4、5、6、7、8、9中选出7个数，使得它们的和是3的倍数，共有种选法。

5、一次，齐王与大将田忌赛马。每人有四匹马，分为四等。田忌知道齐王这次比赛马的出

场顺序依次为一等、二等、三等、四等，而且还知道这八匹马跑得最快的是齐王的一等马，接着依次为自己的一等，齐王的二等，自己的二等，齐王的三等，自己的三等，齐王的四等，自己的四等。田忌有种方法安排自己的马的出场顺序，保证自己至少能赢两场比赛？

6、小珊到邮局购买5张邮票，并要求这些邮票的式样都要相同且全部都要互相连接在一起（两张邮票之间只有顶点与顶点相连不算相连在一起）。现在邮局只尚存最后的九张邮票。如下图所示，为满足小珊的要求，请

第7讲 枚举法

1、今年是2002年，把2002年这样的年份称为“对称年”（年份的个位数字和千位数字相同，百位数字和十位数字相同），从2002年到2999年之间共有个“对称年”。

2、在所有的三位数中，满足其数字和等于12的共有个。

3、下边的加法运算，答案824正好和上面的加数428数字顺序相反，如果选出另外一个三位数加上396后，答案也正好和所选的三位数的数字顺序相反的话，可以选出若干个这样的三位数，这样的三位数还有（除去428外）个。

4、从1、2、3、4、5、6、7、8、9中选出7个数，使得它们的和是3的倍数，共有种选法。

5、一次，齐王与大将田忌赛马。每人有四匹马，分为四等。田忌知道齐王这次比赛马的出

场顺序依次为一等、二等、三等、四等，而且还知道这八匹马跑得最快的是齐王的一等马，接着依次为自己的一等，齐王的二等，自己的二等，齐王的三等，自己的三等，齐王的四等，自己的四等。田忌有种方法安排自己的马的出场顺序，保证自己至少能赢两场比赛？

6、小珊到邮局购买5张邮票，并要求这些邮票的式样都要相同且全部都要互相连接在一起（两张邮票之间只有顶点与顶点相连不算相连在一起）。现在邮局只尚存最后的九张邮票。如下图所示，为满足小珊的要求，请

2013思维训练（一）

——枚举法

班级： 姓名：

我们在课堂上遇到的数学问题，一般都可以列出算式，然后求出结果。但在数学竞赛或生活中却经常会遇到一些有趣的题目，由于找不到计算它们的算式，似乎无从下手。但是，如果题目所述的情况或满足题目要求的对象能够被一一列举出来，或能被分类列举出来，那么问题就可以通过枚举法获得解决。所谓枚举法，就是根据题目要求，将符合要求的结果不重复、不遗漏地一一列举出来，从而解决问题的方法。

例1：小明和小红玩掷骰子的游戏，共有两枚骰子，一起掷出。若两枚骰子的点数和为7，则小明胜；若点数和为8，则小红胜。试判断他们两人谁获胜的可能性大。

例2：数一数，右图中有多少个三角形。

例3：小明的暑假作业有语文、算术、外语三门，他准备每天做一门，且相邻两天不做同一门。如果小明第一天做语文，第五天也做语文，那么，这五天作业他共有多少种不同的安排？

例4：从1～50这50个自然数中选取两个数字，使它们的和大于50，共有多少种不同的取法？

巩固练习：

1、将6拆成两个或两个以上的自然数之和，共有多少种不同拆法？

2、小明有1

二年级提高班第五讲

枚举法的妙用

【例1】艾迪在路上碰到一个小朋友，他要从3片一样的枫树叶和2片一样的杨树叶中挑出一些拍照片，请你帮他算一算，他有多少种同的挑选方法？

【分析】这道题的情况非常多，我们可以把挑选的情况一一枚举出来．

⑴只挑选枫树叶有3种不同的方法：1片，2片，3片． ⑵只挑选杨树叶有2种不同的方

法：1片，2片．

⑶两种树叶搭配挑选可以有6种不同的方法：

①1片枫树叶和1片杨树叶 ②2片枫树叶和1片杨树叶 ③3片枫树叶和1片杨树叶 ④1片枫树叶和2片杨树叶 ⑤2片枫树叶和2片杨树叶 ⑥3片枫树叶和2片杨树叶 （种）不同所以，共有3+2+6=11的挑选方法．另外这道题我们也可以通过表格的方法进行枚举． 【例2】把12个同样大小的正方形拼成1个长方形，可以拼成几

个不同的长方形？

【分析】本题可以按行分类， 12=1×12=2×6=3×4．如图所示，共3种拼法：

【例3】用分别写着0,5,6的三张卡片，可以组成多少个不同的三位数？

【分析】0不能在百位，那么百位的数只能是5，6．百位上是5的三位数有：506，560；百位上

是6的三位数有605，650；这样用0，5，6三张卡片，可以组成

2×2=4（个）不同的三位数．因

为是卡片，所

某地甲乙两市城市发展平综合评价指数计算表

甲市综合评价指数

)(9.1577

3

.1466.3142.137862.1380.1261.157分=++++++=

I

乙市综合评价指数

)(3.2737

2

.2403.5823.1718.1242.3920.1736.229分=++++++=

I

从计算结果看乙市城市发展水平比甲市高

说明：或采用加权平均的方式，找出各个指标的权重系数

2.改进功效系数法举例

某地区四个公司经济效益指标

试用改进功效系数法对四个公司进行排名（已知第一种情况四项指标的权重系数分别相等；第二种情况四项指标的权重系数分别为30%、20%、20%、30%）

解：

现以丁公司例 404.8360403.78.163.78.124=+?--=d 6040+?--='

s h s i i x x x x d

同理，丁公司

940

.74844

.96368

.75321===d d d

同理计算出其他公司各项指标功效系数

改进功效系数表

其中，总功效系D 是按几何平均计算的 185

.82404.83940.74844.96368.7541=???==∏=n n

i i d D 丁第二种情况是采用加权几何平均方式计算