- 1、本文档共12页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
课题:§1.3 算法案例
第 1 课时 辗转相除法与更相减损术、秦九韶算法
一、教学目标:
根据课标要求:在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框 图和程序三种不同方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在解决问题中的重要作用,体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力。制定以下三维目标:
1、知识与技能
理解算法案例的算法步骤和程序框图.
2、过程与方法:
引导学生得出自己设计的算法程序.
3、情感态度与价值观:
体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.
二、重点与难点:
重点:引导学生得出自己设计的算法步骤、程序框图和算法程序.
解决策略:通过分析解决具体问题的算法步骤来引导学生写出算法,根据算法画出程序框图,再根据框图用规范的语言写出程序。
难点:体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力. 解决策略:让学生能严谨地按照自己是程序框图写出程序。
三、学法与教学用具:
1、学法:直观感知、操作确认。
2、教学用具:多媒体。
四、教学过程
(一)引入课题
大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球, 东方人喜欢直握拍打球,对于同一个问题,东、西方人处理问题方式是有所不同的.在小 学,我们学过求两个正整数的最大公约数的方法:先用两个数公有的质因数连续去除,一 直除到所得的商是互质数为止,然后把所有的除数连乘起来. 当两个数公有的质因数较大
时(如 8 251 与 6 105),使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异.
(二)研探新知
怎样用短除法求最大公约数?
怎样用穷举法(也叫枚举法)求最大公约数?
怎样用辗转相除法求最大公约数?
怎样用更相减损术求最大公约数? 讨论结果:
短除法
求两个正整数的最大公约数的步骤:先用两个数公有的质因数连续去除,一直除到所得的商是两个互质数为止,然后把所有的除数连乘起来.
穷举法(也叫枚举法)
穷举法求两个正整数的最大公约数的解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数.
辗转相除法
辗转相除法求两个数的最大公约数,其算法步骤可以描述如下: 第一步,给定两个正整数m,n.
第二步,求余数r:计算m 除以n,将所得余数存放到变量r 中. 第三步,更新被除数和余数:m=n,n=r.
第四步,判断余数r 是否为 0.若余数为 0,则输出结果;否则转向第二步继续循环执行. 如此循环,直到得到结果为止. 这种算法是由欧几里得在公元前 300 年左右首先提出的, 因而又叫欧几里得算法.
更相减损术
我国早期也有解决求最大公约数问题的算法,就是更相减损术. 《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之, 不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”翻译为现 代语言如下:
第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用2 约简;若不是,执行第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数, 继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
(三)范例分析
例 1 用辗转相除法求 8 251 与 6 105 的最大公约数,写出算法分析,画出程序框图,写出算法程序.
解:用两数中较大的数除以较小的数,求得商和余数:8 251=6 105×1+2 146.
由此可得,6 105 与 2 146 的公约数也是 8 251 与 6 105 的公约数,反过来,8 251 与 6 105 的公约数也是 6 105 与 2 146 的公约数,所以它们的最大公约数相等.
对 6 105 与 2 146 重复上述步骤:6 105=2 146×2+1 813.
同理,2 146 与 1 813 的最大公约数也是 6 105 与 2 146 的最大公约数.继续重复上述步骤: 2 146=1 813×1+333,
1 813=333×5+148,
333=148×2+37,
148=37×4.
最后的除数 37 是 148 和 37 的最大公约数,也就是 8 251 与 6 105 的最大公约数.
这就是辗转相除法.由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可以在有限步之后完成,从而总可以用辗转相除法求出两个正整数的最大公约数.
算法分析:从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环结构来构造算法.
算法步骤如下:
第一步,
您可能关注的文档
最近下载
- 第4课《古代诗歌四首——闻王昌龄左迁龙标遥有此寄》课件(共27张PPT)2022—2023学年部编版语文七年级上册.pptx
- 直播运营管理全套完整教学课件.pptx
- PDA TR27-1998 Pharmaceutical Package Integrity英文原版资料.pdf
- Q∕GDW 11897-2018 调度自动化机房设计与建设规范.docx
- 建筑专业图集-03J001:围墙大门.pdf
- 2024年采制样工考试2024年采制样工试题库(判断题)试卷 .pdf
- 营销心理学(第五版)——数字时代消费者行为分析 课件 单凤儒 模块6--8 场景行为:传播与广告心理效应 ---现代场景:网络与新媒体营销心理效应 .pptx
- 内典讲座之研究.pdf
- 新建南通至宁波高速铁路环境影响报告书.pdf
- 2024年GD省生态环境监测专业技术人员大比武模拟试卷及答案-3应急监测.pdf
文档评论(0)