第十一章算法初步与框图、知识网络条件结构第一节算法与程序框图※知识回顾1 •算法的概念：算法通常是指按一定规则解决某一类问题的明确和有限的步骤.2. 程序框图又称流程图，是一种用程序框、流程线及文字说明来表示算法的图形3. 程序框图的三种基本逻辑结构是顺序结构、条件结构、循环结构._4. 算法的描述方式有：自然语言、程序框图、程序语言.5. 算法的基本特征：①明确性：算法的每一步执行什么是明确的；②顺序性：算法的“前一步”是“后一步”的前提，“后一步”是“前一步”的继续；③有限性：算法必须在有限步内完成任务，不能无限制的持续进行；④通用性：算法应能解决某一类问题•※典例精析1.如图所示是一个算法的程序框图，则该程序框图示的功能后,接着判断a,b的大小，若b小，则把b赋给a,否则执行下一步，即判断a与c 的大小，若c小，则把c赋给a,否则执行下一步，这样输出的a是a,b,c三个数中的最小值.所以该程序框图所表示的功能是求a,b,c三个数中的最小值.评注：求a,b,c三个数中的最小值的算法设计也可以用下面程序框图来表示例2.下列程序框图表示的算法功能是（）（1）计算小于100的奇数的连乘积（2）计算从1开始的连续奇数的连乘积（3）计算从1开始的连续奇数的连乘积，当乘积大于100时，计算奇数的个数解析：为了正确地理解程序框图表示的算法，可以将执行过程分解，分析每一步执行的结果•可以看出程序框图中含有当型的循环结构，故分析每一次循环的情况，列表如下：第一次：' '；第二次：、.—一.第三次：，，此时' 不成立,输出结果是7,程序框图表示的算法功能是求使b女殳…共nr 100成立时77的最小值. 选D.评注:通过列表，我们能清楚了解程序的每一步中的各个变量是怎样变化的，这正是程序运行的本质所在.本题若要求编写求使「丨成立时匸的最小值的程序框图或程序时，很容易弄错输出的结果，应注意•例3.在音乐唱片超市里，每张唱片售价为25元，顾客如果购买5张以上（含5 张）唱片，则按九折收费，如果购买10张以上（含10张）唱片，则按八折收费，请设计算法步骤并画出程序框图，要求输入张数x，输出实际收费y（元）.厂°分析:先写出卜与左之间的函数关系式，有25A5）22.5A（5<10）皿 g⑼，再利用条件结构画程序框图.首先要理解各程序框的含义，输入a,b,c三个数之解：算法步骤如下:第一步，输入购买的张数‘，第二步，判断是否小于5,若是，计算’''；否则，判断*是否小于10，若是，计算小小;否则，计算第三步，输出1.程序框图如下：评注:凡必须先根据条件做出判断，然后再决定进行哪一个步骤的问题，在画程序框图时，必须引入判断框，采用条件结构设计算法•如果变量分三级（或以上）时,就需要用到条件结构的嵌套，不能忽视结果中“是”、“否”的书写，否则不知道执行哪一条路径• 一般地,分：段的分段函数，需要引入.个判断框•条件结构有以下两种基本类型•否f*1 + T 卄一7例4.画出求分析:这是一个有规律的数列求和问题，每次都进行了相同的运算，故应用循环结构进行算法设计• 解:程序框图如下：当(2)直到型循环评注：(1) 解题关键是选择好计数变量■和累加变量，的初始值，并写出用■表示的数列的通项公式是；(2)循环结构主要用在一些有规律的重复计算的算法中，如累加求和，累乘求积等问题.在循环结构中，要注意根据条件，设计合理的计数变量、累加(积)变量以及它们的初始值等，特别要注意循环结构中条件的表述要恰当、精确，以免出现多一次或少一次循环•(3)循环结构分为两类：一类是当型循环结构，如下左图所示；另一类是直到型环£=12 »] + 1循环结构，如下右图所示程序框图.解：程序框图如下：例5.某工厂2005年的生产总值为200万元，技术改进后预计以后后每年的年生产 总值都比上一年增长5%.设计一个程序框图，输出预期年生产总值超过 300万元的最早年份及2005年到此年份之前(不包此年份)的年生产总值的和.分析:本例可用循环结构来实现• (1)确定“循环体”：设a 为某年的年生产总值,n 为年份,S 为年产值的总和，则循环体为5 » 5 +a =爲+ 005比⑵初始化变量:n 的初始值为2005,a 的初始值为200,S 的初始值为0.(3)设定循环控制条件:宀解：程序框图如下：I -4 -------卜 - ■!-・・・ +变式训练画出求 F筍出3结東S=SX h/ 編号麻/评注：本问题的关健是设计好循环体，注意F- 与「之间的对应关系.本题若将"x :放在 - •之后，则输出时须重新赋值厂-"，否则卜|的值为超过300 万的年份的下一年•本题也可用当型循环结构来表示•变式训练：设计一个程序框图，求使mm：…—小:的最小的值，并输出此时V的值.解：程序框图如下：※基础自测一、选择题1 .下列说法正确的是( )A. 算法就是某个问题的解题过程；B. 算法执行后可以产生不同的结果；C. 解决某一个具体问题算法不同结果不同；D. 算法执行步骤的次数不可以很大，否则无法实施.1. 解析：选项A，算法不能等同于解法；选项B,例如：判断一个正整数是否为质数，结果为“是质数”和“不是质数”两种；选项C,解决某一个具体问题算法不同结果应该相同，否则算法构造的有问题；选项D,算法可以为很多次，但不可以无限次.2、如图所示的程序框图中，则第3个输出的数是()输出3. 如图给出的是求，的值的一个程序框图，其中判断框内应填入的条件是()A.i>10?B.i<10?C.i>20?D.i<20?输出3. 解析：通过列表，我们能清楚了解程序的每一步中的各个变量f = I 冒=—^-4是怎样变化的，第一次：，I .… I 1 札第二次： 4 ,…依此可知循环的条件是i>10 ?.选A4•阅读右边的程序框图，若输入的"是100，则输出的变量 "和•的值依次是()A. 2550, 2500B. 2550, 2550C. 2500, 2500D. 2500, 25504. 解析：依据框图可得十恥十躺—2^25^ ,7= 99 + 97^95^...+ 1 2500 选A5. 2006年1月份开始实施的《个人所得税法》规定：全月总收入不超过元的免征个人工资、薪金所得税，超过元部分需征税.设全月总收入金额为'元，前三级税率如下左表所示：级数全月应纳税金额x_16f)0税率1不超过加0元部分5%2超过至那币元部分10%3超过200D至5EO元部分15%是当工资薪金所得不超过 1 ;元，计算个人所得税的一个算法框图如图.则输出①、输出②分别为().A 归;门B ・L 丨恥C .0.05 OJx0.0,JT-网；0.1 —1 虻D.5•解析：设全月总收入金额为•，元，所得税额为元，则’与，之间的函数关系为0 A< 1600}A-1600)巧％(1600 < A<2100)25+(x-2100>10% (2100 c x£ 3600)选D二、填空题6. ______________________________________________ 执行右边的程序框图，若p=0.8,则输出的n= _________________________________- ，此时n=2;第二次循环后,\$=丄+丄+丄、0,82 4 82 + 4 t 6 + ■■■ + 1 £)0 2550三、解答题9•请阅读下面程序框图，说明此程序的功能6.解析:第一次循环后,，此时二输出，故填4.$ 二J此时3;第三次循环后，8.如果执行右面的程序框图，那么输出的解：程序功能是求s 的值• * 1十2 + 2•十一+ 2',并输出sF(A + iy (x<o )y= 4(x= Q)10•已知函数 灯"，0),请画出程序框图，要求输入自变量主的值,输出函数值'. 10.解：/严/I 蛊111 •画出一个计算 ’ 1的程序框图.第二节算法的基本语句及算法案例※知识回顾1 •任何一种程序设计语言都包含五种基本的算法语句，它们是输入语句,输出语句, 赋值语句，条件语句，循环语句2. 输入语句的一般格式是"了如内容诬旺；输出语句的一般格式是-；赋值语句的一般格式是鸞I烹跃黑;FF篝件THEN语句体1IF条件THEN B-SE语旬体贈旬体2条件语句的一般格式是'；：或' ' ；DO WHILE条件循坏林循环体循环语句的一般格式是和，.输入语句、输出语句、赋值语句基本对应于程序框图中的顺序结构；条件语句、循环语句分别用来表达程序框图中的条件结构和循环结构•3. 常用符号运算符号：加_+_，减-_，乘*，除/_，乘方aS，整数取商，求余数MOD. 逻辑符号：且AND或OR大于〉，等于二，小于v,大于等于>=,小于等于<=不等于<>.常用函数：绝对值ABS平方根SQR取整INT.4. 算法案例（1）辗转相除法和更相减损术辗转相除法和更相减损术都是求两个正整数的最大公约数的方法•（1）辗转相除法就是对于给定的两个正整数，用大数除以小数，若余数不为^>0, 则将小数和余数构成新的一对数，继续上面的除法，反复执行此步骤，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数•（2）更相减损术就是对于给定的两个正整数，若它们都是偶数，则将它们反复除以2（假设进行了k次），直到它们至少有一个不是偶数后，将大数减小数，然后将差和较小的数构成一对新数，继续上面的减法，反复执行此步骤，直到差和较小的数相等，此时相等的数再乘以原来约简的即为所求两数的最大公约数•（2）秦九韶算法秦九韶算法是求多项式值的优秀算法•设.产出行*「亠"4 %*爲改写为如下形式：住）・（"严坷甘+ %设“也=片声十!这样求n次多项式的值就转化为求n个一次多项式的值.当多项式中有些项不存在时，可将这几项看做-，补齐后再利用秦九韶算法进行计算•对于一个n次多项式，只需做n次乘法和n次加法运算即可.（3）进位制K进制数的基数为k，k进制数是由：之间的数字构成的.将十进制的数转化为k进制数的方法是除k取余法.1CJ■谴嬴』」.u —弋兀£ fr.ti £■ ・i.斗< Jt t 十Mt Al "E 卸右孝曲※典例精析例1 •写出用循环语句描述求「I的值的算法程序.解：算法程序如下：（1）当型循环（2）直到型循环评注：在编写算法的程序时，可先画出程序框图，抓住程序框图表示算法这个核心注意分别用当型循环和直到型循环语句编写的程序中，循环条件的区别与联系•例2、某市对排污水进行综合治理，征收污水处理费，系统对各厂一个月内排出的污水量…吨收取的污水处理费元，运行程序如下所示：请写出y与m的函数关系，并求排放污水150吨的污水处理费用.解：这个程序反映的是一个分段函数y=- 504 1/JJ- 50) (50IDtl)(nr>LOO)因为：「「所以’=1'，故该厂应缴纳污水处理费评注：解决分段函数要用条件语句来处理.本题可画出程序框图帮助理解. 例3. 求三个评注：辗转相除法与更相减损术均是求两个正整数的最大公约数的方法，要理解和掌握它们的操作步骤.变式:试写出求正整数」的最小公倍数的算法程序.解：或例4.用秦九韶算法求多项式壬〉；匸/心芒“朮“ E E在._时的值.分析：先改写多项式，再由内向外计算.评注：用秦九韶算法求多项式值，关健是正确将多项式改写，然后由内向外计算求 得. 本题也可简写为下式： L 2 3 4 5 6 21 8 22 52 I 14 4 1 ] 26 57 )20例5.完成下列进制的转化 ⑴"202 口产__问⑵】0/严 __________ ⑹评注：将・进制的数转化为■进制的数的方法是先将■进制的数转化为十进制的 数，再将这个数转化为’进制的数.变式训练：下面是把二进制数I “ 化为十进制数的一个程序框图，判断框内应 填入的条件是 /> 5? 4 ? / > 4 ? 5?解：lllll ㈢二心2 + I2U 1 1小I,故判断框内应填入的条件” 4.选C . 探基础自测 、选择题1 •下列给出的赋值语句中正确的是（）A - ■B 立一 ■: JC - - D1.解析：赋值语句的功能.选B 2当-:时，下面的程序输出的结果是（）A ■-B _CD _2解析：□ ■2+l -LU2 + l-k3M2 + l=?,7i«2^1 = ]5.选C3.运行下列程序：当输入56, 42时，输出的结果是A . 56B . 42C .84D.144下边程序运行后输出的结果为（ ）当程序输入冬值为123时，问运行的结果是 _____________7.已知n 次多项式’,如果在一种算法中，计算' （k = 2, 3, 4,…，n ）的值需要k — 1次乘法，计算•的值共需要9次运的最大公约数是BA :6•阅读下列程序:算（6次乘法，3次加法），那么计算. 的值共需要_________________________ 次运算.下面给出一种减少运算次数的算法：盘心；W小小Km s（k = 0, 1 , 2，…，n —1）•利用该算法，计算的值共需要6次运算，计算• 的值共需要__________________ 次运算.7 •解析：秦九韶算法适用一般的多项式码（小”匚宀/ S'—的求值问题.直接法乘法运算的次数最多可到达(n + IV J，加法最多n次.秦九韶算法通过2转化把乘法运算的次数减少到最多n次, 加法最多n次.答案：65; 20.8•下面程序运行后输出的结果为8•下面程序运行后输出的结果为。