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

选修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.


相关文章:
高中信息技术 《网络技术应用》知识点 粤教版选修3
高中信息技术 《网络技术应用知识点 粤教版选修3...1 )替换法是一种常用的加密方法. 2 )两种加密...常用的密码破解手段:穷举法;黑客字典法、猜测法、...
用穷举法设计程序教学设计
普通高中信息技术(选修1) 《算法与程序设计》教材第...2节《用穷举法设计程序》的教学内容,包括用穷举法...同时,加强网页课件的辅助、提示功能,特别是对 VB ...
...教学设计-优质公开课-高中信息技术独家精品_图文
《计算机解决问题的过程》教学设计 课题:与计算机进一步亲密接触——计算机解决问题的过程 模块:普通高中信息技术《算法与程序设计》选修章第节 课时:1 课时 ...
高中信息技术教案(全套)
高中信息技术 教学设计 1 - - 1.1 信息及其特征...师:(课件演示) 2.信息的价值性。 (1)信息不能...也为必修模 块的其他章节和各选修模块开展多元化交流...
高中信息技术教师考试试卷及参考答案
粤教版普通高中选修2《多... 7页 1下载券 高中...技术文化与信息文化理念的表达 13.对于任务驱动教学...A.解析法 B.穷举法 C.分治法 D.递归法 27....
高中信息技术会考试题必修选修考试试题及答案
高中信息技术会考试题必修选修考试试题及答案_其它课程_高中教育_教育专区。一、解决...答案:穷举法 、分析程序写出运行结果或补全程 序。 1. Dim a as integer...
《算法与程序设计》选修教案_图文
《算法与程序设计》选修教案_其它课程_高中教育_教育专区。高中信息技术算法教案 ...3 第教学目标 用计算机解决问题 (1)让学生了解算法、穷举法、程序...
高中信息技术Flash第一课ppt_图文
高中信息技术Flash第ppt_学科竞赛_高中教育_教育专区。Flash 软件学习内容...2.在“动画”图层的第 40 帧处插入个关键帧,并将“泡沫”图形移动到场景...
用穷举法解决问题教学设计
穷举法解决问题 、 教材分析: 《用穷举法解决问题高中信息技术选修模块《算法与程序设计》第三章《程序 的实现节内容。 本章侧重于运用算法解决...
《穷举法》
高一年级 算法与程序设计(选修) 课时 1 一、 指导...二、 教学分析 1、教学目标 知识与技能 (1) 理解...《穷举法》是江苏省高中信息技术教材第三章第二节...
更多相关标签: