2019-2020年高中数学5.4.2《算法案例2》教案苏教版必修3

1、2019-2020年高中数学542算法案例2教案苏教版必修 3重点难点重点：通过案例分析理解辗转相除法与更相减损术求最大公约数的方法，体会算法思想.难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言学习要求1 理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析2基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序【课堂互动】问题：写出求两个正整数 a,b（a>b）的最大公约数的一个算法。1. 辗转相除法公元前3世纪，欧几里得介绍了求两个正整数 a,b（a>b）的最大公约数的方法，求出一列数： 这列数从第三项开始，每一项都是前两项相除所得

2、的余数（即），余数等于0的前一项，即是a和b的最大公约数，这种方法称为“欧几里得辗转相除法”。例1 求两个正数8 251和6 105的最大公约数.（分析：8 251与6 105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根 据已有的知识即可求出最大公约数）【解】8 251 = 6 105 X 1+ 2 146显然8 251和的2 146最大公约数也必是 2 146的约数，同样6 105与2 146的公约数也 必是8 251的约数，所以8 251与6 105的最大公约数也是 6 105与2 146的最大公约数.6 105 = 2146X 2 + 18132 146 = 1813X

3、1 + 3331 813 = 333 X 5+ 148333 = 148 X 2+ 37148 = 37 X 4 + 0则37为8 251与6 105的最大公约数.【小结】以上我们求最大公约数的方法就是欧几里得辗转相除法其求最大公约数的步骤如下：第一步：用较大的数除以较小的数，得到一个商和一个余数；第二步：若，则为的最大公约数；若，则用除数除以余数，得到一个商和一个余数；第三步：若，则为的最大公约数；若，则用除数除以余数得到一个商和一个余数；依次计算直至，此时所得到的即为所求的最大公约数【练习】求a=204, b=85的最大公约数，步骤为：51 204 - 85的余数为34,52 85十34的

4、余数为17,53 34 - 17的余数为0。所以它们的最大公约数为17。算法描述：计算出a十b的余数r，若r=0 ,则b为a, b的最大公约数；若r丰0，则把前 面的除数b作为新的被除数，把余数 r作为新的除数（a, b要重新赋值，a b, b Jr）,继续 进行上述运算，直到余数为 0（用While循环语句，循环的执行条件是 工0，当r=0时，循环 终止），此时的除数即为所求的最大公约数。算法如下：S1输入两个正整数 a,b（a>b）；S2 若 Mod(a, b)=0，则转 S3;否则，r Mod(a,b) , a b, b r，转 S2。S3输出最大公约数b.【流程图】开始 ：. 输

5、出b输入a,结束一:'【伪代码】i Read a,b:While Mod(a,b)工 0 r Mod(a,b)Ia bb rEnd WhileI:Print b2. 更相减损法我国早期也有解决求最大公约数问题的算法，就是更相减损术.副置分母之数，以少减多,2约简；若不是，执行第更相减损术求最大公约数的步骤如下：可半者半之，不可半者,更相减损，求其等也，以等数约之.翻译出来为：第一步：任意给出两个正数 ，判断它们是否都是偶数若是，用 二步.第二步：以较大的数减去较小的数， 接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数(等数)就是所求的最大公约

6、数.再从这个角度看一下"求 a=204, b=85的最大公约数”的问题，S1步可以等价为等式：。S2步可以等价为等式：。这两步从减法的角度可以理解为：204-85，所得的差与减式中的较小数比较，再用大的数减小的数，循环执行以上步骤，直到结果为0。此时减数就是 a和b的最大公约数。这一算法根据它的特点，也可以用循环语句完成。参考代码：/a放较大的数，"b放较小的数 If a < b The n'm a a b；b m / 交换a, b中的数End If / 确保a是a, b中较大的数/ r a - b / 两数相减；While r 工 0 If b > r

7、 The n a b b r:Elsea r；End Ifr a - b/ /确保相减后仍用较大的数减去较小的数:End WhilePrint b”用“更相减损法”求多于两个数的最大公约数就可以显示出其优越性【小结】比较辗转相除法与更相减损术的区别(1) 都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计 算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较 明显.(2) 从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则 以减数与差相等而得到.【追踪训练】1. 分析下面一段代码的目的：Read m,nWhile

8、m/n 丰 Int(m/n)c m- I nt(m/n)x nm nn cEnd WhilePrint n(Int(x)表示不超过x的最大整数)【解】 求m, n的最大公约数。2. 用辗转相除法求下列各组数的最大公约数。(1) 225,135;(2) 98,196.3. 用更相减损法求下列各组数的最大公约数。 （31）72,168; （ 2）153,119.4. 现有长度为360cm和780cm两种规格的钢筋若干要焊接一批正方形模型问：怎样才能保 证正方体体积最大且不浪费 ?思路点拨 ： 正方体的所有棱长都相等 , 故必须将钢筋剪裁成长度相等的钢筋条 ;又必须不浪费 , 这就说明必须剪后无剩余

9、 . 于是为了保证正方体的体积最大 , 故剪的钢筋的最大长度为 360cm 和780cm的最大公约数，可用更相减损术求最大公约数 .第 11 课时算法案例 （2）分层训练1、阅读下列代码，写出该代码的运行结果t 1 n 3 s 0While s<10 t t x ns J s+tEnd WhilePrint s答：2、设计一个计算1X 3x 5X 7X 9的算法.下面给出了程序的 面数据中的（）S II 3While I< S Sx II 1+2End WhilePrint S部分，则在横线上不能填入下A. 9 B . 9. 5 C . 10 D . 10.53、 下列一段伪代码执

10、行结束后S的目的是（）S 0a lFor I From l To 4a 2aS S+aEnd ForA.计算 2+22+23+24 B .计算 2+22+23 C .计算 234. 先用不同的算法计算1，再比较其优劣。1 22 3 3 499 100D.计算245.已知 ABC中，试写出作 ABC的一个算法。2x 46.用条件语句表示：输入x的值，通过、二.x 224x (-：，-2X，(-2,2)计算y的值。x 2,7.写出求中最大数的一个算法。8、一球从100m高度落下，每次落地后反弹回原高度的一半，再落下，在第十次落地时，共 经过多少路程？第十次下落多高？思考运用9.我国古代劳动人民对不

11、定方程的研究作出过重要贡献，其中张丘建算经中的百鸡 问题就是一个很有影响力的问题：“今有鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。凡百钱买百鸡，问鸡翁、母、雏各几何？”其意思是：一只公鸡的价钱是五钱，一只母鸡的价钱是三钱，三只小鸡的价钱是一钱。 现在用一百钱买一百鸡，可以买公鸡、母鸡、小鸡各几个？这是一个不定方程的整数解问题，假设公鸡x只，母鸡y只，小鸡z只，首先，可以大致得到x在1至20之间，y在1至33之间，z=100-x-y 可以确定。根据上述算法思想，画出求解的流程图，并写出相应的伪代码。2019-2020年高中数学6.1.2系统抽样教案苏教版必修3学习要求1 体会系统抽样的的概念及如

12、何用系统抽样获取样本；2 感受系统抽样也是等可能性抽样，是否需要用系统抽样，主要是看总体个数的多少【课堂互动】 自学评价案例1某校高一年级有20个班，每班有50名学生为了了解高一学生的视力状况，从 这1000人中抽取一个容量为 100的样本进行检查，应该怎样抽样 ？【分析】这个案例的总体中个体数较多，生活中还有容量大的多的总体，面对这样的总体，采用 抽签或随机数表等简单随机抽样方法是不科学的抽取样本最关键的就是要保证抽样过程的 公平性，要保证总体中每个个体被抽到的机会均等在这样的前提下，我们可以寻求更好的 抽样方法.系统抽样以简单随机抽样为基础，通过将较大容量的总体分组，只需在某一个组内用简

13、单随机抽样方式来获取一个个体，然后在一定规则下就能抽取出全部样本1.系统抽样系统抽样的概念：将总体平均分成几个部分，然后按照一定的规则，从每个部分中抽取 一个个体作为样本，这样的抽样方法称为系统抽样(systematic sampli ng)系统抽样的步骤为：(1) 采用随机的方式将总体中的个体编号;(2) 将整个的编号按一定的间隔 (设为k)分段，当 N/n (N 为总体中的个体数，n为样本容量)是整数时， k=N/n ; 当 N/n 不是整数时，从总体中易V除一些个体，使剩下的总体中个体的个数N能被n整除，这时，k=N /n并将剩下的总体重新编号；(3) 在第一段中用简单随机抽样确定起始的

14、个体编号L;（4）将编号为L, L+k,L+2k,丄+（n-1）k 的个体抽出.【小结】系统抽样是以简单随机抽样为基础的一种抽样方法，对于容量较大、个体差异不明 显的总体通常采用这种抽样方法，在保证公平客观的前提下简化抽样过程在用系统抽样方 法抽取样本时，如果总体个数不能被样本容量整除，可以从总体总体中的个体的个数能被样本容量整除【经典范例】例1在1 000个有机会中奖的号码（编号为000999）中，在公证部门监督下随机抽取的方 法确定后两位数为 88的号码为中奖号码，这是运用哪种抽样方法来确定中奖号码的？依次写 出这10个中奖号码？【解】本题中是运用了系统抽样的方法来确定中奖号码的，中奖号码

15、依次为： 088,188,288,388,488,588,688,788,888,988例2某单位在岗职工共 624人，为了调查工人用于上班途中的时间，决定抽取10%勺工人进行调查试采用系统抽样方法抽取所需的样本【分析】因为624的10%勺为62, 624不能被62整除，为了保证“等距”分段，应剔除 4人.【解】 第一步 将624名职工用随机方式进行编号；第二步 从总体中剔除4人（剔除方法可用随机数表法），将剩下的620名职工重新编号 （分别为000, 001, 002,619）,并分成62段；第三步 在第一段000,009这十个编号中用简单随机抽样确定起始号码i。；第四步 将编号为io, i

16、o+10,i 0+610的个体抽出，组成样本.例3某制罐厂每小时生产易拉罐 10 000个，每天生产时间为12h,为了保证产品的合格率， 每隔一段时间要抽取一个易拉罐送检,工厂规定每天共抽取1 200个进行检测，请你设计一个抽样方案。【解】每天共生产易拉罐 120 000个，共抽取1200个，所以分1200组，每组100个，然后 采用简单随机抽样法从 001100中随机选出一个编号，例如选出的是013号，则从第13个易拉罐开始，每隔 100个，拿出一个送检，或者根据每小时生产10 000个，每隔s拿出个易拉罐送检。例4现要从999名报名者中随机选取100名参加某活动，请你用系统抽样法设计一种方

17、案， 叙述其步骤。你能找到另外的抽样方案吗？比较两种方案的合理性和易操作性【解】按系统抽样法，因为100不能整除999,所以首先将999人编号，采用随机数表法剔除99名，再将剩下的900名报名者重新编号 001900,从001号顺次下去每9人一组，等分成 100组，利用抽签法或随机数表法，从19个数中随机选出一个数，新编号为该数字加上9的倍数的报名者入选。例如选出的随机数为3,则新编号为003,012,021，894共100人入选。还可以采取以下抽样方法： 首先将999名报名者编号为001999，因为111可以整除999, 将这999个编号从001开始顺次每9个一组，然后选用简单随机抽样法从1

18、9的9个数字中随机地抽出一个数字，编号为该数字加上9的倍数的共111名报名者先挑选出来，例如：随机抽到的是 乙则编号为007,016,025，,988,997共111名，最后，再利用随机数表从111名中随机抽取11名剔除。点评：此方法较之系统抽样法更易操作，因为虽然999不能被100整除，但余数99非常大，接近于除数100,而且采用随机数表法从 999个数字中随机抽出 99个数剔除的工作量也较大。 后一种方法先通过系统抽样，随机抽取111名，再利用随机数表法，从 111个数字中随机抽 出11个来剔除，操作起来要相对方便得多。追踪训练I1 为了了解参加一次知识竞赛的1 252名学生的成绩，决定采

19、用系统抽样的方法抽取一个容量为50的样本，那么总体中应随机剔除个体的数目是（A ）（A 2（ B）3（C） 4（ D） 52全班有50位同学，需要从中选取 7人，若采用系统抽样的方法来选取，则每位同学能被 选取的可能性是3. 个总体中有100个个体，随机编号为 0,1,2,99,依编号顺序平均分成10个小组，组号依次为1,2,3, . ,10 .现用系统抽样的方法抽取一个容量为10的样本，规定如果在第一组随机抽取的号码为，那么在第组中抽取的号码个位数字与的个位数字相同.若，则在第7组中抽取的号码是 63.4. 要从1003名学生中选取一个容量为20的样本，试叙述系统抽样的步骤。【解】第一步 将

20、1003名学生有随机方式进行编号；第二步 从总体中剔除3人（剔除方法可用随机数表法 ），将剩下的1000名学生重新编 号并分成20段；第三步 在第一段000、001、002、003、049这十个编号中用简单随机抽样确定起 始号码，比如013第四步 将013逐次加上部分的“长度”（第一部分中个体的个数）的0倍、1倍、2倍、 19 倍得到样本:013、063、113、163、963.第 2 课时 6.1.2 系统抽样分层训练1为了解高三学生身体状况，某学校将高三每个班学号的个位数为1 的学生选作代表进行调查体检，这种抽样方法称为 ( )(A) 系统抽样 (B) 抽签法(C) 简单随机抽样 (D) 随机数表法2系统抽样适用的范围是( )(A) 总体中个数较少 (B) 总体中个数较多 (C) 总体由差异明显的几部分组成(D) 以上均可以3要从已编号(150)的50辆新生产的赛车中随机抽取5辆进行检验，用系统抽样方法确定所选取的 5 辆赛车的编