




已阅读5页,还剩19页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1 3中国古代数学中的算法案例 一 1 求两个正整数最大公约数的算法 辗转相除法 求两个数的最大公约数 其基本步骤是带余除法m nq r 0 r n 反复执行 直到余数r 0为止 求任意两个数的最大公约数的算法是 第一步 输入两个正整数a b a b 第二步 求出a b的余数r 第三步 令a b b r 若r 0 重复第二步 第四步 输出最大公约数a 举例说明 m 90 n 36 m 2n 18 r 18 令m 36 n 18 又有36 18 2 即m 2n 此时r 0 令m 18 n 0 故最大公约数为18 算理 先找到a b中较大的 记为a a b t c 若c 0 记a b b c 返回第2步进行循环 若c 0 输出b 输出b b c y n 输入a b a b c amodb 结束 开始 c amodb a input a b input b c modulo a b whilec0a b b c c modulo a b endb 更相减损术 以两数中较大的数减去较小的数 即78 36 42 以差数42和较小的数36构成新的一对数 对这一对数再用大数减去小数 即42 36 6 再以差数6和较小的数36构成新的一对数 对这一对数再用大数减去小数 即36 6 30 再构成新的一对数 例如 求78和36的最大公约数 继续这一过程 直到产生一对相等的数 这个数就是最大公约数 操作如下 78 36 42 36 6 36 6 30 6 24 6 18 6 12 6 6 理论依据 由a b r a b r 得 a b 与 b r 有相同的公约数 算法如下 s1输入两个正数a b a b s2如果a b 则执行s3 否则转到s5 s3将a b的值赋予r s4若b r 则把b赋予a 把r赋予b 否则把r赋予a 重新执行s2 s5输出最大公约数 输出b y n 输入a b a b 结束 开始 a b b b a a a b y n 程序 a input a b input b whileabifa ba a b elseb b a endendprint io 2 b 两数的最大公约数为 例1 用等值算法 更相减损术 求下列两数的最大公约数 1 225 135 2 98 280 例2 用辗转相除法验证上例中两数的最大公约数是否正确 答案 1 45 2 14 2 割圆术 魏晋时期数学家刘徽 割之弥细 所失弥少 割之又割 以至于不可割 则与圆合体而无所失矣 即从圆内接正六边形开始 让边数逐次加倍 逐个算出这些内接正多边形的面积 从而得到一系列逐次递增的数值 第一 从半径为1的圆内接正六边形开始 计算它的面积s6 第二 逐步加倍圆内接正多边形的边数 分别计算圆内接正十二边形 正二十四边形 正四十八边形 的面积 到一定的边数 设为2m 为止 得到一列递增的数 s6 s12 s24 s48 s2m 第三 s2m近似等于圆面积 下面的关键是找出正n边形的面积与正2n边形的面积之间的关系 以便递推 设圆的半径为1 正n边形的边长ab为xn 弦心距og为hn 面积为sn 根据勾股定理 得 容易知道x6 1 正2n边形的面积等于正n边形的面积加上n个等腰三角形的面积 即 正2n边形的边长为 于是由 求得s12 3 s24 3 105828 n 6 x 1 s 6 sqrt 3 4 fori 1 1 5h sqrt 1 x 2 2 s s n x 1 h 2 n 2 n x sqrt x 2 2 1 h 2 endprint io 2 n s 程序 数学运用 例1 两个正整数的最小公倍数 实际上就是这两数乘积除以它们的最大公约数 试写出求正整数a b最小公倍数的程序 a input a b input b c modulo a b d a b whilec0a b b c c modulo a b endprint io 2 d b 数学运用 例2 用更相减损术求98与63的最大公约数 解 由于63不是偶数 把98和63以大数减小数 并辗转相减 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7 所以 98和63的最大公约数等于7 课堂练习 1 下面一段伪代码的目的是 10reada b20ifa b int a b thengoto7030c a int a b b40a b50b c60goto2070printb a 求a b的最小公倍数b 求a b的最大公约数c 求a被b整除的商d 求b除以a的余数 分析 解题关键就是 a int a b b mod a b b 2 写出图示流程图所表达算法的伪代码 并求出最后输出的n的值 课堂练习 10m 14720n 8430r mod m n 40ifr 0thengoto7050m n n r60goto3070printn80end n的值为21 课堂练习 3 用更相减损术求两个正数84与72的最大公约数 分析 先约简 再求21与18的最大公约数 然后乘以两次约简的质因数4 21 18 318 3 1515 3 1212 3 99 3 66 3 3 所以 21和18的最大公约数等于3 所以 84和72的最大公约数等于12 回顾反思 1 辗转相除法是当大数被小数除尽时 结束除法运算 较小的数就是最大公约数 2 更相减损术是当
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025-2030工业视觉检测深度学习算法在瑕疵识别中的过拟合对策
- 2025-2030工业级无人机巡检数据分析平台架构设计报告
- 2025-2030工业级3D打印金属粉末循环利用技术与成本节约空间
- 2025-2030工业级3D打印材料性能优化与航空航天应用前景报告
- 2025-2030工业物联网边缘计算节点安全防护体系与攻击溯源机制构建
- 中药学临床应用说课稿范文
- 汉语言文学就业现状调查报告
- IT运维故障处理快速响应程序
- 公路桥梁养护技术规范与操作标准
- 小学综合实践课:植物观察教学设计
- 康复养老护理辅具研发
- 2024(苏教版)劳动六年级上册全册教学案
- 2025秋苏教版(2024)小学科学二年级上册(全册)教学设计(附目录P123)
- 2025年amOLED行业研究报告及未来行业发展趋势预测
- 2025年国家电网公司招聘面试模拟题集与答案解析
- 拍照摄影技巧
- 校园招聘服务协议书范本
- 语音厅运营基础知识培训
- 广州市房屋租赁合同国土局标准模版
- 停车场保安安全知识培训课件
- 校长在食堂从业人员培训会上的讲话
评论
0/150
提交评论