当前位置:首页 >> 高中作文 >>

选修1《穷举法》ppt课件2 高中信息技术


穷举法(枚举法)

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

用穷举法解决问题
? 计算机的特点之一就是运算速度快、善于 重复做一件事情,“穷举法”正是基于这 一特点的最古老的算法。它一般是一

时找 不到解决问题的更好的途径,即从数学上 找不到求解的公式或者规则时,根据问题 中的“约束条件”,将解的所有可能情况 一一列举出来,然后再逐一验证是否符合 整个问题的求解要求,从而得到问题的所 有解。

示例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) 的解元素,即为问题的解。

Grammar
金手指考试网 http://www.jszksw.net/ 2016年金手指驾驶员考试科目一 科目四 元贝驾考网 http://www.yuanbeijiakao.net 科目一科目四仿真考试题C1

8

穷举法的使用范围
– 能确定解变量(枚举变量)的个数 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,j-1]*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.


相关文章:
《穷举法》
搜 试试 帮助 全部 DOC PPT TXT PDF XLS ...(选修) 课时 1 一、 指导思想 依据信息技术课程...《穷举法》是江苏省高中信息技术教材第三章第二节...
穷举法教学设计(高中信息技术精品)
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...穷举法教学设计(高中信息技术精品)_其它课程_高中...(选修1) 《算法与程序设计》教材第 三章第2节的...
用穷举法设计程序教学设计(高中信息技术精品)
3、掌握用穷举法设计程序的一般步骤。 (二)过程与...普通高中信息技术(选修1) 《算法与程序设计》教材第...多媒体课件 六、教学过程 教学环 教师活动 节 1、...
高中信息技术Flash第一课ppt
高中信息技术Flash第ppt_学科竞赛_高中教育_教育专区。Flash 软件学习内容...2.在“动画”图层的第 40 帧处插入个关键帧,并将“泡沫”图形移动到场景...
4.2 用穷举法设计程序教学设计(高中信息技术精品)
本节内容是广东教育出版社出版的普通高中信息技术(选修1) 《算法与程序设计》教材第四章第 2节的教学内容,包括有穷举法的基本思路,用穷举法求解问题,穷举法中...
高一信息技术第一课(含ppt演示和教师简案)
高一信息技术课(含ppt演示和教师简案)_其它课程_高中教育_教育专区。高中第...教材上其余的内容安排到第二堂课上用。 而且是开学的第周, 通常学生机房的...
2011年高中信息技术真题
每题 1 分,共60 分) 1.普通高中阶段的技术课程...学生在获得必修的学分之后至少再选修 2 个模块,并...D.③④①② 38.穷举法的适用范围是 ( A.一切...
高中《信息技术基础》1.2算法描述与设计教案
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...高中《信息技术基础》1.2算法描述与设计教案_其它课程...讲授法,演示法,实践法 2 教学过程 学生活动 导入 ...
2010高中信息技术
1/2 相关文档推荐 高中2010信息技术模拟试... 16...分别表示选修模块“算法与程序设计”“网络技术应用”...A.排序与查找 B.递归法 C.穷举法 D.解析法 【...
3.2 用穷举法解决问题教学设计(高中信息技术精品)
3.2穷举法解决问题教学设计(高中信息技术精品)_...课选自教科版《算法与程序设计》选修第三章的第二...系统套 软件:Visual Basic 软件、自制的课件 【...
更多相关标签:
高中化学选修4课件ppt | 高中化学选修3课件ppt | 高中化学选修5课件ppt | 高中数学选修2 1课件 | 高中物理选修3 1课件 | 高中数学选修1 1课件 | 高中化学选修1课件 | 高中数学选修2 2课件 |