




已阅读5页,还剩23页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
古代算法案例 1 回顾算法的四种表示方法 1 自然语言 3 程序框图 4 程序语言 三种逻辑结构 五种基本语句 复习引入 2 数学语言 x 5 y 20 ifx 0 x y 3 elsey y 3 endprint io 2 x y y x b 复习引入 d 3 执行如图的程序 最后一个输出的数是多少 1999 2002 复习引入 c 复习引入 c 高考真题 b 高考真题 c 高考真题 d 高考真题 可半者半之 不可半者 副置分母 子之数 以少减多 更相减损 求其等也 以等数约之 九章算术 中的更相减损术 背景介绍 一 求两个正整数最大公约数的算法 1 更相减损术 等值算法 例如 求78和36的最大公约数 操作如下 78 36 42 36 6 36 6 30 6 24 6 18 6 12 6 6 原理 对任意两个数 每次操作后所得的两数与前两数有相同的最大公约数 而两数的值逐渐减小 经过有限步的操作后 总能得到相等的两个数 即求得两数的最大公约数 7步 算法如下 s1输入两个正数a b s2如果a b 则执行s3 否则转到s5 s3若a b 则把a b的值重新赋予a 否则 a b 则把b a重新赋予b 重新执行s2 s5输出最大公约数 程序框图 程序语言 a input a b input b whileabifa ba a b elseb b a endendprint io 2 a 两数的最大公约数为 2 辗转相除法 求两个数的最大公约数 其基本步骤是带余除法m nq r 0 r n 反复执行 直到余数r 0为止 欧几里得算法 78 36 6 36 1步 288 123 42 123 42 39 3 39 3步 思考 你能把辗转相除法编成一个计算机程序吗 1 算法步骤 第一步 输入两个正整数m n m n 第二步 计算m除以n所得的余数r 第三步 m n n r 第四步 若r 0 则m n的最大公约数等于m 否则转到第二步 第五步 输出最大公约数m 2 程序框图 3 程序 m input m n input n whilemodulo m n 0 r modulo m n m n n r endd r 比较辗转相除法与更相减损术的区别 1 都是求最大公约数的方法 计算上辗转相除法以除法为主 更相减损术以减法为主 计算次数上辗转相除法计算次数相对较少 特别当两个数字大小区别较大时计算次数的区别较明显 2 从结果体现形式来看 辗转相除法体现结果是以相除余数为0则得到 而更相减损术则以减数与差相等而得到 小结 二 秦九韶算法 设计求多项式f x 5x5 3x4 2x3 3x2 x 1当x 2时的函数值 一般的解决方案 x 2 y 5 x 5 3 x 4 2 x 3 3 x 2 x 1 y 设计求多项式f x 5x5 3x4 2x3 3x2 x 1当x 2时的函数值 次加法 次乘法 秦九韶算法适用一般的多项式p x anxn an 1xn 1 a1x a0的求值问题 p x anxn an 1xn 1 a1x a0 anxn 1 an 1xn 2 a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 n次乘法 n次加法 要求多项式的值 应该先算最内层的一次多项式的值 即 然后 由内到外逐层计算一次多项式的值 即 最后的一项是什么 2 n次乘法和n次加法 秦九韶算法的特点 得递推公式为 1 降幂 世界上多项式求值最先进算法 用秦九韶算法求函数 1 几次加
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 两企业合并管理办法
- 产品体验官管理办法
- 集中管控管理办法
- 防灾工程管理办法
- 云南项目库管理办法
- 降职减薪管理办法
- 互联网商城管理办法
- 省学科项目管理办法
- 主管级考核管理办法
- 仓储缓存区管理办法
- 老旧小区施工安全文明施工方案
- 康复科护士的运动障碍康复与护理
- (完整word版)英语国际音标表(48个)打印版
- JCT640-2010 顶进施工法用钢筋混凝土排水管
- 江民杀毒软件
- 网络安全题库及答案(汇总1000题)-网络安全题库及答案
- 医院满意度调查工作制度(二篇)
- 工程项目档案试题
- GB/T 33213-2016无损检测基于光纤传感技术的应力监测方法
- GB/T 2652-1989焊缝及熔敷金属拉伸试验方法
- 建筑设计防火规范2001修订版
评论
0/150
提交评论