北师大 数学必修3算法同步讲义 第21节 顺序结构与选择结构.docx
《北师大 数学必修3算法同步讲义 第21节 顺序结构与选择结构.docx》由会员分享,可在线阅读,更多相关《北师大 数学必修3算法同步讲义 第21节 顺序结构与选择结构.docx(28页珍藏版)》请在冰点文库上搜索。
![北师大 数学必修3算法同步讲义 第21节 顺序结构与选择结构.docx](https://file1.bingdoc.com/fileroot1/2023-5/1/be99b819-b7b1-4f23-98a3-d9ecabaa058a/be99b819-b7b1-4f23-98a3-d9ecabaa058a1.gif)
北师大数学必修3算法同步讲义第21节顺序结构与选择结构
§2算法的基本结构及设计
2.1顺序结构与选择结构
现在的大学里一般计算机都要学习C语言,这是一种结构化程序设计语言,它既具有高级语言的重点,又具有低级语言的许多特点,因此,既适合编写应用程序,又适合编写系统程序。
学习和使用C语言需要有一定的软、硬件基础知识。
其中最主要内容是算法的构成要素和三种基本结构,那么算法的基本结构有哪些呢?
上一节中“韩信点兵”的算法与“素因数”的算法有什么区别?
❶研习教材重难点
研习点1:
顺序结构
1.顺序结构及其基本框架
我们已经能够用自然语言来描述算法,但是看起来不够直观、形象.如果能像研究函数那样,借助于图形,形象、直观地表示出算法,那将有助于我们对算法的理解.通常说“一图胜万言”,就是这个道理.
教材例1向我们展示了确定线段的5等分点的作图算法的自然语言描述算法和算法图表.这种图表称之为流程图.
知识链接:
通常,算法流程图由程序框和流程线组成.一个或几个程序框的组合表示算法中的一个步骤;流程线是方向箭头,按照算法进行的顺序将程序框连结起来.用规定式样的图形、指向线和文字组合起来表示算法.构成流程图的符号如下图所示
N-S结构化流程图(1973年由美国学者I.Nassi和B.Shneiderman提出,N和S是这两位学者英文姓名的第一个字母).
例1中算法是按作图的顺序设计的算法结构,数学中常见的作图问题一般都是按照尺规作图的规则来作图的,此种顺序就是一种算法.如例1,按步骤依次执行的一个算法,称为具有“顺序结构”的算法,或者称为算法的顺序结构.从图2-4中我们可以看到
此算法流程图用到了流程图中的起止框,
多个处理框和流程线.它们构成了顺序结构
流程图的基本框架.
顺序结构流程图形式如图所示:
2.顺序结构的作用及特点
顺序结构是最简单的算法结构,顺序结构由若干个依次执行的处理步骤组成,任何算法都离不开顺序结构.
【联想·质疑】顺序结构有哪些特点?
顺序结构流程图中步骤能否互换?
①.顺序,就是一步一步地,不能跳跃,也不能回头.顺序结构的特点:
是直观、清楚,便于检查和交流,计算机按书写的先后次序,自上而下逐条顺序执行程序语句,中间没有选择或重复执行的过程.
①顺序结构流程图步骤必须按顺序执行,不能随意的进行互换.若任意交换其中的两个位置的顺序,则算法将无法进行到底,即虚线框内各步是依次执行的,是一个顺序结构.
顺序结构是指按书写顺序依次执行的算法结构.数学中常见的问题一般都是顺序结构的算法.如代数中的求平均数、方差、⋯⋯几何中的作图问题、⋯⋯
思考与交流(P97)
(1)可以仿照例1的作法,第1-6步骤中依次作出线段得线段AC的8倍、16倍、64倍、100倍,下面的步骤相同,则可得任意给定线段的8等分、16等分、64等分、100等分问题.
(2)这一算法是解决任意线段等分问题的最佳方法,也可以应用测量的方法进行等分线段.
例题1:
写出求半径为5的圆的面积的算法的程序流程图.
[研析]其算法步骤为:
1.取r=5;
2.计算S=πr2;
2.输出S.
这个算法的流程图如图所示.
研习点2:
选择结构
1.选择结构及其基本框架
日常生活中我们经常会面对一些选择和判断,教材例2是一个闰年的判断问题,其判断过程中需要对一些问题作出分析,其算法设计中应用了三个选择判断框,其作用是用于作出一次判断后(是否能被4整除),对判断的结果再一次进行新的判断(能被4整除,则能否被100整除).
[知识链接]闰年问题:
在公历(格里历)纪年中,有闰日的年份叫闰年,一般年份365天,闰年为366天。
由于地球绕太阳运行周期为365天5小时48分46秒(合365.24219天)即一回归年,公历把一年定为365天。
所余下的时间约为四年累计一天,加在二月里,所以平常年份每年365天,二月为28天,闰年为366天,二月为29天。
因此,每400年中有97个闰年,闰年在2月末增加一天,闰年366天。
闰年的计算方法:
公元纪年的年数可以被四整除,即为闰年;被100整除而不能被400整除为平年;被100整除也可被400整除的为闰年。
如2000年是闰年,而1900年不是。
通过例2的分析可以得到选择结构的概念:
在解决某些具体问题时,有时需要根据不同的条件选择不同的算法,同时,要先判断,根据判断的结果决定后面的步骤,这样的结构通常称作选择结构.
选择结构的算法流程图如图所示,当算法执行到条件结构中的条件时,
必定满足“真”、“假”中的一个
出口,并且只能执行“是”、“否”
中的一个出口.其显著特点是事先要判
断条件的真假,根据判断执行不同的处理.
2.选择结构的作用及特点
在许多算法中,需要对问题的条件作出逻辑判断,判断后依据条件是否成立而进行不同的处理方式,这就需要用条件结构来实现算法.
【积累·活用】哪类问题的算法需要选用选择结构?
在生活中,我们根据天气的变化选择交通工具,增减衣服;去邮局寄信贴邮票的问题,个人所得税的计算问题,都属于需要根据不同的条件选择不同结果的类型,这些设计时均选用条件结构的程序框图.同样在程序中,根据条件的不同,则执行不同的指令.
凡涉及分类问题的算法常用到选择结构,它是依据指定条件选择执行不同处理的结构.
改变条件框中的条件能实现“是”、“否”的调位.这与我们原来学习过的不等式表示范围的知识、集合中的补集和简易逻辑中的逻辑关系有密切联系.如“
”的“是”与“
”的“否”是等价的,“整除”中的“是”与“不被整除”中的“否”是等价的.
【领悟·整合】选择结构具有什么特征,应用选择结构有哪些注意点?
选择结构的特点:
在程序执行过程中出现了分支,要根据不同情况选择其中一个分支执行.其显著特征是事先要判断条件的真假,根据判断执行不同的处理.
应用选择结构时需要注意以下几点:
(1)必须准确对条件作出是与否的判断,以决定下一步的执行步骤;
(2)作图过程中要注意是与否条件的后一步骤的正确选择,即A与B的位置不可互换;
归纳整理:
如何识别与认识教材中图2-4和图2-7中算法的流程图?
流程图中的符号具有哪些功能?
如何画流程图?
下面通过具体的例子说明几个基本的程序框和它们各自表示的功能.
起止框是任何流程不可缺少的,表示程序的开始和结束;输入、输出框可用在算法中任何输入、输出的位置;算法中间要处理数据或计算,可分别写在不同的处理框内;当算法要求你对两个不同的结果进行判断时,要写在判断框内;一个算法步骤到另一个算法步骤用流程线连结.
3.流程图表示算法需要遵循哪些的规则?
为了使大家彼此之间能够读懂各自画出的框图,必须遵守一些共同的规则:
(1)使用标准的框图符号;
(2)框图一般按从上到下、从左到右的方向画;
(3)除判断框外,大多数流程图符号只有一个进入点和一个退出点,判断框是具有超过一个退出点的唯一符号;
(4)一种判断框是“是”与“不是”两分支的判断,而且有且仅有两个结果;另一种是多分支判断,有几种不同的结果;
(5)在框图符号内描述的语言要非常简练清楚.
【辨析·比较】条件结构与顺序结构不同的地方在哪里?
条件结构不同于顺序结构的地方是:
它不是依次执行操作指令进行运算,而是依据条件作出逻辑判断,选择执行不同指令中的一个.一般地,这里的判断主要是判断“是”(即“Y”)或“否”(即“N”),即是否符合条件的要求,因而它有一个入口和两个出口.
例题2:
现有如图所示的一个程序流程图,请仔细研究
该程序的作用,回答下列问题.
(1)该程序的功能是什么?
(2)如果输入5,0,-1,则输出的值分别是什么?
[研析]识图能力是一个重要的数学解题能力,根据流程图,
判断程序的功能,或根据流程图写出算法步骤,解题过程中常出
现的问题是将程序的步骤顺序倒置,特别是判断框的选择.
本题中根据流程图得出每一步骤的意义后,对程序功能的总结
也是一个不易掌握的要点,解题时可适当用草图演示一下,也可以先
代入不同的数据,根据数据结论,由特殊推广到一般.
(1)从该流程图来看,该程序首先输入一个实数a,
如果这个数是a≥0,结果就输出这个数,如果这个数是a<0,
则输出它的相反数,所以说这个程序是用来求一个任意实数的绝对值的.
(2)如果输入5,0,-1,则输出的值分别5,0,-1.
探究解题新思路
▲基础思维探究
题型1.公式计算与求值问题
典例1:
.试画一个计算
的算法流程图.
[研析]如图所示.
[探索·发现]
显然应用顺序结构即可解决这一简单的计算问题,本问题可以的算法不仅可以计算
还可以用于计算任意两数之积问题.那么三个数相乘求积,四个数相乘呢?
应用此流程图,只需在中间再加入几步计算即可,即只需对第一次计算两数的积,再与下面的一个数相乘,就可以得三个或四个,甚至更多的数相乘的积的算法.
【拓展·变式】
1.求1×2×3×4×5×6×7,试设计不同的算法并画出流程图.
典例2:
画出由梯形两底a、b和高h,求梯形面积的算法流程图.
[研析]由于
只需输入数值,即可得其面积式,
故应用顺序结构写出其算法流程图.算法流程图如图所示.
[辨析·比较]
此算法为面积公式和运算,与求值计算问题有明显的不同,其运算过程中无数据,均用字母表示,这一特征最有非常大的优越性,即任意数据均可以代入其中,作为梯形的两底和高的值,得对应的梯形的面积.即此算法即为任意的梯形的面积运算程序.求值问题仅是此运算中的一个特例,它们间的不同之处可以用函数与函数值间的关系进行类比比较.
公式的计算与求值运算问题常应用顺序结构设计算法.此类问题的特点是运算的步骤较少,按公式或数与式的运算法则的顺序依次进行运算,即可得其结论,公式算法是求值运算的一般情形,更具有可推广性、通用性、简明性的特征.
【拓展·变式】
2.已知直线l1:
Ax+By+C1=0和直线l2:
Ax+By+C2=0,写出直线l1与直线l2的距离d的算法流程图.
题型2.分段函数的算法
典例3:
函数
请设计算法流程图,要求输入自变量,输出函数值.
[研析]其程序流程图如图所示.
[类比·扩展]
本例给出的分段函数为三段,应用选择结构时,有两次选择,注意的是这两次选择第二次是在第一次的判断基础上的又一次选择,其两次选择可以相互交换顺序,但其对应的下一步执行要相应改变.其实对于分段函数超过三段以上的同样可以应用选择结构设计算法,只需相应的增加选择框即可.
分段函数代表了一类选择结构的算法,此类问题设计算法时需要注意第一步判断的选择,因为后面的每一步判断均取决于它.当其段超过三个以上时,一般可以取“外边界”范围作为第一选择判断支,其余判断支则可以按顺序依次设计入算法程序.
【拓展·变式】
3.有这样一个分段函数y=
如何设计一个流程图来描述这个分段函数所表示的算法.
▲综合思维探究
题型1学科内综合题
典例4.有关专家建议,在未来几年内,中国的通货膨胀率保持在3%左右,这将对我国经济的稳定有利无害.所谓通货膨胀率为3%,指的是每年消费品的价格增长率为3%.在这种情况下,某种品牌的钢琴2004年的价格是10000元,请用流程图描述这种钢琴今后四年的价格变化情况,并输出四年后的价格.
【研析】用P表示钢琴的价格,不难看出有如下的算法步骤:
2005年
;
2006年
;
2007年
;
2008年
;
因此,价格的变化情况表为:
年份
2004
2005
2006
2007
2008
钢琴的价格
10000
10300
10609
10927.27
11255.09
程序框图如右图所示为:
方法探究
本题所反映的顺序结构只须严格按照传统的解决数学问题的解题思路,将问题解决掉.其中连续四次运算P=PM的目的是将每一个得到的新值P代入下一步运算,根据题目的要求,需要多次次运算,就给出多少个运算框.这就是将解题步骤“细化”.“细化”指的是写出算法步骤、画出程序框图.
【拓展·变式】
4.一个地区的人口数约为45647人,并且每年人口增长率为2.8%,请用流程图表示一下这个地区5年后的人口..
题型2学科间渗透题
典例5.某快递公司规定甲、乙两地之间物品的托运费用根据下列方法计算:
其中f(单位:
元)为托运费,ω为托运物品的重量(单位:
千克),试画出计算费用f的程序框图.
[研析]费用的计算公式随物品重量的变化而有所不同,因此计算时先看物品的重量,在不同的条件下,执行不同的指令,这是条件结构的运用,是二分支条件结构.其中,物品的重量通过输入的方式给出.
相应的算法:
1.输入物品重量ω;
2.如果ω≤50,那么f=0.53ω,否则,f=50×0.53+(ω-50)×0.85;
3.输出物品重量ω和托运费f.
其程序流程图如图所示.
[积累·活用]
设计算法时应先作好设计,即每一步的程序要能够心中有数,本题是日常生活中常见的邮购物品听邮费计算问题,要注意其控制条件可改为“ω>50?
”.则此时“是”与“否”需作对换.
【拓展·变式】
5.如果学生的成绩大于或等于60分,则输出“及格”,否则输出“不及格”.用程序框图表示这一算法过程.
题型3实际应用题
典例6.国家法定工作日内,每周工作时间满工作量为40小时,每小时工资8元;如因需要加班,则每小时工资为10元.某小姐在一周内工作时间为x小时,个人住房公积金\,失业险等合计为10%.试画出其净得工资y元的算法的流程图.(注:
满工作量外的工作时间为加班)
[研析]是否加班,工资有费用不同,则只需找出比较值即可,由于每周工作时间满工作量为40小时,则超过40与小于40工资的结算方式要用两种方式来计算,故用选择结构设计算法.算法流程图如图所示.
推广引申
条件结构叠加的一般形式是:
1.它可以解决实际问题中的根据不同的情况(一般在两种情况以上)
分类讨论并按不同方式处理的问题;
2.所涉及的条件1、条件2、……一般不能同时成立,否则会出现同一
情况不同处理的结果.也就是条件必须将不同的情况区别开来;
3.它适合于三分段及以上的分段函数求值、含参数方程的求解……多
种情况的分类讨论问题;
4.该种形式结构,程序在执行时对所有的条件都要进行判断.
【拓展·变式】
6.某班级一次数学考试,成绩满分为100分,现对该班的成绩进行分析评价:
成绩超过80分的记为“A”,低于60分的记为“C”,其他的记为“B”.请设计算法,当输入的数学成绩为
时,输出相应的评价结果.(写出算法,画出程序框图.
▲创新思维探究
题型1开放探究题
典例7.画出解不等式ax+b>0(b≠0)的程序框图.
[研析]不等式的解问题需要分类讨论,即分
分类依次进行讨论,并选择不同的结论,故考虑用选择结构设计算法.
算法流程图如图所示.
[技巧点拨]
不等式分类标准
是选择结构的分类依据,每一个分类支就对应着一个选择判断框图,选择框图的两个出口一个是是,一个是否,是与否往往决定后续分类的各种情形.解决中能够辨析清楚此分界,则可轻松解决此类问题.
【拓展·变式】
7.画出从a,b,c三个数中找出最大值的算法流程图.
题型2课标创新题
典例8.求方程x2+ax+b=0的解的过程的算法流程图.
[研析]其程序流程图如图所示.
[梳理·总结]
一元二次方程的求根公式是方程求解的关键,一元二次方程的根一般有三种情形,算法设计时抓住了
的值的正负与是否为零作两次判断,分别得出方程有一解,有两解及无解的结论.本题若将方程引申为ax2+bx+c=0,则这个算法比较复杂,要清楚每一个过程和每一个环节,不能漏掉任何一种可能,否则算法是错误的,从分析可以看出有5种不同的输出形式.
【拓展·变式】
8.写出方程ax2+bx+c=0的解的算法,并用流程图描述这个算法.
❸开拓学习新视野
▲课标知识拓展
【探求新知】
遗传算法简介
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。
它最早由美国密执安大学的Holland教授提出,起源于60年代对自然和人工适应系统的研究。
70年代DeJong基于遗传算法思想在计算机上进行了大量的纯数值函数优化计算实验。
在一系列研究工作的基础上,80年代由Goldberg进行归纳总结,形成遗传算法的基本框架。
我国有关遗传算法的研究从90年代以来一直处于不断上升的时期,特别是近年来,遗传算法的应用在许多领域取得了令人瞩目的成果。
遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的领域和种类。
对一个需要进行优化和计算的实际应用问题,一般可按下述步骤来求解问题的遗传算法。
1.确定决策变量及其各种约束条件,机确定出个体的表现型X和问题的解空间。
2.建立优化模型,即确定出目标函数的类型(是求目标函数的最小值还是最大值)及其数学描述形式或量化方法。
3.确定表示可行解的染色体编码方法,即确定出个体的基因X及遗传算法的搜索空间。
4.确定编码方法,即确定出个体基因型X到个体表现型X的对应关系或转换方法。
5.确定个体适应度的量化评价方法,即确定出由目标函数值f(x)到个体适应度F(x)的转换规则。
6.设计遗传算子,即确定出选择算子、交叉运算、变异运算遗传算子的具体操作方法。
7.确定遗传算法的有关运行参数,即确定出遗传算法的M、T、Pc、Pm等分数
▲领悟数学之妙
【数学趣闻】
算法应用之平安错车
两列火车相对而行如图之有一段旁轨可以利用怎样才能平安错车?
为了方便起见我们把左边的列车叫做“动力号”,右侧的火车叫做“前进号”
在解这个算法是索要涉及的铁轨有四段:
左边至旁轨间的那段正规(标为A)。
从旁轨一段转辙器至另一端转辙器之间的那段正规(C)、旁轨B、旁轨至右侧间的那段正规(D)。
指令“前进到A”的意思是“前进号”的火车(包括车头即现在挂在它后面的所有车厢)向前移动,直到正列货车全部进入A段。
当然,两列火车的车厢各为n节,“动力号”火车的车头标为P1,其车厢为P2、P3……指令“挂上Pk”的意思是把“动力号”的Pk车厢挂在“前进号”火车上。
现在可以给出这个算法了:
1.“动力号”火车完全分开
2.对于k=1至n+1
前进到A挂上Pk
后退到D前进到C
脱挂Pk后退到D
前进到A后退到C
挂上Pk后退至D
脱挂Pk
3.“动力号”火车在连接起来
第一步是把问题城的货车全部分开成单独的车头及n节车厢。
接着算法进入一个循环,该循环内有十一个步骤反复执行,有“前进号”的火车来完成循环内的全部指令。
开始时整列“前进号”火车前进到A,在A端挂上问题城火车的车头P1,然后它牵引着P1后退到D,扳动旁轨转辙器,把P1推入B。
此时它与P1脱挂,又退回到D段。
再次扳动转辙器后,他又前进到A。
接着他在退回入旁轨,挂上P1,把P1从旁轨推到D段。
在与P1脱挂。
“前进号”火车对问题城的火车的每节车厢反复执行以上步骤,直到主循环圈全部执行完毕。
此时,问题城的整列火车就调到了“前进号”火车原来的位置上,于是它就可以前进了。
下面的两个问题,请你想一想,你能给出解决问题的算法吗?
问题一:
一列火车想掉头,他只有铁路旁边的一小段副轨,长度恰好容得下一节车厢,该如何做呢?
问题二:
左下方有一座不坚固的桥,这座桥只有一节车厢那么长,能勉强承担一节车厢的重量但车头不能经过,如何将两个车厢对调?
优化考题新演练
一、理解与应用
1.流程图中表示判断框的是( )
A.矩形框B.菱形框C.圆形框D.椭圆形框
2.1+2+3+4+…+________>2004,在横线上写出最小的正整数为()
A.61B.62C.63D.64
二、拓展与创新
3.完成下面的表格:
图形符号
名称
符号表示的意义
起、止框
(1)
(2)
数据的输入或结果的输出
(3)
赋值、执行计算语句、结果的传送
(4)
(5)
(6)
流程进行的方向
4.如图所示,下面是求解一元二次方程ax2+bx+c=0(a≠0)的流程图,请在空缺的地方填上适当的标注.
第4题图
三、综合与探究
5.已知点P(x0,y0)和直线l:
Ax+By+C=0,求点P到直线l的距离.用流程图表示这种算法.
6.写出函数f(x)=x2-2x,当x=2时,求函数值的算法.说明应用哪种算法结构.
7.设计求|x|的算法,并画出流程图.
8.如图所示,下面流程图表示了一个什么样的算法?
第8题图
本节答案与解析研读
【拓展·变式】
1.流程图如图所示.
2.直线l1:
Ax+By+C1=0和直线l2:
Ax+By+C2=0的距离d
所以应用顺序结构作出其算法流程图.算法流程图如图所示.
3.算法流程图如图所示.
4.应用顺序结构表示程序框图如图所示.
5.显然成绩大于或等于60分,则输出“及格”,否则输出“不及格”,需要输入变量A,对A的值与60的大小关系作出判断,用两条路径对其中一种作出选择.其流程图如图所示.
6.算法步骤:
第一步,输入学生的数学成绩.
第二步,判断该同学的数学成绩是否大于80,若满足输出“A”.
第三步,判断该同学的数学成绩是否小于60,若满足输出“C”.
第四步,判断该同学的数学成绩是否大于等于60,同时小于等于80,若满足输出“B”.结束.
程序框图如图所示.
7.对于三个数中找最大值,需要用到至少两次判断,首先必须将两数比较大小,用其中的最大(或小)的数作为下一个选择中与另一个数比较大小,再选择较大(或小)的数.故用选择结构.算法流程图如图所示.
8.要首先判断a是否等于0,然后在a=0和a≠0两种情况下,分别选择算法.其次分别就b是否等于0,及判别式的情况,分别选择不同的算法,也就是要考虑到解方程的各种情况.
具体算法如下:
(1)若a=0,则判断b是否等于0.
①若b≠0,则方程的解为x=-
.
②若b=0,则判断c是否等于0.
a.若c≠0,则方程无解.
b.若c=0,则任何一个实数都是方程的解.
(2)若a≠0,则判断判别式Δ=b2-4ac的符号.
①若Δ<0,则方程无解.
②若Δ≥0,则判断Δ=0与Δ>0两种情况.
a.若Δ=0,则方程只有一解x=-
.
b.若Δ≠0,则方程有两解,x1=
,x2=
.
其算法流程图如图所示.
优化考题新演练答案:
1.B.菱形框表示判断.
2.C.
>2004,n2+n-4008>0.∵n>0,∴n>
≈62.8.
∴n的最小正整数值为63.
3.
(1)流程图的开始或结束.
(2)输入、输出框.(3)处理框.(4)判断框.(5)根据给定条件判断.(6)流程线.
4.
(1)Δ<0
(2)x1
,x2=
(3)输出x1,x2.
5.流程图如图所示.
6.其算法步骤为:
(1)把x=2代入函数式f(x)=x2-2x,
(2)计算22-2×2=0,
(3)输出结果,即当x=2时,函数f(x)=x2-2x的函数值为0.
本题是应用了顺序结构.
(1)若x<0,则|x|等于-x;
(2)若x≥0