高二数学《算法案例》 课件必修3.ppt

算法案例2 广义地说 为了解决某一问题而采取的方法和步骤 就称之为算法 算法的概念 一般而言 对一类问题的机械的 统一的求解方法称为算法 知识回顾 流程图 是由一些图框和流程线组成的 其中图框表示各种操作的类型 图框中的文字和符号表示操作的内容 流程线表示操作的先后次序 流程图的概念 顺序结构及框图表示 1 顺序结构 依次进行多个处理的结构称为顺序结构 语句a 语句b 2 顺序结构的流程图 顺序结构是最简单 最基本的算法结构 语句与语句之间 框与框之间是按从上到下的顺序进行的 它是由若干个处理步骤组成的 这是任何一个算法都离不开的基本结构 选择结构也叫条件结构 是指在算法中通过对条件的判断 根据条件是否成立而选择不同流向的算法结构 右图此结构中包含一个判断框 根据给定的条件p是否成立而选择执行a框或b框 无论p条件是否成立 只能执行a框或b框之一 不可能同时执行a框和b框 也不可能a框 b框都不执行 直到型循环 当型循环 先执行 后判断 先判断 后执行 n 进入循环 y 进入循环 循环结构 已学过的伪代码中的几种基本算法语句 1 赋值语句 变量 表达式或变量或常数 2 输入语句 reada b 3 输出语句 4 条件语句 printa b ifathenbelsecendif 直到型语句 当循环的次数已经确定 可用 for 语句表示 for 语句伪代码格式 forifrom 初值 to 终值 step 步长 endfor 6 for语句 35 915 在小学 我们学过求两个正整数的最大公约数的方法 先用两个数公有的质因数连续去除 一直到所得的商是互质数为止 然后把所以的除数乘起来 例如 求18与30的最大共约数 1830 2 3 所以 18与30的最大共约数是 2 3 6 引入课题 利用找公约数的方法来求最大公约数 如果公约数比较大而且根据我们的观察又不能得到一些公约数 我们又应该怎样求它们的最大公约数 比如求8251与6105的最大公约数 观察上面的式子 你有什么发现 你的发现 对我们解决 求8251与6105的最大公约数 的问题有什么帮助 8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 以上我们求最大公约数的方法就是辗转相除法 也叫欧几里德算法 它是由欧几里德在公元前300年左右首先提出的 练习 用辗转相除法求204与85的最大公约数 你能把辗转相除法求最大共约数的过程 写成算法吗 该算法中 要用到什么主要的算法结构 每一次循环中所进行的是什么样的运算 循环何时结束 下一次循环的输入整数应该是什么 循环结构 r mod a b r 0 a bb r 这样交换数据的方式 前面我们学习过吗 在求斐波拉契数列中的数 请用自然语言描述该算法 s1输入两个正整数a b a b s2若mod a b 0 则输出最大公约数b 算法结束 否则r mod a b a b b r 转s2 s1输入两个正整数a b a b s2r mod a b s3a bs4b r s5若r不等于0 转s2s6输出最大公约数a 将自然语言描述的算法改写为伪代码 reada bwhilemod a b