当前位置:首页 >> 学科竞赛 >>

穷举法


穷举法(枚举法)

学习目标
? ?

? ?

理解穷举法的思想方法 学会分析建立正确的穷举步骤,归纳穷 举法的穷举技巧 学会优化穷举算法 学会使用穷举法解决现实生活、学习中 遇到的问题

用穷举法解决问题
?

计算机的特点之一就是运算速度快、善 于重复

做一件事情,“穷举法”正是基 于这一特点的最古老的算法。它一般是 一时找不到解决问题的更好的途径,即 从数学上找不到求解的公式或者规则时, 根据问题中的“约束条件”,将解的所 有可能情况一一列举出来,然后再逐一 验证是否符合整个问题的求解要求,从 而得到问题的所有解。

示例1
?

求满足表达式A+B=C的所有整数解,其 中A,B,C为1~3之间的整数。

解题思路
?

?
? ?

?

本题非常简单,即枚举变量A,B,C的所有可能 取值情况,对每种取值情况判断是否符合表 达式即可。 算法如下 for A:=1 to 3 do for B:=1 to 3 do for C:=1 to 3 do
if(A+B=C) then writeln(A,’ ‘,B,’ ‘,C);

穷举法的定义
?

所谓穷举法,指的是从可能的解的集合 中一一枚举各元素,用题目给定的检验 条件判定哪些是无用的,哪些是有用的。 能使命题成立的,即为解。

解题思路
?

示例中的解变量有3个:A,B,C。其中 解变量A的可能取值范围A∈{1, 2 ,3} 解变量B的可能取值范围B∈{1, 2 ,3} 解变量C的可能取值范围C∈{1, 2 ,3} 从而问题的可能解有3*3*3=27个,可能解集: (A,B,C)∈{(1,1,1),(1,1,2),(1,1, 3),…,(3,3,1),(3,3,2),(3,3, 3)} 在上述可能解集中,满足题目给定的检验条件 (A+B==C)的解元素,即为问题的解。

?

穷举法的使用范围
– 能确定解变量(枚举变量)的个数 n ; – 每个解变量Ai(1 <= i <= n)的可能值能 确定范围且能连续取得。

算法框架
设解变量的个数是n,Ai1—解变量Ai的最小值;Aik—解变量Ai的最 大值(1≤i≤n),即A11≤A1≤A1k,Ai1≤Ai≤Aik,……, An1≤An≤Ank 算法框架如下(伪代码): for A1←A11 to A1k do for A2←A21 to A2k do …………………… for Ai←Ai1 to Aik do …………………… for An←An1 to Ank do if 状态(A1,…,Ai,…,An)满足检验条件 then 输出问题的解;

示例2
?

“水仙花数问题” 。 水仙花数是指一个 三位数,它的各位数的立方和,正好是等 于该数本身。例如153=1^3+5^3+3^3。 请设计算法求解100-999其他的水仙花。

解题思路
?

?

?

该数的百位范围1-9,十位范围0-9,个 位范围0-9 约束条件:该数的个、十、百位数的立 方和正好是等于该数本身 程序结构选择:三重循环
能优化吗?

解题思路
? ?

?

三位数范围100-999 约束条件:该三位数的各位数的立方和 正好是等于该数本身 程序结构选择:一重循环

穷举法
? ?

枚举法的特点是算法简单,但有时运算量大。 优化枚举算法(考察重点)
枚举算法的时间复杂度=状态总数*考察单个状态 的耗时 – 排除明显不属于解集的元素 – 减少状态总数(即减少枚举变量和枚举变量的值 域) – 降低单个状态的考察代价

示例1优化程序
?

示例算法显然可以修改如下:
for A:=1 to 3 do for B:=1 to 3 do begin C:=A+B; if(C>=1)and(C<=3) then 输出A,B,C; end 通过变量的依赖关系减少了解变量的个数(局部枚 举),优化了枚举算法,n^3 -> n^2。

示例3
?

公鸡一只值5元,鸡母一只值3元,小鸡 三只值1元。现在有100只鸡,正好值 100元钱,问公鸡、母鸡和小鸡各有几 只?

设 变量设置为:X表示公鸡只数,Y表示母鸡只数,Z表示小鸡只数。 穷举时如何利用好百鸡和百钱两个已知条件,选择合适的穷举方法,使程序最优化? 变量设置:试找出下列变量的最小穷举范围 X穷举范围: ___________________ Y穷举范围: _________________ Z穷举范围: ___________________ 优化一下可以考虑 Z的设置方式: ___________________ 减少穷举的范围和不必要的穷举是优化穷举算法的关键。

练习
?

完全数 古希腊人称因子的和等于本身 的数是完全数,例如28的因子是1、2、 4、7、14,而1+2+4+7+14=28,所以 28是一个完全数。编程输出2~1000内 所有的完全数。

破解密码
?

一张单据上有一个5位数的编号,其百 位数和十位数已经变得模糊不清,但是 知道这个5位数是37或67的倍数。现在 要求设计一个算法,找出所有满足这些 条件的5位数,并统计这些5位数的个数。

NO.25**6

? ?

?
? ? ? ?

n:=25006; For i:=0 to 99 do Begin n:=n+i*100; if (n mod 37=0)or(n mod 67 =0) then writeln(n); End;

猜冠军
?

A,B,C,D,E,F 6人参加跳高决赛,甲乙 丙丁4人猜测谁是冠军: 甲说:“冠军不是A,就是B。” 乙说:“冠军决不是C” 丙说:“DEF都不可能是冠军。” 丁说:“冠军可能是DEF中的一个” 比赛成绩公布时发现,这4个人所说的话中, 只有一句话是对的。你能断定谁是冠军吗?

?

提示:本题关键在问题的转化 设定冠军为X(1<=X<=6) 甲乙丙丁四个人的话可以用逻辑表达式表示 如下: 甲:X=1 OR X=2 乙:X<>3 丙:X<=3 丁:X>=4

? ? ?

?
? ?

?
? ?

For x := 1 To 6 do begin s := 0 If (x = 1) Or (x = 2) Then s = s + 1; If (x <> 3 )Then s = s + 1; If (x <= 3) Then s = s + 1; If (x >= 4 )Then s = s + 1; If( s = 1) Then writeln( "冠军是 ", x) End;

?

输入一根木棒的长度,将该木棒分成三 段,每一段的长度为正整数;输出由这 三段小木棒组成的不一样边长的三角形 的个数。如输入10,则输出2,能组成 的两个三角形边长为2、4、4 和3、3、 4。

?

四皇后问题 在4*4的棋盘上安置4个皇 后,要求任意两个皇后不在同一行、同 一列、同一对角线上,输出所有可能的 皇后放置方案。

分析:

1) 本题是一个搜索问题,搜索范围 44,找出符 合条件的方案;
2)方案必须满足的条件:任意两个不在同一行、 同一列和同一对角线。

? ? ? ? ? ? ?

?
? ? ? ? ?

?
?

const n=4; type stack=array[1..n] of integer; var i1,i2,i3,i4:integer; s:stack; function check:boolean; var i,j:integer; begin for i:=1 to n-1 do for j:=i+1 to n do if (s[i]=s[j]) or (s[i]-i=s[j]-j) or (s[i]+i=s[j]+j) then begin check:=false; exit end; check:=true end;

?
? ? ? ? ? ? ? ? ? ?

?
? ? ? ?

procedure print; var i:integer; begin for i:=1 to n do write(s[i]:2); writeln end; begin for i1:=1 to n do for i2:=1 to n do for i3:=1 to n do for i4:=1 to n do begin s[1]:=i1;s[2]:=i2;s[3]:=i3;s[4]:=i4; if check then print; end; end.

?

将1~9这九个数字填入 九个空格中。每一横行 的三个数字组成一个三 位数。如果要使第二行 的三位数是第一行的两 倍, 第三行的三位数是 第一行的三倍, 应怎样 填数。(一共4组解, 一组如下图)

1

9

2

3

8

4

5

7

6

?

本题目有9个格子,要求填数,如果不 考虑问题给出的条件,共有9! =362880种方案,在这些方案中符合问 题条件的即为解。因此可以采用枚举法。 但仔细分析问题,显然第一行的数不会 超过400,实际上只要确定第一行的数 就可以根据条件算出其他两行的数了。 这样仅需枚举400次。(优化

?

? ? ?

?
? ? ? ? ? ?

program ex_8(input,output); var i,j,k,s:integer; function sum(s:integer):integer; begin sum:=s div 100+s div 10 mod 10+s mod 10 end;{sum} function mul(s:integer):longint; begin mul:=(s div 100)*(s div 10 mod 10)*(s mod 10) end;{mul}

? ? ? ? ? ? ? ?

?
? ? ?

?
? ? ?

Begin for i:=1 to 3 do for j:=1 to 9 do if j<>i then for k:=1 to 9 do if (k<>j) and (k<>i) then begin s:=i*100+j*10+k; if 3*s<1000 then if (sum(s)+sum(2*s)+sum(3*s)=45) and (mul(s)*mul(2*s)*mul(3*s)=362880) then begin writeln(s); writeln(2*s); writeln(3*s); writeln; end; end; end.

阿姆斯特朗数。
?

问题描述:编一个程序找出所有的三位 数到七位数中的阿姆斯特朗数。 阿姆 斯特朗数也叫水仙花数,它的定义如下: 若一个n位自然数的各位数字的n次方 之和等于它本身,则称这个自然数为阿 姆斯特朗数。例如 153(153=1*1*1+3*3*3+5*5*5) 是一个三位数的阿姆斯特朗数,8208则 是一个四位数的阿姆斯特朗数。

引入
算法描述: for I:=100 to 9999999 do begin 拆分I各位上的数字; 计算I的位数; 验证是否是阿姆斯特朗数,若是则输出; end;

? ?

算法分析: 为了使得程序尽快运行出正确结果,程序中使 用了一个数组power存放所有数字的各次幂 之值, power[i,j]等于i的j次方。变量 currentnumber存放当前要被验证的数,数 组digit存放当前数的各位数字,开始时 digit[3]=1,其它元素均为0,此时表示当前数 为100。 highest为当前数的位数

? ? ? ?

?
? ? ? ? ? ? ?

程序: program ex3(input,outoutp); const maxlen=7; var i,j,currentnumber,highest,sum,total:longint; digit:array [0..maxlen+1] of integer; power:array [0..9,0..maxlen] of longint; begin for i:=0 to 9 do begin power[i,0]:=1; for j:=1 to maxlen do power[i,j]:=power[i,j1]*i end;

?
? ? ? ? ? ? ? ?

for i:=1 to maxlen do digit[i]:=0; digit[3]:=1; highest:=3; currentnumber:=100; total:=0; while digit[maxlen+1]=0 do begin sum:=0; for i:=1 to highest do
sum:=sum+power[digit[i],highest]; if sum=currentnumber then begin total:=total+1; write(currentnumber:maxlen+5); if total mod 6=0 then writeln end;

?
? ?

?

?
? ? ? ? ? ?

digit[1]:=digit[1]+1; i:=1; while digit[i]=10 do begin digit[i+1]:=digit[i+1]+1; digit[i]:=0; i:=i+1 end; if i>highest then highest:=i; currentnumber:=currentnumber+1 end; writeln end.

? ? ?


相关文章:
穷举法详细
穷举法详细_高一数学_数学_高中教育_教育专区。NOIP&ACM 第三讲 穷举法一、穷举法的基本概念 穷举方法是基于计算机特点而进行解题的思维方法。 一般是在一时找不...
用穷举法设计程序
穷举法设计程序_数学_自然科学_专业资料。《穷举法解决问题》教学设计 《用穷举法设计程序》一、教学目标 1、知识与技能 ⑴了解穷举法的基本概念及用穷举法设计...
《用穷举法解决问题》教学设计
《用穷举法解决问题》教学设计 用穷举法解决问题》江苏省新沂市第一中学 张奉华(221400) 教材分析与教法: 一、 教材分析与教法:首先,我校选择《算法与程序设计》...
穷举法
穷举法_学科竞赛_小学教育_教育专区。用穷举法解决问题教学设计 【教材分析】 本节课选自教科版《算法与程序设计》选修第三章的第二节。本节课讲的是现实生活中...
用穷举法解决问题教学设计
穷举法解决问题 一、 教材分析: 《用穷举法解决问题》是高中信息技术选修模块《算法与程序设计》第三章《程序 的实现》 第二节内容。 本章侧重于运用算法解决...
穷举法
穷举法_学科竞赛_小学教育_教育专区。计数法导学案 课题:穷举法 审核: 课型:新授 使用时间: 执笔: 一、学习目标 1、 字典排列法 2、 累加法 二、重点难点 ...
1穷举法
常用算法—穷举法重点:1、穷举法的基本思想 2、利用穷举法设计程序的基本步骤和方法 3、穷举技巧(方案的确立和变量的安排等) 难点:1、确定穷举方案和安排变量 2...
4-2节 用穷举法设计程序
(5).通过调试不同的例程,掌握穷举法穷举技巧(变量安排、穷举方案的确定)。 (6).计算机只是人类的工具,穷举方案的确定得靠人脑来完成,但穷举过程的实施计算 机...
穷举法破解远程登录windows系统的密码
穷举法破解远程登录windows系统的密码_电脑基础知识_IT/计算机_专业资料。穷举法破解远程登录windows系统的密码 穷举法破解远程登录 windows 系统的密码一、首先用工具...
穷举法
穷举法_学科竞赛_小学教育_教育专区。循环结构的嵌套应用举例 —穷举法(VB)教材: 《Visual Basic 程序设计》高教版 内容:用穷举法解决问题 教师:株洲市中等职业学...
更多相关标签:
穷举 | 穷举法破解密码 | 幸运破解器 | 穷举法 英文 | 枚举法 | 穷举法密码破解器 | c语言穷举法 | 弱密码 |