13算法案例.doc

学科：数学 高一年级 25,26 班 教师：蒲军红 课题算法案例教学目标1、理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；2、了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；3、了解各种进位制转化为十进制的规律；4、学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k取余法，并理解其中的数学规律.教学重点基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.教学难点基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.教学设想通过练习让学生深入体会设计程序的思路与数学思想的运用。教学用具黑板教学方法讲议结合课时安排4板书设计算法案例1、辗转相除法与更相减损术 例题解析2、 秦九韶算法 课堂练习3、各种进位制转化为十进制 课时小结 课后作业教学反思教学设计（首页） 康乐一中教导处制教学活动设计拓展、延伸、补充辗转相除法和更相减损术（一）创设情景、导入课题1.研究一个实际问题的算法，主要从哪几方面展开？算法步骤、程序框图和编写程序三方面展开.2.在程序框图中算法的基本逻辑结构有哪几种？顺序结构、条件结构、循环结构3.在程序设计中基本的算法语句有哪几种？输入语句、输出语句、赋值语句、条件语句、循环语句4.思考1:18与30的最大公约数是多少？你是怎样得到的？5. 思考2:对于8251与6105这两个数，它们的最大公约数是多少？你是怎样得到的？由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢？（板书课题）（二）师生互动、探究新知1. 辗转相除法思考3：注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？ 我们发现6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.思考4：重复上述操作，你能得到8251与6105这两个数的最大公约数吗？61052146×2181321461813×13331813333×5148333148×23714837×40以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商和一个余数；第二步：若0，则n为m，n的最大公约数；若0，则用除数n除以余数得到一个商和一个余数；第三步：若0，则为m，n的最大公约数；若0，则用除数除以余数得到一个商和一个余数；依次计算直至0，此时所得到的即为所求的最大公约数.思考5:你能把辗转相除法编成一个计算机程序吗？第一步，给定两个正整数m，n(m>n).第二步，计算m除以n所得的余数r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步. INPUT m，nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mEND思考6:如果用当型循环结构构造算法，则用辗转相除法求两个正整数m，n的最大公约数的程序框图和程序分别如何表示？审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充INPUT m，nWHILE n>0r=m MOD nm=nn=rWENDPRINT mEND九章算术是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数更相减损术求最大公约数的步骤如下：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之.”翻译出来为：第一步：任意给出两个正整数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步.第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.例1 用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：9863356335283528728721217141477所以，98与63的最大公约数是7。练习：用更相减损术求两个正数84与72的最大公约数。（答案：12）审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充（三）讲练结合，巩固提高例2 分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6.更相减损术:168-93=75，93-75=18，75-18=57，57-18=39，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6， 6-3=3.例3 求325，130，270三个数的最大公约数. 因为325=130×2+65，130=65×2，所以325与130的最大公约数是65. 因为270=65×4+10，65=10×6+5，10=5×2，所以65与270最大公约数是5. 故325，130，270三个数的最大公约数是5.练习:用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(m>n). 审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充第二步，计算m-n所得的差k. 第三步，比较n与k的大小，其中大者用m表示，小者用n表示. 第四步，若m=n，则m，n的最大公约数等于m；否则，返回第二步. 讨论:该算法的程序框图如何表示？讨论:该程序框图对应的程序如何表述？INPUT m，nWHILE mnk=m-nIF n>k THENm=nn=kELSEm=kEND IFWENDPRINT mEND（四）小结1、辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数. 2、更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.（五）布置作业P45练习：1题.P48习题组：1题审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充秦九韶算法（一）复习提问、导入课题1、什么是辗转相除法和更相减损术？2、辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合.（二）师生互动、探究新知1.秦九韶算法的基本思想 思考1：对于多项式，求f（5）的值.根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算。思考2：另一种做法是先计算的值，再把多项式变形为：再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果.显然少了6次乘法运算。思考3:有没有更有效的算法呢？利用后一种算法求多项式的值，这个多项式应写成哪种形式？这就是我国南宋时期数学家秦九韶在他的著作数书九章中提出的算法.这种算法就叫秦九韶算法.思考4:对于f(x)=，由内向外审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充逐层计算一次多项式的值，其算法步骤如何？ 第一步，计算v1=. 第二步，计算v2=v1x+.第三步，计算v3=v2x+.第n步，计算+a0.思考5:在秦九韶算法中，记v0=，那么第k步的算式是什么？ (k=1，2，n)例1、已知一个5次多项式为用秦九韶算法求这个多项式当时的值.解：略思考：（1）例1计算时需要多少次乘法计算？多少次加法计算？ （2）在利用秦九韶算法计算n次多项式当时需要多少次乘法计算和多少次加法计算？练习：阅读下列程序，说明它解决的实际问题是什么？INPUT “x=”；an=0y=0WHLE n<5 y=y+(n+1)*an n=n+1WENDPRINT yEND求多项式 在x=a时的值. 2. 秦九韶算法的程序设计审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，输入多项式的次数n，最高次项的系数和x的值. 第二步，令v=，i=n-1. 第三步，输入i次项的系数. 第四步，i=i-1.INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=ai=n-1WHILE i>=0PRINT “i=”；iINPUT “ai=”；av=v*x+ai=i-1WENDPRINT vEND第五步，判断i0是否成立.若是，则返回第三步；否则，输出多项式的值v. 讨论:该算法的程序框图如何表示？讨论:该程序框图对应的程序如何表述？（三）小结2.计算机的一个很重要的特点就是运算速度快，但评价算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法.在多项式求值的各种算法中，秦九韶算法是一个优秀算法. （四）布置作业P45练习：2.P48习题组：2.审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充 k进制化十进制（一）复习提问、导入课题1.简述辗转相除法和更相减损术的用途及内容.2、秦九韶算法的用途及内容.将这些算法转化为程序，就可以由计算机来完成相关运算.（二）师生互动、探究新知进位制的概念 进位制是为了计数和运算方便而约定的记数系统.约定满二进一，就是二进制；满十进一，就是十进制；七天为一周，就是七进制；十二个月为一年，就是十二进制；六十秒为一分钟，六十分钟为一个小时，就是六十进制；等等.一般地，“满几进一”就是几进制. “满K进一”就是K进制，其中k称为k进制的基数.那么k是一个什么范围内的数？ 思考1:十进制使用09十个数字，那么二进制、五进制、七进制分别使用哪些数字？ 与十进制类似，其它的进位制也可以按照位置原则计数. 在十进制中10表示十，在二进制中10表示2.一般地，若k是一个大于1的整数，则以k为基数的k进制数可以表示为一串数字连写在一起的形式：.思考2：其中各个数位上的数字，a1，a0的取值范围如何？例如:十进制数3721表示的数可以写成：3×103+7×102+2×101+1×100.例1：把二进制数110011（2）化为十进制数.审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充110011（2）=1×25+1×24+0×23+0×22+1×21+1×20 =51 练习：把八进制数 5671（8）化为十进制数.5671（8）=.探究:如何将k进制数写成各数位上的数字与基数k的幂的乘积之和的形式？= ×+ ×+ + a1×k1+ a0×k0讨论:在二进制中，0+0，0+1，1+0，1+1的值分别是多少？例2:二进制数110011（3）化为十进制数是什么数？110011（3）=1×35+1×34+0×33+0×32+1×31+1×30 =243+81+3+1=328讨论: 中化为十进制数是什么数？ai2i-1探究：如何改进上述算法，把其它进位制化为十进制数？请举例说明.练习：将下列各进制数化为十进制数.（1）10304（4） ； （2）4321（5）.10304（4）=1×44+3×42+4×40=308.4321（5）=4×53+3×52+2×51+1×50=586. （三）讲练结合，巩固提高例3:设计一个算法，把2进制数a（共有n位）化为十进制数b，并转化成程序框图，写出程序.第一步，输入a，2和n的值.第二步，令b=0，i=1.第三步，b=b+ai2i-1，i=i+1.第四步，判断i>n 是否成立.若是，则执行第五步；否则，返回第三步.第五步，输出b的值.审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充练习:设计一个算法，把k进制数a（共有n位）化为十进制数b.第一步，输入a，k和n的值.第二步，令b=0，i=1.第三步，b=b+aiki-1，i=i+1.第四步，判断i>n 是否成立.若是，则执行第五步；否则，返回第三步.第五步，输出b的值.INPUT “a，k，n=”;a,k,nb=0i=1t=a MOD 10DOb=b+t*k（i-1）a=a10t=a MOD 10i=i+1LOOP UNTIL i>nPRINT bENDINPUT “a，2，n=”;a,2,nb=0i=1t=a MOD 10DOb=b+t*2（i-1）a=a10t=a MOD 10i=i+1LOOP UNTIL i>nPRINT bEND例4：已知20a1（2）=b10（3）,求数字a，b的值.20a1（2）=2×23+a×2+1=2a+17.审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充b10（3）=b×32+1×3=9b+3.所以2a+17=9b+3，即9b-2a=14. 故a=2，b=2. （四）小结1、k进制数使用0（k-1）共k个数字，但左侧第一个数位上的数字（首位数字）不为0.2、用表示k进制数，其中k称为基数，十进制数一般不标注基数.3、把k进制数化为十进制数的一般算式是：= ×+ ×+ + a1×k1+ a0×k0（五）布置作业：P48习题1.3B组：1.审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充 十进制化k进制（一）复习提问、导入课题1、“满几进一”就是几进制.2、k进制使用0，1，k-1这k个数字.3、k进制数化为十进制数的一般算式: = ×+ ×+ + a1×k1+ a0×k04、利用k进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把任何一个k进制数化为十进制数.（二）师生互动、探究新知练习:把二进制数100101（2）化为十进制数.100101（2）=1×25+0×24+0×23+1×22+0×21+1×20 =37讨论:怎样把十进制数89化为二进制数？例1:把十进制数89化为二进制数.观察下面的算式你有什么发现吗？ 89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1=1×26+0×25+1×24+1×23+0×22+0×21+1×20=1011001（2）.根据二进制“满二进一”的原则，可以用2连续去除89所得商，然后取余数. 这样化十进制数为二进制数的算法叫做除2取余法.练习:把十进制数196化为五进制数.除二取余法也可以推广为把十进制数化为k进制数的算法，称为除k取余法.即用5连续去除196或所得商，然后取余数.196=1241（5）推广：怎样把十进制数转化为k进制数？若十进制数a除以k所得的商是q0，余数是r0， 审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充即a=k·q0+ r0；q0除以k所得的商是q1，余数是r1，即q0=k·q1+ r1； qn-1除以k所得的商是0，余数是rn， 即qn-1= rn，那么十进制数a化为k进制数是：a=例2:根据上面的分析，将十进制数a化为二进制数的算法步骤如何设计？第一步，输入十进制数a的值.第二步，求出a除以2所得的商q，余数r.第三步，把所得的余数依次从右到左排列.第四步，若q0，则a=q，返回第二步；否则，输出全部余数r排列得到的二进制数.练习:设计一个程序，实现“除k取余法”（kN，2k9）.第一步，输入十进制数a的值和基数k的值.INPUT a，k b=0i=0DOq=akr=a MOD kb=b+r*10ii=i+1a=qLOOP UNTIL q=0PRINT bEND第二步，求出a除以k所得的商q，余数r.第三步，把所得的余数依次从右到左排列.第四步，若q0，则a=q，返回第二步；否则，输出全部余数r排列得到的二进制数.审阅人年 月 日 教学设计（续页） 康乐一中教导处制教学活动设计拓展、延伸、补充（三）讲练结合，巩固提高练习1 将十进制数258分别转化为四进制数和六进制数.258=10002（4）=1110（6）练习2 将五进制数1234（5）转化为七进制数. 1234（5）=365（7） （四）小结1、进位制的概念及转化方法.2、通过k进制数与十进制数的相互转化，实现计算机操作.（五）布置作业：P45练习：3.P48习题组：3、4.审阅人年 月 日 教学设计（续页） 康乐一中教导处制