算法案例教案.doc

算法案例教案.doc:..课题:§、秦九韶算法一、 教学目标:根据课标要求:在学生学习了算法的初步知识,理解了表示算法的算法步骤、程序框图和程序三种不同方式以后,再结合典型算法案例,让学生经历设计算法解决问题的全过程,体验算法在解决问题中的重要作用,体会算法的基木思想,提高逻辑思维能力,发展冇条理地思考与数学表达能力。制定以下三维冃标:1、 、 过程与方法:、 情感态度与价值观:体会算法的垄本思想,提高逻辑思维能力,、 重点与难点:重点:引导学生得出口己设计的算法步骤、:通过分析解决具体问题的算法步骤來引导学生写出算法,根据算法画出程序框图,再根据框图用规范的语言写出程序。难点:体会算法的基本思想,提髙逻辑思维能力,:让学生能严谨地按照自己是程序框图写出程序。三、 学法与教学用具:1、 学法:肓观感知、操作确认。2、 教学用具:多媒体。四、 教学过程(-)引入课题大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球,东方人喜欢直握扌n打球,对于同一个问题,东、,我们学过求两个正整数的最大公约数的方法:先用两个数公冇的质因数连续去除,一直除到所得的商是互质数为止,(如8251与6105),——辗转相除法与更相减损术,由此可以体会东、西方文化的弟异.(-)研探新知(1) 怎样用短除法求最人公约数?(2) 怎样用穷举法(也叫枚举法)求最大公约数?(3) 怎样用辗转和除法求最大公约数?(4) 怎样用更相减损术求最大公约数?讨论结果:(1) 短除法求两个正整数的最人公约数的步骤:先用两个数公有-的质因数连续去除,一肓除到所得的商是两个互质数为止,然后把所有的除数连乘起来.(2) 穷举法(也叫枚举法)穷举法求两个正整数的最人公约数的解题步骤:从两个数屮较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最人公约数.(3) 辗转相除法辗转相除法求两个数的最人公约数,其算法步骤可以描述如下:第一步,给定两个正整数m,,求余数c计算m除以n,,更新被除数和余数:m二n,n=,,则输出结果;,,因而又叫欧几里得算法.(4) 更相减损术我国早期也有解决求最人公约数问题的算法,就是更相减损术.《九章算术》是屮国古代的数学专著,其中的“更相减损术”也可以用來求两个数的最人公约数,即“可半者半Z,不可半者,副置分母、子之数,以少减多,更相减损,•”翻译为现代语言如下:第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用2约简;若不是,执行第二步,以较大的数减玄•较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,肓到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最人公约数.(三)范例分析例1用辗转相除法求8251与6105的最大公约数,写出算法分析,画出程序框图,:用两数屮较人的数除以较小的数,求得商和余数:8251=6105X1+,6105与2146的公约数也是8251与6105的公约数,反过来,8251与6105的公约数也是6105 2146的公约数,:6105=2146X2+,:2146=1813X1+333,1813=333X5+148,333=148X2+37,148=,,对于任意两个正整数,上述除法步骤总可以在有限步之后完成,:从上面的例子可以看出,辗转相除法中包含重复操作的步骤,:第一步,给定两个正整数m,,,m=n,n=,若一0,则HI,n的最大公约数