算法初步小结与复习(绝对精品).ppt

1 1算法与程序框图 1 1 1算法的概念 先去括号 再乘除 后加减 1 什么是算法呢 要把大象装冰箱 分几步 答 分三步 第一步 打开冰箱门 第二步 把大象装冰箱 第三步 关上冰箱门 问 简单地说 算法就是解决问题的程序或步骤 什么是算法呢 第一步 第二步 第三步 消元 解一元一次方程 2 得 解 得 代入求解 将代入 得 写一写 写出解第二个方程组的算法 第一步 第二步 第三步 解 得 将 代入 得 变一变 在数学上 通常是按照一定规则解决某一类问题的明确有限的步骤 算法的定义 例1 1 设计一个算法 判断7是否为质数 2 设计一个算法 判断35是否为质数 算法 探究 你能写出 判断整数n n 2 是否为质数 的算法吗 第一步 给定大于2的整数n 第二步 令i 2 算法的基本特点 1 有穷性 一个算法应包括有限的操作步骤 能在执行有穷的操作步骤之后结束 2 确定性 算法的计算规则及相应的计算步骤必须是唯一确定的 既不能含糊其词 也不能有二义性 3 逻辑性 算法中从开始的 第一步 到 最后一步 之间做到环环相扣 分工明确 前一步 是 后一步 的前提 后一步 是 前一步 的继续 算法1 第二步 计算101 50 第三步 写出运算结果 算法2 第一步 取n 100 第二步 计算 第三步 写出运算结果 写出求1 2 3 100的一个算法 1 100 2 99 50 51 第一步 将原式变形为 你会了吗 2 任意给定一个正实数 设计一个算法求以这个数为半径的圆的面积 第一步 输入任意一个正实数r 0 第二步 计算圆的面积 S r2 第三步 输出圆的面积S 1 1 2程序框图 程序框图 程序框图又称流程图 是一种用程序框 流程线及文字说明来表示算法的图形 在程序框图中 一个或几个程序框的组合表示算法中的一个步骤 带有方向箭头的流程线将程序框连接起来 表示算法步骤的执行顺序 例用程序框图表示 判断整数n n 2 是否为质数 的算法 设n是一个大于2的整数 一般用i i 1表示 i i 1 说明 i表示从2 n 1 的所有正整数 用以判断例1步骤2是否终止 i是一个计数变量 有了这个变量 算法才能依次执行 逐步考察从2 n 1 的所有正整数中是否有n的因数存在 画程序框图的规则 1 使用标准的图形符号 2 框图一般按从上到下 从左到右的方向画 3 除判断框外 大多数流程图符号只有一个进入点和一个退出点 判断框具有超过一个退出点的唯一符号 4 判断框分两大类 一类判断框 是 与 否 两分支的判断 而且又且仅有两个结果 另一类是多分支判断 有几种不同的结果 5 在图形符号内描述的语言要非常简练清楚 算法的基本逻辑结构 顺序结构 用程序框图来表示算法 有三种不同的基本逻辑结构 条件结构 循环结构 三种基本结构 表示一个良好算法的基本单元 顺序结构 条件结构 选择结构 循环结构 While 当型 循环 Until 直到型 循环 顺序结构 顺序结构是由若干个依次执行的步骤组成的 这是任何一个算法都离不开的基本结构 例1已知一个三角形的三边边长分别为a b c 利用海伦 秦九韶公式设计一个算法 求出它的面积 画出它的程序框图 程序框图 习题1设计一算法 输入圆的半径 输出圆的面积 并画出流程图 算法分析 第一步 输入圆的半径 第二步 利用公式 圆的面积 圆周率 半径的平方 计算圆的面积 第三步 输出圆的面积 思考 整个程序框图有什么特点 条件结构 选择结构 算法的流程根据条件是否成立有不同的流向 条件结构就是处理这种过程的结构 例2任意给定3个正实数 设计一个算法 判断分别以这3个数为三边边长的三角形是否存在 画出这个算法的程序框图 解 算法如下 S1输入xS2若x为奇数 则输出A 3x 2 否则输出A 5xS3算法结束 习题2设x为一个正整数 规定如下运算 若x为奇数 则求3x 2 若x为偶数 则为5x 写出算法 并画出程序框图 循环结构 在一些算法中 从否处开始 按照一定条件 反复执行某一处理步骤的情况 这就是循环结构 反复执行的处理步骤称为循环体 在循环结构中 通常都有一个起到循环计数作用的变量 这个变量的取值一般都含在执行或中止循环体的条件中 例3设计一个计算1 2 3 100的值的算法 并画出程序框图 算法分析 需要一个累加变量和一个计数变量 将累加变量的初始值设为0 计数变量的值可以从1到100 1 2 基本算法语句 第一章算法初步 探究新知 我们知道 顺序结构是任何一个算法都离不开的基本结构 输入 输出语句和赋值语句基本上对应于算法中的顺序结构 计算机从上而下按照语句排列的顺序执行这些语句 输入语句和输出语句分别用来实现算法的输入信息 输出结果的功能 如右图 输入语句和输出语句分别用来实现算法的输入信息 输出结果的功能 例1用描点法作函数y x3 3x2 24x 30的图象时 需要求出自变量和函数的一组对应值 编写程序 分别计算当x 5 4 3 2 1 0 1 2 3 4 5时的函数值 INPUT x xy x 3 3 x 2 24 x 30PRINTxPRINTyEND 程序 输入语句 赋值语句 打印语句 打印语句 表示结束 输出语句 输出语句 一 输入语句 INPUT 提示内容 变量 输入语句的一般格式 说明 1 输入语句的作用是实现算法的输入信息功能 2 提示内容 提示用户输入什么样的信息 变量是指程序在运行时其值是可以变化的量 3 输入语句要求输入的值只能是具体的常数 不能是函数 变量或表达式 4 提示内容与变量之间用分号 隔开 若输入多个变量 变量与变量之间用逗号 隔开 例如 输入一个学生数学 语文 英语三门课的成绩 可以写成 INPUT 数学 语文 英语 a b c 注意 INPUT语句不但可以给单个变量赋值 还可以给多个变量赋值 其格式为 INPUT 提示内容1 提示内容2 提示内容3 变量1 变量2 变量3 练一练 请你用输入语句表达课本P5和P9页程序框图中输入框中的内容 P7页 INPUT n n P9页 INPUTa b c 二 输出语句 PRINT 提示内容 表达式 说明 1 提示内容 提示用户输出什么样的信息 表达式是指程序要输出的数据 输出常量 变量的值和字符串等系统信息 输出数值计算的结果 2 输出语句的用途 输出语句的一般格式 3 同输入语句一样 表达式前也可以有 提示内容 思考 在课本P7页图1 1 2程序框图中的输出框的内容怎样用输出语句来表达 参考答案 输出框 PRINT nisaprimenumber PRINT nisnotaprimenumber PRINT S S 三 赋值语句 1 赋值语句的一般格式 变量 表达式 2 赋值语句的作用是 先计算出赋值号右边表达式的值 然后把这个值赋给左边的变量 使该变量的值等于表达式的值 3 赋值语句中的 称作赋值号 与数学中的等号的意义是不同的 赋值号的左右两边不能对换 4 赋值语句左边只能是变量名字而不是表达式 如 2 x是错误的 右边表达式可以是一个数据 常量或算式 不能利用赋值语句进行代数式的演算 如化简 因式分解 解方程等 5 对于一个变量可以多次赋值 例题解析 例2 编写程序 计算一个学生数学 语文 英语三门课的平均成绩 分析 先写出算法 画出程序框图 再进行编程 结束 程序框图 INPUT Maths Chinese English a b cy a b c 3PRINT y yEND 程序 例3 给一个变量重复赋值 程序 A 10A A 15PRINTAEND A的输出值是多少 分析 此程序给变量A赋了两次值 A的初值为10 第二次赋值后 初值被 覆盖 A的值变为25 因此输出值是25 变式引申 在此程序的基础上 设计一个程序 要求最后A的输出值是30 A 10A A 15PRINTAA A 5PRINTAEND 程序 例3 给一个变量重复赋值 程序 A 10A A 15PRINTAEND 例4 交换两个变量A和B的值 并输出交换前后的值 分析 引入一个中间变量X 将A的值赋予X 又将B的值赋予A 再将X的值赋予B 从而达到交换A B的值 比如交换装满水的两个水桶里的水需要再找一个空桶 INPUTAINPUTBPRINTA BX AA BB XPRINTA BEND 程序 不能 练习1 编写一个程序 要求输入一个圆的半径 便能输出该圆的周长和面积 取3 14 分析 设圆的半径为R 则圆的周长C 2 R 面积S R2 可以利用顺序结构中的INPUT语句 PRINT语句和赋值语句设计程序 INPUT R RC 2 3 14 RS 3 14 R 2PRINT C CPRINT S SEND 算法中的条件结构是由条件语句来表达的 条件语句是处理条件分支逻辑结构的算法语句 条件语句的一般格式 只含一个 分支 的条件结构 写成条件语句为 当计算机执行这种形式的条件语句时 首先对IF后的条件进行判断 如果条件符合 就执行THEN后的语句体 否则执行ENDIF之后的语句 含两个 分支 的条件结构 写成条件语句为 当计算机执行上述语句时 首先对IF后的条件进行判断 如果条件符合 就执行THEN后的语句体1 否则执行ELSE后的语句体2 条件语句的作用在程序执行过程中 根据判断是否满足约定的条件而决定是否需要转换到何处去 需要计算机按条件进行分析 比较 判断 并按判断后的不同情况进行不同的处理 1 编写一个程序 求任意实数的绝对值 程序如下 程序框图 开始 y x y x 输出y 结束 x 0 是 否 例题解析 例题解析 例6 编写程序 输入一元二次方程ax2 bx c 0的系数 输出它的实数根 算法分析 一元二次方程的根有三种不同情况 设判别式 b2 4ac 1 当 0时 一元二次方程有两个不等的实数根 2 当 0时 一元二次方程有两个相等的实数根 3 当 0时 一元二次方程没有实数根 程序 INPUT a b c a b cd b b 4 a cIFd 0THENp b 2 a q SQR d 2 a IFd 0THENPRINT Onerealroot pELSEx1 p qx2 p qPRINT Tworealroots x1 x2ENDIFELSEPRINT Norealroot ENDIFEND 例7 编写程序 使得任意输入的3个整数按从大到小的顺序输出 算法分析 用a b c表示输入的3个整数 为了节约变量 把它们重新排列后 仍用a b c表示 并使a b c 具体操作步骤如下 第一步 输入3个整数a b c 第二步 将a与b比较 并把小者赋给b 大者赋给a 第三步 将a与c比较 并把小者赋给c 大者赋给a 此时a已是三者中最大的 第四步 将b与c比较 并把小者赋给c 大者赋给b 此时a b c已按从大到小的顺序排列好 第五步 按顺序输出a b c 程序 INPUT a b c a b cIFb aTHENt aa bb tENDIFIFc aTHENt aa cc tENDIF IFc bTHENt bb cc tENDIFPRINTa b cEND 算法中的循环结构是由循环语句来实现的 循环结构有两种 当型与直到型 当型循环结构 当条件满足时反复执行循环体 直到型循环结构 反复执行循环体直到条件满足 对应于程序框图中的两种循环结构 一般程序设计语言中也有当型 WHILE型 和直到型 UNTIL型 两种语句结构 即WHILE语句和UNTIL语句 1 WHILE语句的一般格式是 WHILE条件循环体WEND 其中循环体是由计算机反复执行的一组语句构成的 WHLIE后面的 条件 是用于控制计算机执行循环体或跳出循环体的 WHILE 当 时候 WEND 朝 方向行走 1 WHILE语句的一般格式是 WHILE条件循环体WEND 当计算机遇到WHILE语句时 先判断条件的真假 如果条件符合 就执行WHILE与WEND之间的循环体 然后再检查上述条件 如果条件仍符合 再次执行循环体 这个过程反复进行 直到某一次条件不符合为止 这时 计算机将不执行循环体 直接跳到WEND语句后 接着执行WEND之后的语句 2 UNTIL语句的一般格式是 DO循环体LOOPUNTIL条件 DO 做什么 LOOPUNTIL 绕环回线走 直到达到某种条件为止 思考 参照其直到型循环结构对应的程序框图 说说计算机是按怎样的顺序执行UNTIL语句的 2 UNTIL语句的一般格式是 DO循环体LOOPUNTIL条件 从UNTIL型循环结构分析 计算机执行该语句时 先执行一次循环体 然后进行条件的判断 如果条件不满足 继续返回执行循环体 然后再进行条件的判断 这个过程反复进行 直到某一次条件满足时 不再执行循环体 跳到LOOPUNTIL语句后执行其他语句 是先执行循环体后进行条件判断的循环语句 提问 通过对照 大家觉得WHILE型语句与UNTIL型语句之间有什么区别呢 区别 在WHILE语句中 是当条件满足时执行循环体 而在UNTIL语句中 是当条件不满足时执行循环体 例1 编写程序 计算自然数1 2 3 99 100的和 分析 这是一个累加问题 我们可以用WHILE型语句 也可以用UNTIL型语句 i 1S 0 WHLIEi 100 S S i i i 1 WEND PRINTS END i 1S 0 DO S S ii i 1 LOOPUNTIL i 100 PRINTS END 变式训练 1 编写程序求 n 1 2 3 4 5 n的值 如何修改 WHILE语句 i 1S 0 WHLIEi 100 S S i i i 1 WEND PRINTS END INPUT n n S 1 S S i i n S 1 n S S i 变式训练 2 编写程序求 1 3 5 7 101的值 如何修改 UNITL语句 i 1S 0 DO S S i i i 1 LOOPUNTILi 100 PRINTS END S 1 101 S S i i i 2 直到型 S 1 S S i i i 2 i 101 算法案例 1 3 辗转相除法更相减损术 1 1 1 1 求两个正整数的最大公约数 1 求25和35的最大公约数 2 求225和135的最大公约数 2 求8251和6105的最大公约数 所以 25和35的最大公约数为5 所以 225和135的最大公约数为5 3 3 45 课前复习 3 15 9 知识回顾 先用两个数公有的质因数连续去除 一直除到所得的商是互质数为止 然后把所有的除数连乘起来 3 3 5 辗转相除法 欧几里得算法 观察用辗转相除法求8251和6105的最大公约数的过程 第一步用两数中较大的数除以较小的数 求得商和余数8251 6105 1 2146 结论 8251和6105的公约数就是6105和2146的公约数 求8251和6105的最大公约数 只要求出6105和2146的公约数就可以了 第二步对6105和2146重复第一步的做法6105 2146 2 1813同理6105和2146的最大公约数也是2146和1813的最大公约数 思考 从上述的过程你体会到了什么 完整的过程 8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 例2用辗转相除法求225和135的最大公约数 225 135 1 90 135 90 1 45 90 45 2 显然37是148和37的最大公约数 也就是8251和6105的最大公约数 显然45是90和45的最大公约数 也就是225和135的最大公约数 思考1 从上面的两个例子可以看出计算的规律是什么 S1 用大数除以小数 S2 除数变成被除数 余数变成除数 S3 重复S1 直到余数为0 第一步 给定两个正数m n第二步 计算m除以n所得到余数r第三步 m n n r第四步 若r 0 则m n的最大公约数等于m 否则返回第二步 辗转相除法求最大公约数算法 辗转相除法是一个反复执行直到余数等于0停止的步骤 这实际上是一个循环结构 否 开始 输入两个正数m n m n r mMODn r 0 输出n 结束 m x m n n r 否 是 是 x n n m 更相减损术 算理 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 第一步 任意给定两个正整数 判断他们是否都是偶数 若是 则用2约简 若不是 则执行第二步 第二步 以较大的数减较小的数 接着把所得的差与较小的数比较 并以大数减小数 继续这个操作 直到所得的减数和差相等为止 则这个等数或这个等数与约简的数的乘积就是所求的最大公约数 例1 用更相减损术求98与63的最大公约数 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 即 98 63 35 63 35 28 35 28 7 28 7 21 21 7 14 14 7 7 所以 98与63的最大公约数是7 二者算理相似 有异曲同工之妙1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 差为0 辗转相除法与更相减损术的区别 秦九韶算法 1 3 2 问题1 设计求多项式f x 2x5 5x4 4x3 3x2 6x 7当x 5时的值的算法 并写出程序 点评 上述算法一共做了15次乘法运算 5次加法运算 优点是简单 易懂 缺点是不通用 不能解决任意多项多求值问题 而且计算效率不高 这析计算上述多项式的值 一共需要9次乘法运算 5次加法运算 问题2 有没有更高效的算法 分析 计算x的幂时 可以利用前面的计算结果 以减少计算量 即先计算x2 然后依次计算 的值 第二种做法与第一种做法相比 乘法的运算次数减少了 因而能提高运算效率 而且对于计算机来说 做一次乘法所需的运算时间比做一次加法要长得多 因此第二种做法能更快地得到结果 问题3 能否探索更好的算法 来解决任意多项式的求值问题 f x 2x5 5x4 4x3 3x2 6x 7 2x4 5x3 4x2 3x 6 x 7 2x3 5x2 4x 3 x 6 x 7 2x2 5x 4 x 3 x 6 x 7 2x 5 x 4 x 3 x 6 x 7 v0 2v1 v0 x 5 2 5 5 5v2 v1x 4 5 5 4 21v3 v2x 3 21 5 3 108v4 v3x 6 108 5 6 534v5 v4x 7 534 5 7 2677 这种求多项式值的方法就叫秦九韶算法 f x anxn an 1xn 1 an 2xn 2 a1x a0 我们可以改写成如下形式 求多项式的值时 首先计算最内层括号内一次多项式的值 即 v1 anx an 1 然后由内向外逐层计算一次多项式的值 即 一般地 对于一个n次多项式 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 这样 求n次多项式f x 的值就转化为求n个一次多项式的值 这种算法称为秦九韶算法 f x anx an 1 x an 2 x a1 x a0 秦九韶算法 点评 秦九韶算法是求一元多项式的值的一种方法 它的特点是 把求一个n次多项式的值转化为求n个一次多项式的值 通过这种转化 把运算的次数由至多n n 1 2次乘法运算和n次加法运算 减少为n次乘法运算和n次加法运算 大大提高了运算效率 v1 anx an 1 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 观察上述秦九韶算法中的n个一次式 可见vk的计算要用到vk 1的值 若令v0 an 得 这是一个在秦九韶算法中反复执行的步骤 因此可用循环结构来实现 问题 画出程序框图 表示用秦九韶算法求5次多项式f x a5x5 a4x4 a3x3 a2x2 a1x a0当x x0 x0是任意实数 时的值的过程 然后写出程序 算法步骤如下 第一步 输入多项式次数n 最高次项的系数an和x的值 第二步 将v的值初始化为an 将i的值初始化为n 1 第三步 输入i次项的系数ai 第四步 v vx ai i i 1 第五步 判断i是否大于或等于0 若是 则返回第三步 否则 输出多项式的值v 否 程序框图 开始 输入n an x的值 i 0 i n 1 v an v vx ai i i 1 输出v 结束 是 输入ai 进位制 1 3 3 问题1 我们常见的数字都是十进制的 但是并不是生活中的每一种数字都是十进制的 比如时间和角度的单位用六十进位制 电子计算机用的是二进制 那么什么是进位制 不同的进位制之间又有什么联系呢 进位制是人们为了计数和运算的方便而约定的一种记数系统 约定满二进一 就是二进制 满十进一 就是十进制 满十六进一 就是十六进制 等等 满几进一 就是几进制 几进制的基数就是几 可使用数字符号的个数称为基数 基数都是大于1的整数 例如 二进制可使用的数字有0和1 基数是2 十进制可使用的数字有0 1 2 8 9等十个数字 基数是10 十六进制可使用的数字或符号有0 9等10个数字以及A F等6个字母 规定字母A F对应10 15 十六进制的基数是16 注意 为了区分不同的进位制 常在数字的右下脚标明基数 如111001 2 表示二进制数 34 5 表示5进制数 十进制数一般不标注基数 问题2 十进制数3721中的3表示3个千 7表示7个百 2表示2个十 1表示1个一 从而它可以写成下面的形式 3721 3 103 7 102 2 101 1 100 想一想二进制数1011 2 可以类似的写成什么形式 1011 2 1 23 0 22 1 21 1 20 同理 3421 5 3 53 4 52 2 51 1 50 C7A16 16 12 164 7 163 10 162 1 161 6 160 一般地 若k是一个大于1的整数 那么以k为基数的k进制数可以表示为一串数字连写在一起的形式 anan 1 a1a0 k 0 an k 0 an 1 a1 a0 k 意思是 1 第一个数字an不能等于0 2 每一个数字an an 1 a1 a0都须小于k k进制的数也可以表示成不同位上数字与基数k的幂的乘积之和的形式 即 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 注意这是一个n 1位数 问题3 二进制只用0和1两个数字 这正好与电路的通和断两种状态相对应 因此计算机内部都使用二进制 计算机在进行数的运算时 先把接受到的数转化成二进制数进行运算 再把运算结果转化为十进制数输出 那么二进制数与十进制数之间是如何转化的呢 例1 把二进制数110011 2 化为十进制数 分析 先把二进制数写成不同位上数字与2的幂的乘积之和的形式 再按照十进制数的运算规则计算出结果 解 110011 2 1 25 1 24 0 23 0 22 1 21 1 20 1 32 1 16 1 2 1 51 问题4 你会把三进制数10221 3 化为十进制数吗 解 10221 3 1 34 0 33 2 32 2 31 1 30 81 18 6 1 106 总结 k进制数转化为十进制数的方法 先把k进制的数表示成不同位上数字与基数k的幂的乘积之和的形式 即 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 再按照十进制数的运算规则计算出结果 例设计一个算法 把k进制数a 共有n位 化为十进制数b 算法步骤如下 开始 输入a k n b 0 i 1 把a的右数第i位数字赋给t i i 1 i n 输出b 结束 否 是 INPUTa k ni 1b 0t aMOD10DOb b t k i 1 a a 10t aMOD10i i