1.3算法案例(已修)

13算法案例131辗转相除法和更相减损术一、教学目标：1、知识与技能理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析；基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法与计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤.3、情感与价值观通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献.在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力.二、教学重点、难点：重点：理解辗转相除法与更相减损术求最大公约数的方法.难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.三、教学用具：PPT计算器、图形计算器四、教学设想：（一）创设情景、导入课题1. 研究一个实际问题的算法，主要从哪几方面展开？算法步骤、程序框图和编写程序三方面展开.2. 在程序框图中算法的基本逻辑结构有哪几种？顺序结构、条件结构、循环结构3. 在程序设计中基本的算法语句有哪几种？输入语句、输出语句、赋值语句、条件语句、循环语句4. 思考1:18与30的最大公约数是多少？你是怎样得到的？5. 思考2:对于8251与6105这两个数，它们的最大公约数是多少？你是怎样得到的？由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难.有没有其它的方法可以较简单的找出它们的最大公约数呢？（板书课题）（二）师生互动、探究新知1. 辗转相除法思考3:注意到825仁6105X1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？我们发现6105=2146X2+1813，同理，6105与2146的公约数和2146与1813的公约数相等思考4:重复上述操作，你能得到8251与6105这两个数的最大公约数吗？6105=2146X2+18132146=1813X1+3331813=333X5+148333=148X2+37148=37X4+0以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的.利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商q和一个余数r；第二步：若r。=0,则n为mn的最大公约数；若r。工0，则用除数n除以余数r。得到一个商q1和一个余数*；第三步：若1=0,则r为m,n的最大公约数；若A工0，则用除数r除以余数*得到一个商q?和一个余数J；依次计算直至rn=0,此时所得到的rn4即为所求的最大公约数思考5：你能把辗转相除法编成一个计算机程序吗？第一步，给定两个正整数m,n（mn）.第二步，计算m除以n所得的余数r.第三步，m=n,n=r.第四步，若r=0,则mn的最大公约数等于m否则，返回第二步思考6:如果用当型循环结构构造算法，则用辗转相除法求两个正整数mn的最大公约数的程序框图和程序分别如何表示？2. 更相减损术九章算术是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数更相减损术求最大公约数的步骤如下：“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之”翻译出来为：第一步：任意给出两个正整数；判断它们是否都是偶数若是，用2约简；若不是，执行第二步第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数例1用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98-63=3563-35=2835-28=728-7=2121-7=1414-7=7所以，98与63的最大公约数是7。练习：用更相减损术求两个正数84与72的最大公约数。（答案：12）三）讲练结合，巩固提高例2分别用辗转相除法和更相减损术求168与93的最大公约数.辗转相除法：168=93X1+75,93=75X1+18,75=18X4+3，18=3X6.更相减损术: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=130X2+65,130=65X2，所以325与130的最大公约数是65.因为270=65X4+10,65=10X6+5,10=5X2,所以65与270最大公约数是5.故325,130,270三个数的最大公约数是5.练习：用更相减损术求两个正整数mn的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m,n（mn）.第二步，计算m-n所得的差k.第三步，比较n与k的大小，其中大者用m表示，小者用n表示.第四步，若m=n则m,n的最大公约数等于m;否则，返回第二步.讨论:该算法的程序框图如何表示？讨论:该程序框图对应的程序如何表述？k=m-nIFnkTHENm=nn=kELSEm=kENDIFWENDPRINTm（四）小结1、辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数2、更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数（五）布置作业P45练习：1题.P48习题1.3A组：1题1.3.2秦九韶算法一、教学目标：1、知识与技能了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质；基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.2、过程与方法模仿秦九韶计算方法，体会古人计算构思的巧妙.并从程序的学习中体会数学的严谨，领会数学算法与计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤.3、情感与价值观通过对秦九韶算法的学习，了解中国古代数学家对数学的贡献，充分认识到我国文化历史的悠久并认识到信息技术对数学的促进.二、教学重点、难点：重点：秦九韶算法的特点.难点：把秦九韶算法转换成程序框图与程序语言三、教学用具：PPT计算器、图形计算器四、教学设想：（一）复习提问、导入课题1、什么是辗转相除法和更相减损术？2、辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合（二）师生互动、探究新知1. 秦九韶算法的基本思想思考1：对于多项式f（x）=x5.X4.X3.X2.X1，求f（5）的值.根据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算。2思考2:另一种做法是先计算x的值，再把多项式变形为：2f(x)二x(1x(1x(1x)x1再统计一下计算当x二5时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果显然少了6次乘法运算。思考3:有没有更有效的算法呢？利用后一种算法求多项式f(x)二anxn-anjxnJ-a1x-a0的值，这个多项式应写成哪种形式？nndn_2f(x)二anXanxan亠亠axa。=(anXandxan/Xai)xa。=(anXn之anxnJ32)x-ai)x-a。=(anXanj)xanjxai)ao这就是我国南宋时期数学家秦九韶在他的著作数书九章中提出的算法这种算法就叫秦九韶算法思考4：对于f(x)=iianXanJX-anx川川axao，由内向外逐层计算一次多项式的值，其算法步骤如何？第一步，计算Vi=anXan4第二步，计算v2=vix+an2.第三步，计算v3=v2X+an；第n步，计算vn=vnjX+ao.思考5:在秦九韶算法中，记vo=a0，那么第k步的算式是什么?Vk-Vk4Xan止(k=i,2，n)例i已知一个5次多项式为f(x)=4x52x43.5x-2?-0.8用秦九韶算法求这个多项式当x=5时的值.解：略思考：(i)例i计算时需要多少次乘法计算？多少次加法计算?(2)在利用秦九韶算法计算n次多项式当x时需要多少次乘法计算和多少次加法计算？练习：阅读下列程序，说明它解决的实际问题是什么?y=0WHLEn0是否成立若是，则返回第三步；否则，输出多项式的值v.讨论：该算法的程序框图如何表示？讨论:该程序框图对应的程序如何表述?/InPuT“n=”nINPUT“an=”aINPUT“x=”xv=ai=n-1WHILEi=0PRINT“i=”iINPUT“ai=”av=v*x+ai=i-1WEND（三）小结1. 秦九韶算法计算多项式的值及程序设计2. 计算机的一个很重要的特点就是运算速度快，但评价算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论算法在多项式求值的各种算法中，秦九韶算法是一个优秀算法（四）布置作业：P45练习：2.P48习题1.3A组：2.1.3.3k进制化十进制一、教学目标：1、知识与技能了解各种进位制转化为十进制的规律.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.2、过程与方法学习各种进位制转换成十进制的计算方法，并理解其中的数学规律.进一步巩固把数学算法转化成计算机语言的一般步骤.3、情感与价值观体会进位制转换中存在的趣味二、教学重点、难点：重点：k进制表示数及转化为十进制的方法难点：除k去余法的理解以及各进位制之间转换的程序框图的设计；k进制数一般形式的理解三、教学用具：PPT计算器、图形计算器四、教学设想：（一）复习提问、导入课题1. 简述辗转相除法和更相减损术的用途及内容2、秦九韶算法的用途及内容将这些算法转化为程序，就可以由计算机来完成相关运算（二）师生互动、探究新知进位制的概念进位制是为了计数和运算方便而约定的记数系统约定满二进一，就是二进制；满十进一，就是十进制；七天为一周，就是七进制；十二个月为一年，就是十二进制；六十秒为一分钟，六十分钟为一个小时，就是六十进制；等等一般地，满几进一”就是几进制“满K进一”就是K进制，其中k称为k进制的基数那么k是一个什么范围内的数？思考1:十进制使用09十个数字，那么二进制、五进制、七进制分别使用哪些数字？与十进制类似，其它的进位制也可以按照位置原则计数在十进制中10表示十，在二进制中10表示2.般地，若k是一个大于1的整数，则以k为基数的k进制数可以表示为一串数字连写在一起的形式：ananCa1a0k思考2：其中各个数位上的数字务，an/，a1,a。的取值范围如何？例如：十进制数3721表示的数可以写成:3X103+7X102+2X101+1X10.例1:把二进制数110011(2)化为十进制数543210110011(2)=1X2+1X2+0X2+0X2+1X2+1X2=51练习：把八进制数5671(8)化为十进制数.5671(8)=5汉83+6x82+7X81+1汉8=3001.k的幕的乘积之和探究：如何将k进制数ananja1a0k写成各数位上的数字与基数anan1a1a0的形式?1、八0+a1Xk+a0Xk讨论：在二进制中，0+0,0+1,1+0,1+1的值分别是多少?例2:二进制数110011化为十进制数是什么数?543210110011(3)=1X3+1X3+0X3+0X3+1X3+1X3=243+81+3+1=328讨论：a.ana。2中ai化为十进制数是什么数？i-1ai2探究：如何改进上述算法，把其它进位制化为十进制数？请举例说明练习：将下列各进制数化为十进制数(1)10304(4);(2)4321(5).42010304(4)=1X4+3X4+4X4=308.32104321(5)=4X5+3X5+2X5+1X5=586.(三) 讲练结合，巩固提高例3:设计一个算法，把2进制数a(共有n位)化为十进制数b,并转化成程序框图,写出程序第一步，输入a,2和n的值.第二步，令b=0,i=1.i1第三步，b=b+ai2,i=i+1.第四步，判断in是否成立.若是，则执行第五步；否则，返回第三步.第五步，输出b的值.i=1t=aMOD10DOb=b+t*2A（i-1）a=a10t=aMOD10i=i+1LOOPUNTILinPRINTb练习：设计一个算法，把k进制数a（共有n位）化为十进制数b.第一步，输入a,k和n的值.第二步，令b=0，i=1.第三步，b=b+aiki-1，i=i+1.第四步，判断in是否成立.若是，则执行第五步；否则，返回第三步第五步，输出b的值.i=1t=aMOD10DOb=b+t*k（i-1）a=a10t=aMOD10i=i+1LOOPUNTILinPRINTb例4:已知20a1（2）=b10（3）,求数字a，b的值.320a1（2）=2x2+ax2+1=2a+17.b10（3）=bx3+1X3=9b+3.所以2a+17=9b+3,即9b-2a=14.故a=2,b=2.（四）小结1、k进制数使用0（k-1）共k个数字，但左侧第一个数位上的数字（首位数字）不为0.2、用ananaok表示k进制数，其中k称为基数，十进制数一般不标注基数3、把k进制数化为十进制数的一般算式是：ananaia0k=anxk+玄“二xk+a1xk+aoXk（五）布置作业：P48习题1.3B组：1.1.3.4十进制化k进制一、教学目标：1、知识与技能了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换.2、过程与方法学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k取余法，并理解其中的数学规律.3、情感与价值观体会不同进位制转换中存在的趣味，了解计算机的电路与二进制的联系，进一步认识到计算机与数学的联系.二、教学重点、难点：重点：各进位制表示数的方法及各进位制之间的转换难点：除k取余法的理解以及各进位制之间转换的程序框图的设计；k进制数一般形式的理解三、教学用具：PPT计算器、图形计算器四、教学设想：(一) 复习提问、导入课题1、满几进一”就是几进制2、k进制使用0,1,k-1这k个数字.3、k进制数化为十进制数的一般算式：nn10ana*aiaok=anxk+anjxk+aixk+axk4、利用k进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把任何一个k进制数化为十进制数.(二) 师生互动、探究新知练习：把二进制数100101(2)化为十进制数.543210100101(2)=1X2+0X2+0X2+1X2+0X2+1X2=37讨论：怎样把十进制数89化为二进制数？例1:把十进制数89化为二进制数.观察下面的算式你有什么发现吗？89=2X(2X(2X(2X(2X2+1)+1)+0)+0)+1=1X26+0X25+1X24+1X23+0X22+0X21+1X2=1011001(2).根据二进制“满二进一”的原则，可以用2连续去除89所得商，然后取余数.这样化十进制数为二进制数的算法叫做除2取余法.练习：把十进制数196化为五进制数除二取余法也可以推广为把十进制数化为k进制数的算法，称为除k取余法.即用5连续去除196或所得商，然后取余数.196=1241(5)推广：怎样把十进制数转化为k进制数？若十进制数a除以k所得的商是q。，余数是r0即a=kq0+r0;q0除以k所得的商是q1，余数是r1,即qo=kqi+r1;qn-1除以k所得的商是0,余数是rn,即qn-1=rn,那么十进制数a化为k进制数是：3=佔丄nr。k例2:根据上面的分析，将十进制数a化为二进制数的算法步骤如何设计？第一步，输入十进制数a的值.第二步，求出a除以2所得的商q，余数r.第三步，把所得的余数依次从右到左排列第四步，若0，贝Ua=q,返回第二步；否则，输出全部余数r排列得到的二进制数练习：设计一个程序，实现“除k取余法”(kN,2Wkw9).第一步，输入十进制数a的值和基数k的值.第二步，求出a除以k所得的商q,余数r.第三步，把所得的余数依次从右到左排列第四步，若0，贝Ua=q,返回第二步；否则，输出全部余数r排列得到的二进制数fNPUTa,kb=0i=0DOq=akr=aMODkAb=b+r*10ii=i+1a=qLOOPUNTILq=0PRINTbEND(三) 讲练结合，巩固提高练习1将十进制数258分别转化为四进制数和六进制数258=10002（4）=1110（6）练习2将五进制数1234（5）转化为七进制数.1234（5）=365（7）四）小结1、进位制的概念及转化方法.2、通过k进制数与十进制数的相互转化，实现计算机操作五）布置作业：P45练习：3.P48习题1.3A组：3、4.