1.4 算法案例（教案）-2020年高中同步教与学数学(苏教版必修3)

高中同步教与学·全新教案(活页) 第1章算法初步 1.4算法案例(1课时 教学目标》 情感、态度与价值观 1.通过学生的主动参与,师生,生生的合作交流,提高学生的 知识与技能 兴趣,激发其求知欲,培养探索精神 1.介绍中国古代算法的案例:韩信点兵一孙子问题 2.体会中国古代数学发展的贡献,培养爱国主义情怀 理解辗转相除法与更相减损术中蕴含的数学原理,并能 根据这些原理进行算法分析 重点难点》 3.基本能根据算法语句与流程图的知识设计完整的流程图u重点 写出算法程序 理解辗转相除法与更相减损术求最大公约数的方法 过程与方法 难点 1.改变解决问题的思路,要将抽象的数学思维变为具体的步 把辗转相除法与更相减损术的方法转换成流程图与伪代 骤化的思维方式,提高逻辑思维能力 2.学会借助实例分析,探索数学问题 《案例(-)》 教学过程》 、新课导入 ②m被5除后余3,即Mod(m,5)=3; 提出问题:在小学,我们已经学过求最大公约数的知识,如口 ③m被7除后余2,即Mod(m,7)=2. 算求出12与20的公约数.其方法为:先用两个数公有的质因数 用自然语言可以将算法写为 连续去除,一直除到所得的商是互质数为止,然后把所有的除数 连乘起来.我们都是利用找公约数的方法来求最大公约数,如果 S2如果Mod(m,3)≠2或Mod(m,5)≠3或Mod(m,7)≠ 公约数比较大而且根据我们的观察又不能得到一些公约数,我2则执行S3,否则执行S4 们又应该怎样求它们的最大公约数?比如求8251与6105的最 nm+1; 大公约数?这就是我们这一堂课所要探讨的内容 S4输出 设计意图通过已学内容,激发学生兴趣.引出本节所学内 流程图和伪代码: (妗 、讲授新课 1.剩余定理 例1韩信是秦末汉初的著名军事家.据说有一次汉高祖刘 邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐 个报数,就能知道场上的士兵的人数 韩信先令士兵排成3列纵队,结果有2个人多余;接着立 Ⅵodm,5)3或 下令将队形改为5列纵队,这一改,又多出3人;随后他又下令改 为7列纵队,这次又剩下2人无法成整行 在场的人都哈哈大笑,以为韩信不能清点出准确的人数,不 料笑声刚落,韩信高声报告共有士兵2工科333人.众人听了 输出m 愣,不知道韩信用什么方法这么快就能得出正确的结果的.同学 们,你知道吗? 【学生】根据教师给出的框图写出伪代码 【教师】孙子问题”相当于求关于x,y,x的不定方程组的 伪代码 m=5y+3,的正整数解 While mod(m,3)≠2或Mod(m,5)≠3或Mod(m,7)≠2 m=7x+2 【教师】给出框图并分析算法 设所求的数为m,根据题意m应该同时满足下列三个条件 End while Print m ①m被3除后余2,即Mod(m,3)=2 2.辗转相除法 高中同步教与学·全新教案(活页) 例2求两个正数8251和6105的最大公约数 教师分析:8251与6105两数都比较大,而且没有明显的公 输入m 约数,我们可以考虑用两数中较大的数除以较小的数,求得商和 余数 8251=6105×1+2146 显然6105与2146的公约数也必是8251与6105的公约 数,反过来,8251与6105的最大公约数也是6105与2146的 最大公约数,所以它们的最大公约数相等 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 最后的除数37是148和37的最大公约数,也就是8251与 结甫 6105的最大公约数 以上我们求最大公约数的方法就是辗转相除法.也叫欧几 设计意图通过学生在老师的引导下主动探究,培养学生 里得算法,它是由欧几里得在公元前300年左右首先提出的 合作探究的精神,进一步培养学生应用新知识解决问题的能力 【学生练习】同桌相互给对方出一个题 例3求1734,816,1343的最大公约数 【教师总结】用辗转相除法求最大公约数的步骤如下: 【教师】分析:三个数的最大公约数分别是每个数的约数,因此 (1)用较大的数m除以较小的数n得到一个商S和一个余 也是任意两个数的最大公约数的约数,也就是说三个数的最大公约 数R0 数是其中任意两个数的最大公约数与第三个数的最大公约数 (2)若R=0,则n为m,n的最大公约数;若R≠0,则用除 生】用“辗转相「 数n除以余数R得到一个商S1和一个余数R1; 先求1734和816的最大公约数 1734=816×2+102 (3)若R1=0,则R1为m,n的最大公约数;若R1≠0,则用除 数R。除以余数R1得到一个商S1和一个余数R2;……依次计算 816=102×8 直至Rn=0,此时所得到的Rn1即为所求的最大公约数 所以1734与816的