1、 第第 一一 章章 算法初步算法初步 知能整合提升知能整合提升 一、算法的设计一、算法的设计 1.算法设计与一般意义上的解决问题不同算法设计与一般意义上的解决问题不同， 它是对一类问题的一般解法的抽它是对一类问题的一般解法的抽 象与概括象与概括， 它往往是把问题的解法划分为若干个可执行的步骤它往往是把问题的解法划分为若干个可执行的步骤， 有时是重复多次有时是重复多次， 但最终都必须在有限个步骤之内完成但最终都必须在有限个步骤之内完成. 2.设计算法时应注意：设计算法时应注意： (1)与解决该问题的一般方法相联系与解决该问题的一般方法相联系，从中从中提炼与概括算法步骤提炼与概括算法步骤. (2)
2、将解决的问题过程划分为将解决的问题过程划分为若干步骤若干步骤. (3)引入有关的参数或变量对算法步骤加以表达引入有关的参数或变量对算法步骤加以表达. (4)用简练的语言将各步骤表达出来用简练的语言将各步骤表达出来. 二、程序框图二、程序框图 1.程序框图是用规定的图形和指向线来准确、 直观、 形象地表示算法的图形程序框图是用规定的图形和指向线来准确、 直观、 形象地表示算法的图形. 2.算法的三种基本逻辑结构算法的三种基本逻辑结构 (1)顺序结构顺序结构 (2)条件结构条件结构 (3)循环结构循环结构 3.画程序框图的规则画程序框图的规则 (1)使用标准的框图符号使用标准的框图符号. (2)框
3、框图一般按从上到下、从左到右的方向画图一般按从上到下、从左到右的方向画. (3)除判断框外除判断框外，大多数框图符号只有一个进入点和一个退出点大多数框图符号只有一个进入点和一个退出点，判断框是判断框是 具有超过一个退出点的唯一符具有超过一个退出点的唯一符号号. (4)一种判断框是一种判断框是“是是”与与“不是不是”两分支的判断两分支的判断，而且有且仅有两个结果；而且有且仅有两个结果； 另一种是多分支判断另一种是多分支判断，有几种不同的结果有几种不同的结果. (5)在图形符号内描述的语言要非常简练清楚在图形符号内描述的语言要非常简练清楚. 三、基本算法语句三、基本算法语句 1.赋值语句的一般格式
4、：变量表达式赋值语句的一般格式：变量表达式 2.输入语句实现算法的信息输入功能输入语句实现算法的信息输入功能，一般格式为一般格式为 INPUT “提示内容提示内容”； 变量变量. 3.输出语句实现算法的信息输出功能输出语句实现算法的信息输出功能，一般格式为一般格式为 PRINT “提示内容提示内容”； 表达式表达式. 4.条件语句有两种条件语句有两种，一种是一种是 IFTHENELSE，其格式是：其格式是： IF 条件条件 THEN 语句语句1 ELSE 语句语句2 END IF 对应的框图为：对应的框图为： 另一种是另一种是 IFTHEN 语句语句，其格式是：其格式是： IF 条件条件 TH
5、EN 语句语句 END IF 对应的框图为：对应的框图为： 5.循环语句循环语句 (1)算法中的循环结构是用循环语句来实现的算法中的循环结构是用循环语句来实现的，对应于循环结构中的两种循对应于循环结构中的两种循 环结构环结构，一般程序设计语言也有当型一般程序设计语言也有当型(WHILE 型型)和直到型和直到型(UNTIL 型型)两种语言两种语言 结构结构. (2)WHILE 语句的一般格式为：语句的一般格式为： WHILE 条件条件 循环体循环体 WEND 对应的程序框图为：对应的程序框图为： 当计算机遇到当计算机遇到 WHILE 语句语句时时，先判断条件的真假先判断条件的真假，如果条件符合如
6、果条件符合，执行执行 WHILE 和和 WEND 之间循环体；若之间循环体；若条件不符合，计算机就不再执行循环体，而条件不符合，计算机就不再执行循环体，而 会直接跳到会直接跳到 WEND 语句后语句后，接着执行接着执行 WEND 之后的语句之后的语句. (3)UNTIL 语句的一般格式为：语句的一般格式为： DO 循环体循环体 LOOP UNTIL 条件条件 对应程序框图为：对应程序框图为： 6.使用算法语句时应注意的几个问题：使用算法语句时应注意的几个问题： (1)一个输入语句可以对多个变量赋值一个输入语句可以对多个变量赋值，中间用中间用“， ”隔开隔开，输出语句也类似输出语句也类似. (2
7、)赋值号左边只能是变量赋值号左边只能是变量，而不能是表达式而不能是表达式.两边不能两边不能对换，若对称，需引对换，若对称，需引 入第三个变量入第三个变量. (3)条件语条件语句一般用在需要对条件进行判断的算法设计中句一般用在需要对条件进行判断的算法设计中，如判断一个数的如判断一个数的 正负正负，确定两数大小等确定两数大小等. (4)当型循环是当条件满足时执行循环体当型循环是当条件满足时执行循环体，而直到型循环是当条件不满足时而直到型循环是当条件不满足时 执行循环体执行循环体. (5)在解决一些需要反复执行的任务时在解决一些需要反复执行的任务时，如累加求和、累乘求积通常都用循如累加求和、累乘求积
8、通常都用循 环语句来实现环语句来实现，要注意循环变量的控制条件要注意循环变量的控制条件. (6)在循环语句中嵌套条件语句时在循环语句中嵌套条件语句时， 有时会在条件语句中添加有时会在条件语句中添加“ELSE” 语句语句， 添加后添加后，如果没有语句需要执行如果没有语句需要执行，就会就会造成错误造成错误. 四、算法案例四、算法案例 1.求最大公约数求最大公约数 (1)更相减损术更相减损术 更相减损术更相减损术(也叫等值算法也叫等值算法)是我国古代数学家在求两个正整数的最大公约是我国古代数学家在求两个正整数的最大公约 数时数时的一个算法的一个算法，其操作过程是：对于给定的两个正整数其操作过程是：对
9、于给定的两个正整数，用较大的数减去较小用较大的数减去较小 的数的数，接着把得到的差与较小的数比较接着把得到的差与较小的数比较，用这两个数中较大的数减去较小的数用这两个数中较大的数减去较小的数， 继续上述操作继续上述操作(大数减去小数大数减去小数)，直到产生一对相等的数为止直到产生一对相等的数为止，那么这个数那么这个数(等数等数) 即是所求的最大公约数即是所求的最大公约数. (2)辗转相除法辗转相除法 辗转相除法辗转相除法(即欧几里得算法即欧几里得算法)就是给定两个正整数就是给定两个正整数，用较大的数除以较小的，用较大的数除以较小的 数，若余数不为零，则将较小的数和余数继续上面的除法，直到余数为
10、零，此时数，若余数不为零，则将较小的数和余数继续上面的除法，直到余数为零，此时 的除数就是所求的最大公约数的除数就是所求的最大公约数. (3)二者的区别与联系二者的区别与联系 辗转相除法进行的是除法运算辗转相除法进行的是除法运算， 即辗转相除即辗转相除， 而更相减损术进行的是减法运而更相减损术进行的是减法运 算算，即辗转相减即辗转相减，但实质都是一个递归过程但实质都是一个递归过程. 2.秦九韶算法是多项式求值的优秀算法秦九韶算法是多项式求值的优秀算法，秦九韶算法的特点是：秦九韶算法的特点是： (1)化高次多项式求值为一次多项式求值化高次多项式求值为一次多项式求值. (2)减少了运算次数减少了运
11、算次数，提高了运算效率提高了运算效率. (3)步骤重步骤重复执行，容易用计算机实现复执行，容易用计算机实现.利用秦九韶算法计算多项式的值的关利用秦九韶算法计算多项式的值的关 键是能正确地将所给多项式改写键是能正确地将所给多项式改写， 然后由内向外逐次计算然后由内向外逐次计算， 由于后项计算用到前由于后项计算用到前 项的结果项的结果，故应认真、细心故应认真、细心，确保中间结果的准确性确保中间结果的准确性.若在多项式中有几项不存若在多项式中有几项不存 在时在时，可将这些项的系数看成可将这些项的系数看成 0，即把这些项看作即把这些项看作 0xn. 3.(1)将将 k 进制数转化为十进制数的方法： 先
12、把进制数转化为十进制数的方法： 先把 k 进制数写成用各位进制数写成用各位上的数字上的数字 与与 k 的幂的乘积的形式的幂的乘积的形式，再按照十进制的运算规则计算出结果再按照十进制的运算规则计算出结果. (2)将十进制数化为将十进制数化为 k 进制数的方法是除以进制数的方法是除以 k 取余法取余法，即用即用 k 连续去除十进连续去除十进 制数制数(或所得或所得的商的商)，直到商是零为止，然后把各步得到的余数倒着写出来就是相，直到商是零为止，然后把各步得到的余数倒着写出来就是相 应的应的 k 进制数进制数. (3)k 进制数之间的转化进制数之间的转化，首先转化成十进制数首先转化成十进制数，再转化
13、为其他进制数再转化为其他进制数. 热点考点例析热点考点例析 算法设计算法设计 算法概念的特征分析：算法概念的特征分析： (1)算法是一种循序渐进解决问题的过程算法是一种循序渐进解决问题的过程，尤指一种为在有限步骤内解决问尤指一种为在有限步骤内解决问 题而建立的可重复应用的计算过程题而建立的可重复应用的计算过程. (2)算法的特征算法的特征 有穷性：一个算法必须保证它的执有穷性：一个算法必须保证它的执行步骤是行步骤是有限的，即它是能终止的有限的，即它是能终止的. 确定性：算法中的每个步骤必须有确切的含义确定性：算法中的每个步骤必须有确切的含义. 可执行性： 算法中的每个步骤都要实践能做的可执行性
14、： 算法中的每个步骤都要实践能做的， 而且能在有限的时间内完而且能在有限的时间内完 成成. (3)算法是连接人和计算机的纽带算法是连接人和计算机的纽带，是计算机科学的基础是计算机科学的基础，利用计算机解决利用计算机解决 问题需要算法问题需要算法. 特别提醒特别提醒 在设计算法时注意：在设计算法时注意：(1)与解决所求问题的一般方法相联系与解决所求问题的一般方法相联系，并并 从中提炼与概括步骤；从中提炼与概括步骤；(2)将解决问题的过程划分为若干步；将解决问题的过程划分为若干步；(3)引入有关的参数引入有关的参数 或变量对算法步骤加以表述或变量对算法步骤加以表述. 用自然用自然语言描述将全班语言
15、描述将全班 40名学生中考试成绩不及格者的分数打印出来名学生中考试成绩不及格者的分数打印出来. 解析：解析： 第一步第一步，令令 n1. 第二第二步步，若若 n 大于大于 40，则执行第七步；则执行第七步； 否则否则，执行下一步执行下一步. 第三步第三步，输入一成绩输入一成绩 G. 第四步第四步，将将 G 和和 60 作比较作比较.若若 G 小于小于 60，则打印出分数则打印出分数 G； 否则否则，执行下一步执行下一步. 第五步第五步，使使 n 的值加的值加 1. 第六步第六步，返回到第二步返回到第二步. 第七步第七步，算法结束算法结束. 1.函数函数 y x1， （x0） 0， （x0） x
16、1， （x0，则则 yx1，然后执行第四步；否则然后执行第四步；否则，执行第三步执行第三步. 第第三步三步，若若 x0，则则 y0；否则；否则，yx1. 第四步第四步，输出输出 y. 程序框图及其画法程序框图及其画法 1.程序框图是用规定的图形和指向线来准确、 直观、 形象地表示算法的图形程序框图是用规定的图形和指向线来准确、 直观、 形象地表示算法的图形. 2.画程序框图的步骤：画程序框图的步骤： (1)对问对问题设计出合理有效的算法；题设计出合理有效的算法； (2)分析算法的逻辑结构；分析算法的逻辑结构； (3)由逻辑结构画出相应的程序框图由逻辑结构画出相应的程序框图. 某商场进行优惠促销
17、：若购物金额某商场进行优惠促销：若购物金额 x 在在 500 元以上元以上，打打 8 折；若购物折；若购物 金额金额 x 在在 300 元以上元以上，打打 9 折；否则折；否则，不打折不打折.设计算法的程序框图设计算法的程序框图，要求输入要求输入 购物金额购物金额 x，即能输出实际交款额即能输出实际交款额. 解析：解析： 算法步骤如下：算法步骤如下： 第一第一步：输入购物金额步：输入购物金额 x. 第二步：判断第二步：判断 x300 是否成立是否成立，若成立若成立，则则 yx；否则；否则，执行第三步执行第三步. 第三步：判断第三步：判断 x500 是否成立是否成立，若成立若成立，则则 y0.9
18、x；否则；否则，y0.8x. 第四步：输出第四步：输出 y，结束算法结束算法. 程序框图如下：程序框图如下： 2.铁路部门托运行李的收费方法如下：铁路部门托运行李的收费方法如下：y 是收费额是收费额(单位：元单位：元)，x 是行李重量是行李重量 (单位：单位：kg)，当当 020 kg 时时，20 kg 的部分按的部分按 0.35 元元/kg 收费收费，超出超出 20 kg 的部分的部分，则按则按 0.65 元元/kg 收费收费. (1)请根据上述收费方法求出请根据上述收费方法求出 y 关于关于 x 的函数式；的函数式； (2)画出程序框图画出程序框图. 解析：解析： (1)y 关于关于 x
19、的函数式为：的函数式为： y 0.35x， ， （020） (2)程序框图如图所示程序框图如图所示. 算法语句的设计与应用算法语句的设计与应用 算法语句设计的几点说明：算法语句设计的几点说明： (1)条件语句主要用于一些需要进行条件判断的算法；循环语条件语句主要用于一些需要进行条件判断的算法；循环语句主要用于有句主要用于有 规律的计算，使用时应注意设计一些合理的计数变量规律的计算，使用时应注意设计一些合理的计数变量. (2)循环结构的两种格式中循环结构的两种格式中，判断框内的条件表述在解决同一问题时是不同判断框内的条件表述在解决同一问题时是不同 的的，它们恰好相反它们恰好相反，两种循环只是实现
20、循环运算的不同方法两种循环只是实现循环运算的不同方法，它们之间可以互相它们之间可以互相 转化转化. (3)理解五种不同功能的基本算法语句理解五种不同功能的基本算法语句，并懂得兼顾基本语句的格式要求并懂得兼顾基本语句的格式要求， 从而完成程序设计任务从而完成程序设计任务. 特别提醒特别提醒 程序设计中应特别注意的是：条件语句的条件表达和循环语句程序设计中应特别注意的是：条件语句的条件表达和循环语句 中的循环变量的取值范围中的循环变量的取值范围. 请根据给出的算法程序画出程序框图请根据给出的算法程序画出程序框图. a1 b1 i2 WHILE i1 THEN yx2 ELSE y2*x END I
21、F PRINT y END 解析：解析： 由程序可知由程序可知，它解决的是求分段函数它解决的是求分段函数 y x 2，x1 2x，x1 的函数值的函数值，显显 然然，当当 x 3时时，y 32；当；当 x0 时时，y0. 答案：答案： 32 0 7.任意给出一个数据任意给出一个数据(正数正数)，写出以它为半径的圆的周长和面积的一个算法写出以它为半径的圆的周长和面积的一个算法 程序程序. 解析：解析： 记记 PI3.141 592 6，算法程序如下：算法程序如下： INPUT “请输入圆的半径请输入圆的半径 r：”；r C2*PI*r SPI*r2 PRINT “圆的半径圆的半径 r”；r PRINT “圆的周长圆的周长 C”；C PRINT “圆的面积圆的面积 S”；S END 8.设计算法求设计算法求 1 12 1 34 1 56 1 2 0132 014的值 的值. 解析：解析： 这是一个累加求和问题这是一个累加求和问题，共共 1 007 项相加项相加，可设计一个计数变量可设计一个计数变量， 一个累加变量一个累加变量，用循环结构实现这一算法用循环结构实现这一算法.程序框图如图所示：程序框图如图所示： 程序如下：程序如下： S0 i1 DO SS1/(i*(i1) ii2 LOOP UNTIL i2 013 PRINT S END 谢谢观看！谢谢观看！
