枚举算法

ACM算法--枚举⽅法（指数枚举，组合枚举）模板

// 递归实现指数型枚举

vector chosen;

void calc(int x) {

if (x == n + 1) {

for (int i = 0; i < chosen.size(); i++)

printf("%d ", chosen[i]);

puts("");

return;

}

calc(x + 1);

chosen.push_back(x);

calc(x + 1);

chosen.pop_back();

}

// 递归实现组合型枚举

vector chosen;

void calc(int x) {

if (chosen.size() > m || chosen.size() + (n - x + 1) < m) return;

if (x == n + 1) {

for (int i = 0; i < chosen.size(); i++)

printf("%d ", chosen[i]);

puts("");

return;

}

calc(x + 1);

chosen.push_back(x);

calc(x + 1);

chosen.pop_back();

}

// 递归实现排列型枚举

int order[20];

bool chosen[20];

void calc(int k) {

if (k == n + 1) {

for (int i = 1; i <= n; i++)

printf("%d ", order[i]);

puts("");

return;

}

for (int i = 1; i <= n; i++) {

if (chosen[i]) continue;

order[k] = i;

chosen[i] = 1;

calc(k + 1);

chosen[i] = 0;

order[k] = 0;

}

}

// 模拟机器实现，把组合型枚举改为⾮递归

枚举算法

一、定义：

枚举法就是按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，若是，我们采纳这个解，否则抛弃它。在列举的过程中，既不能遗漏也不应重复。

通过生活实例，理解枚举算法的定义，找出枚举算法的关键步骤及注意点

1．在枚举算法中往往把问题分解成二部分：

（1）一一列举：

这是一个循环结构。要考虑的问题是如何设置循环变量、初值、终值和递增值。循环变量是否参与检验。（要强调本算法的主要是利用计算机的运算速度快这一特点，不必过多地去做算法优化工作。）

（2）检验：

这是一个分支结构。要考虑的问题是检验的对象是谁？逻辑判数后的二个结果该如何处理？

2．分析出以上二个核心问题后，再合成：

要注意循环变量与判断对象是否是同一个变量。

3．该算法的输入和输出处理：

输入：大部分情况下是利用循环变量来代替。

输出：一般情况下是判断的一个分支中实现的。

用循环结构实现一一列举的过程，用分支结构实现检验的过程，理解枚举算法流程图的基本框架。

二、算法实例

【例5】．求1-1000中，能被3整除的数

对该问题的分析：

（1）从1-1000一一列举，这是一个循环结构

（2）在循环中对每个数进行检验。

凡是能被3整除的数，打印输出，否则继续下一个数。

【例6】．找出[1，1000]中所有能被7和11整除的数

本例参照上例，修改其中的判断部分。

【例7】. 一张单据上有一个5位数的编号，万位数是1，千位数时4，百位数是7，个位数、十位数已经模糊不清。该5位数是57或67的倍数，输出所有满足这些条件的5位数的个数。

【例8】一张单据上有一个5位数的编号，万位数是1，千位数时4，十位数是7，个位数和百位数已经模糊不清。该5位数是57或67的倍数，输出所有满足这些条件的5位数的个数。

【例9】．找水仙花数（若三位数x=100a+10b+c，满足a3+b3+c3=x，则x为水仙花数）

《枚举算法》教学设计

苍南县成人教育中心学校 陈荣军

一、教学目标

1、知识与技能目标：

理解枚举算法的基本原理，熟悉枚举算法程序设计的基本思路及程序结构特点；学会使用枚举算法解决现实生活、学习中所遇到的问题。

2、过程与方法:

围绕“课堂任务导航程序”，通过课堂任务设计，让学生熟悉用枚举算法求解问题的基本过程，并把它运用到实际生活中去解决问题，学会选择适当的枚举方法多角度分析问题，解决问题。

3、情感态度与价值观：

激发学生的学习热情，提高学生自主学习能力，增强学生创新意识；引导学生关注枚举算法在社会生活中的应用，并以此培养学生将算法思想运用到解决实际问题中去的能力。

二、学情分析

本节内容的教学对象是普通高中高一学生，他们经过半学期的信息技术教学，具备了一定的计算机操作能力；在VB程序设计方面，也已经有所学习，具备一定的基础，但因所上课时不多，学生对VB还只是略知皮毛，语法及编程能力有待于进一步提高。

三、教材分析

1、本节主要内容介绍

枚举算法是程序设计中使用最为普遍、学生必须熟练掌握和正确运用的一种算法。它利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检查，从中找出符合要求的答案。用枚举算法解决问题，通常可以从确定范围、逐一列举，验证条件、逐一验证这两个方面进行分析，把这两个方面分析好了，问题自然会迎刃而解。

2、重点难点分析

教学重点：

（1）理解枚举算法的基本原理。

（2）能根据问题描述确定枚举范围，并能用程序正确表示验证条件。

（3）枚举算法的程序实现。

教学难点：

（1）各种枚举算法的优劣评价。 （2）编程实现枚举算法。

四、教学设计理念 采用了以学生的学习和发展为中心，基于建构主义理论的任务驱动、情境教学等教学方法，突出自主、合作、探究等学习方法；强调信息技术与生活实际的联系，培养学生的逻辑思维能力、解决问题的能力以及创新意识等；设置多元化的评价方式，让学生掌握学习内容的同时，形成交流与评价的能力。

枚举法

在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法．

枚举法是利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，因此枚举法是通过牺牲时间来换取答案的全面性。

在数学和计算机科学理论中，一个集的枚举是列出某些有穷序列集的所有成员的程序，或者是一种特定类型对象的计数。这两种类型经常（但不总是）重叠。

特点

将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，合适就保留，不合适就丢弃。例如：

找出1到100之间的素数。需要将1到100之间的所有整数进行判断。

枚举算法因为要列举问题的所有可能的答案，所有它具备以下几个特点：

1、得到的结果肯定是正确的；

2、可能做了很多的无用功，浪费了宝贵的时间，效率低下。

3、通常会涉及到求极值（如最大，最小，最重等）。

4、数据量大的话，可能会造成时间崩溃。

结构

枚举算法的一般结构：while循环。

首先考虑一个问题：将1到100之间的所有整数转换为二进制数表示。

算法一：

for i:=1 to 100 do begin

将i转换为二进制，采用不断除以2，余数即为转换为2进制以后的结果。一直除商为0为止。

end;

算法二：二进制加法，此时需要数组来帮忙。

program p;

var a:array[1..100] of integer; {用于保存转换后的二进制结果}

i,j,k:integer;

begin

fillchar(a,sizeof(a),0); {100个数组元素全部初始化为0}

for i:=1 to 100 do begin k:=100;

while a[k]=1 do dec(k); {找高位第一个为0的位置}