1.3.1算法案例(一)
更新时间:2023-06-09 17:10:01 阅读量: 实用文档 文档下载
- 算法案例教案推荐度:
- 相关推荐
必修1,3 第一章 集合与函数概念 第一章 算法初步
2 8251
算法案例(一) 算法案例(案例1 案例 辗转相除法与更相减损术
必修1,3 第一章 集合与函数概念 第一章 算法初步
创设情景, 〖创设情景,揭示课题〗 [问题1]:在小学,我们已经学过求最大公约数的知 问题1]:在小学, 1]识,你能求出18与30的最大公约数吗? 你能求出18与30的最大公约数吗? 18 的最大公约数吗
2 18 30 3 9 15 3 5 ∴18和30的最大公约 ∴18和30的最大公约 数是2 数是2×3=6.(1) 5 ) 25 5 35 7
方法:先用两个数公有的质 方法:先用两个数公有的质 因数连续去除 连续去除, 因数连续去除,一直除到所得 的商是互质数为止, 的商是互质数为止,然后把所 有的除数连乘起来. 有的除数连乘起来.
练习1(1)求25和35的最大公约数 求49和63的最大公约数 求 和 的最大公约数 的最大公约数,(2)求 和 的最大公约数 的最大公约数. 练习(2) 7 ) 49 7 63 9
所以, 和 的最大公约数为 的最大公约数为5 所以,25和35的最大公约数为
所以, 和 的最大公约数为 的最大公约数为7 所以,49和63的最大公约数为
必修1,3 第一章 集合与函数概念 第一章 算法初步
创设情景, 〖创设情景,揭示课题〗 [问题2]:我们都是利用找公约数的方法来求最 问题2]:我们都是利用找公约数的方法来求最 2]: 大公约数, 大公约数,如果公约数比较大而且根据我们的 观察又不能得到一些公约数, 观察又不能得到一些公约数,我们又应该怎样 求它们的最大公约数?比如求8251 6105的最 8251与 求它们的最大公约数?比如求8251与6105的最 大公约数? 大公约数? 思路1:试值?! 思路 :试值?!2 8251 2 6150 3 8251 3 6150 4 8251 4 6150 5 8251 5 6150 6 8251 6 6150
何时结束?有何好的方法? 何时结束?有何好的方法?
必修1,3 第一章 集合与函数概念 第一章 算法初步
案例一:辗转相除法(欧几里得算法) 案例一:辗转相除法(欧几里得算法)观察用辗转相除法求8251和6105的最大公约数的过程 观察用辗转相除法求 和 的最大公约数的过程 第一步 用两数中较大的数除以较小的数,求得商和余数 用两数中较大的数除以较小的数, 8251=6105×1+2146 ×
结论: 的公约数就是6105和2146 结论: 8251和6105的公约数就是 和 的公约数就是 和 的公约数, 的最大公约数, 的公约数,求8251和6105的最大公约数,只要 和 的最大公约数 求出6105和2146的公约数就可以了 的公约数就可以了. 求出6105和2146的公约数就可以了. 第二步 对6105和2146重复第一步的做法 和 重复第一步的做法 6105=2146×2+1813 × 同理6105和2146的最大公约数也是 的最大公约数也是2146和1813 同理 和 的最大公约数也是 和 的最大公约数. 的最大公约数
必修1,3 第一章 集合与函数概念 第一章 算法初步
完整的过程8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0
例如,用辗转相除法求 例如,用辗转相除法求225和135的最大公约数 和 的
最大公约数 225=135×1+90 135=90×1+45 90=45×2 显然45是 和 的最大公约数 的最大公约数, 显然 是90和45的最大公约数,也就是 225和135的最大公约数 和 的最大公约数
思考: 思考:从上面的两个例子可 以看出计算的规律是什么? 以看出计算的规律是什么?S1:用大数除以小数 : S2:除数变成被除数,余数变成除数 :除数变成被除数, S3:重复S1,直到余数为 :重复 ,直到余数为0
显然37是 显然 是148和37的最大公约 和 的最大公约 也就是8251和6105的最 数,也就是 和 的最 大公约数
必修1,3 第一章 集合与函数概念 第一章 算法初步
利用辗转相除法求最大公约数的步骤如下: 利用辗转相除法求最大公约数的步骤如下:第一步:用较大的数m除以较小的数n 第一步:用较大的数m除以较小的数n得到一 个商q 和一个余数r (m=n× 个商q0和一个余数r0;(m=n×q0+r0) 第二步: 为最大公约数; 第二步:若r0=0,则n为m,n为最大公约数; ≠0,则用除数n除以余数r 得到一个商q 若r0≠0,则用除数n除以余数r0得到一个商q1和一 个余数r 个余数r1;(n=r0×q1+r1) 第三步: r0为最大公约 第三步:若r1=0,则r0为m, r0为最大公约 ≠0,则用除数r 除以余数r 数;若r1≠0,则用除数r0除以余数r1得到一个商 和一个余数r q2和一个余数r2;(r0=r1×q2+r2) …… 此时所得到的r 依次计算直至r 依次计算直至rn=0,此时所得到的rn-1 ,即 为所求的最大公约数. 为所求的最大公约数.
必修1,3 第一章 集合与函数概念 第一章 算法初步
辗转相除法是一个反复执行 直到余数等于0停止的步骤, 直到余数等于0停止的步骤, 这实际上是一个循环结构. 这实际上是一个循环结构. 用程序框图表示出右边的过程
m=n×q+r8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333
r=m MOD n m=n n=r r=0? 是 否
1813=333×5+148 333=148×2+37 148=37×4+0
必修1,3 第一章 集合与函数概念 第一章 算法初步
思考:画出辗转相除法的程序框图并设计其程序 思考:开始输入两个正数m,n 输入两个正数
r=m MOD nm=n n=r r=0?
否
是输出n 输出
INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT n END
结束
必修1,3 第一章 集合与函数概念 第一章 算法初步
思考:画出辗转相除法的程序框图并设计其程序 思考:开始输入两个正数m,n 输入两个正数 m<n?
是x=n n=m m=x n=r m=n
否
r=m MOD nr≠0?
是
否输出n 输出
结束
INPUT m,n IF m<n THEN x=n n=m m=x END IF r=m MOD n WHILE r<>0 m=n n=r r=m MOD n WEND PRINT n END
必修1,3 第一章 集合与函数概念 第一章 算法初步
练习2 利用辗转相除法求两数4081与 练习2:利用辗转相除法求两数4081与 4081 20723的最大公约数 的最大公约数. 20723的最大公约数. (53) 20723=4081×5+318; × 4081=318×12+265; × 318=265×1+53; × 265=53×5+0. ×
必修1,3 第一章 集合与函数概念 第一章 算法初步
知识探究( 知识探究(二):更相减损术
1:设两个正整数m n n=k, 1:设两个正整数m>n,若m-n=k,则m与n 设两个正整数 的最大公约数和n 的最大公约数相等. 的最大公约数和n与k的最大公约数相等. 反复利
用这个原理,可求得98 63的最 98与 反复利用这个原理,可求得98与63的最 大公约数为多少? 大公约数为多少? 98-63=35, 98-63=35, 63-35=28, 63-35=28, 35-28=7, 35-28=7, 28-7=21, 28-7=21, 21-7=14, 21-7=14, 14-7=7. 14-
必修1,3 第一章 集合与函数概念 第一章 算法初步
《九章算术》——更相减损术 九章算术》 更相减损术 算理:可半者半之,不可半者,副置分母、子之数, 算理:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之 以少减多,更相减损,求其等也,以等数约之.
第一步:任意给顶两个正整数;判断他们是否都是偶数。 第一步:任意给顶两个正整数;判断他们是否都是偶数。若是,则用2约简;若不是则执行第二步. 若是,则用2约简;若不是则执行第二步.
第二步:以较大的数减较小的数, 第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作, 的数比较,并以大数减小数。继续这个操作,直到所得的 减数和差相等为止,则这个等数就是所求的最大公约数. 减数和差相等为止,则这个等数就是所求的最大公约数
必修1,3 第一章 集合与函数概念 第一章 算法初步
2:上述求两个正整数的最大公约数的方 2:上述求两个正整数的最大公约数的方 法称为更相减损术 一般地, 更相减损术. 法称为更相减损术.一般地,用更相减损 术求两个正整数m 的最大公约数, 术求两个正整数m,n的最大公约数,可 以用什么逻辑结构来构造算法? 以用什么逻辑结构来构造算法?其算法 步骤如何设计? 步骤如何设计?第一步,给定两个正整数m,n(m>n). 第一步,给定两个正整数m 第二步,计算m 所得的差k. 第二步,计算m-n所得的差k. 第三步,比较n与k的大小,其中大者用m表 第三步,比较n 的大小,其中大者用m 小者用n表示. 示,小者用n表示. 第四步, m=n, 第四步,若m=n,则m,n的最大公约数等于 否则,返回第二步. m;否则,返回第二步.
必修1,3 第一章 集合与函数概念 第一章 算法初步
3:该算法的程序框图如何表示? 3:该算法的程序框图如何表示? 该算法的程序框图如何表示开始 输入m, 输入 ,n m≠n? ? m=k否
否
是 k=m-n n>k? ? 是 m=n n=k 输出m 输出 结束
必修1,3 第一章 集合与函数概念 第一章 算法初步
4:该程序框图对应的程序如何表述? 4:该程序框图对应的程序如何表述? 该程序框图对应的程序如何表述 开始 m, INPUT m,n WHILE m<>n n 输入m, 输入 ,n k=mk=m-n n>k IF n k THEN 否 m≠n? ? m=n 是 n=k k=m-n m=k ELSE m=k 否 输出m 输出 n>k? ? END IF 是 WEND 结束 m=n PRINT m n=k END
必修1,3 第一章 集合与函数概念 第一章 算法初步
“更相减损术”在中国古代数学专著 更相减损术” 九章算术》中记述为: 《九章算术》中记述为: 可半者半之,不可半者,副置分母、 可半者半之,不可半者,副置分母、子 之数,以少减多,更相减
损,求其等也, 之数,以少减多,更相减损,求其等也, 以等数约之. 以等数约之.
必修1,3 第一章 集合与函数概念 第一章 算法初步
INPUT “m,n=“;m,n IF m<n THEN a=m m=n n=a END IF K=0 WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n=n/2 k=k+1 WEND d=m- n
While d<>n IF d>n then m=d ELSE m=n n=d End if d=m-n Wend d=2^k*d PRINT d End
必修1,3 第一章 集合与函数概念 第一章 算法初步
理论迁移
例1 分别用辗转相除法和更相减损 术求168 93的最大公约数 168与 的最大公约数. 术求168与93的最大公约数. 辗转相除法:168=93×1+75, 辗转相除法:168=93×1+75, 93=75×1+18, 93=75×1+18, 75=18×4+3, 75=18×4+3, 18=3× 18=3×6.
必修1,3 第一章 集合与函数概念 第一章 算法初步
更相减损术:168-93=75, 更相减损术:168-93=75, :168 93-75=18, 93-75=18, 75-18=57, 75-18=57, 57-18=39, 57-18=39, 39-18=21, 39-18=21, 21-18=3, 21-18=3, 18-3=15, 18-3=15, 15-3=12, 15-3=12, 12-3=9, 12-3=9, 3=6, 9-3=6, 6-3=3.
必修1,3 第一章 集合与函数概念 第一章 算法初步
325,130,270三个数的最大 例2 求325,130,270三个数的最大 公约数. 公约数. 325=130× 因为325=130 2+65,130=65× 因为325=130×2+65,130=65×2, 所以325 130的最大公约数是65. 325与 的最大公约数是65 所以325与130的最大公约数是65. 因为270=65×4+10,65=10×6+5, 因为270=65×4+10,65=10×6+5, 270=65 10=5× 所以65 270最大公约数是 65与 最大公约数是5 10=5×2,所以65与270最大公约数是5. 故325,130,270三个数的最大公约 325,130,270三个数的最大公约 数是5. 数是5.
必修1,3 第一章 集合与函数概念 第一章 算法初步
小结作业 1.辗转相除法 辗转相除法, 1.辗转相除法,就是对于给定的两个正整 用较大的数除以较小的数, 数,用较大的数除以较小的数,若余数不为 则将余数和较小的数构成新的一对数, 零,则将余数和较小的数构成新的一对数, 继续上面的除法,直到大数被小数除尽为止, 继续上面的除法,直到大数被小数除尽为止, 这时的较小的数即为原来两个数的最大公约 数. 更相减损术, 2. 更相减损术,就是对于给定的两个正 整数,用较大的数减去较小的数, 整数,用较大的数减去较小的数,然后将差 和较小的数构成新的一对数, 和较小的数构成新的一对数,继续上面的减 直到差和较小的数相等, 法,直到差和较小的数相等,此时相等的两 数即为原来两个数的最大公约数. 数即为原来两个数的最大公约数.
正在阅读:
1.3.1算法案例(一)06-09
公共关系学(本)阶段练习203-01
20XX年5月小学班主任工作计划12-11
化工原理答案(夏清主编,包括绪论)10-19
2022-2022年高中数学山东高三高考真卷模拟试题【5】含答案考点及04-11
吴江20092010学年第二学期高二期末测试文科试题6科6套英语04-13
MVT型矿床01-04
最让我难忘的事作文500字07-11
洞头县财政局行政执法依据梳理统计表09-07
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 算法
- 案例
- 1.3
- 【备考2014】(安徽专用)2013版高中历史 阶段滚动检测(二)第一~十六单元全程复习方略精练精析 新人教版
- cmodels - sat-based disjunctive answer set solver
- 凤凰小学教师备课要求
- 一般病人住院流程图
- 5周岁的iPad走上十字路口 该何去何从
- 论文:老板与职业经理人的“中国式离婚”
- 护理学基础-案例分析
- 数据库原理及应用(答案已补全)
- SiC_p_Al基复合材料的切削加工研究现状
- 正方形性质导学案
- 中国移动国际漫游统一资费表
- 变频旋转式压缩机的研究现状与进展
- 2010年GCT语文预测试题及答案下载
- 2005~2006学年第二学期高等数学期末试卷(1)
- 论内部审计在公司治理中的作用
- 日产2500t复合水泥(矿渣和粉煤灰)粉磨车间工艺设计说明书
- 从一起行政诉讼案再论动产抵押登记审查制度的调整和变化
- 2012年中国工业经济运行上半年报告
- 5.1-ABB变频器ACS800-67参数的设置-20100717
- 答案 大学语文第3阶段测试题3a