课标人教A版必修3全套第一章算法案例

人教A版高中数学必修3多思、创新、融合1可编辑ppt2可编辑ppt复习回顾基本结构流程图顺序结构变量与赋值循环结构基本语句循环语句条件语句WHILE语句UNTIL语句IF-THEN语句语句适用结构算法条件结构3可编辑ppt我们这节课就利用基本的算法程序来解决一些实际问题，进一步体会算法的程序思想。案例1.辗转相除法与更相减损术4可编辑ppt在初中，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？230391535所以，18和30的最大公约数是：2×3＝6互质因数但是，当我们处理较大数（如：8251与6105）的最大公因数时，如果利用这种方法可能计算量比较大，步骤比较多。下面我们介绍一种古老而有效的算法——辗转相除法5可编辑ppt这种算法是欧几里得公元前300年左右首先提出的，因此又叫欧几里得算法例1求两个正数8251和6105的最大公约数。分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数解8251＝6105×1＋2146显然8251和6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数继续下去，我们得到：欧几里得（公元前330-公元前275）：古希腊数学家，雅典人欧几里得是柏拉图的学生，长期在亚历山大里亚教书。公元前300年左右，代表作《几何原本》13卷问世，创立了著名的欧氏几何，至今仍为中学生必学的一门基础知识。欧几里得对光学也有一定研究。6可编辑ppt6105＝2146×2＋1813

2146＝1813×1＋333

1813＝333×5＋148

333＝148×2＋37

148＝37×4＋0

则37为8251与6105的最大公约数这就是辗转相除法，有除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步骤之后完成你能写出它的算法程序吗？7可编辑ppt利用辗转相除法求最大公约数的步骤如下：第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2第n步：依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数………………8可编辑pptr=mMODnm=nn=rr=o?否是程序图框带余除法INPUT“请输入m，n的值”；m，nIFm>nTHENa=mm=nn=aENDIFDOr=mMODNm=nn=rLOOPUNTILr=0PRINTmEND作用是什么？为什么要用直到型循环结构？9可编辑ppt练一练1.利用辗转相除法求两数4081与20723的最大公约数，写出它的流程框图和BASIC程序10可编辑ppt更相减损术我国早期也有解决求最大公约数问题的算法《九章算术》（公元50年～100年或更早）是中国古代数学专著，承先秦数学发展的源流，进入汉朝后又经许多学者的删补才最后成书，这大约是公元一世纪的下半叶。它的出现，标志着中国古代数学体系的形成。11可编辑ppt历代数学家把它尊为“算经之首”．这是世界上最早的印刷本数学书。

《九章算术》共收有246个数学问题，分为九章。分别是：方田、栗米、衰分、少广、商功、均输、盈不足、方程、勾股。

《九章算术》是世界上最早系统叙述了分数运算的著作；其中盈不足的算法更是一项令人惊奇的创造；“方程”章还在世界数学史上首次阐述了负数及其加减运算法则。12可编辑ppt更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。第三部：继续第二步，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数13可编辑ppt例2用更相减损术求98与63的最大公约数.解由于63不是偶数，把98和63以大数减小数，并辗转相减98-63＝3563-35＝2835-28＝728-7＝1414-7＝7所以，98与63的最大公约数是7两种算法比较，你有什么发现？14可编辑ppt比较辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到15可编辑ppt练习思考一.用辗转相除法求下列各组数的最大公约数，并在自己编写的BASIC程序中验证。

（1）225，135（2）98，196（3）72，168思考二：用更相减损法可否求上述3组数的最大公约数？可否利用更相减损法设计出程序框图及程序？若能，在电脑上测试自己的程序；若不能说明无法实现的理由。思考三：利用辗转相除法是否可以求两数的最大公倍数？试设计程序框图并转换成程序在BASIC中实现。16可编辑ppt案例二（秦九韶算法）怎样求多项式当x=5时的值？据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算我们把多项式变形为：再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果。显然少了6次乘法运算。这种算法就叫秦九韶算法。17可编辑ppt秦九韶（1202--1261年），字道古，安岳县人。其父秦季栖，进士出身，官至工部郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父居中都（今北京），受到名师指导，学习日益增进。及长，随父迁湖州（今浙江吴兴县），在西门外修建住房，由秦九韶设计施工，堂分7间，后为列室，仅中堂1间，纵横7丈，极其宏伟宽敞，显示出他在建筑方面的才能它的一般计算步骤如下：18可编辑ppt把一个多项式改写为：19可编辑ppt求多项式的值时，首先计算最内层括号内的一次多项式的值，即：再有内向外逐层计算一次多项式的值，即：这样将求n次多项式f(x)的值转化为求n个一次多项式的值。20可编辑ppt例3设计利用秦九韶算法计算5次多项式当时的值的程序框图以及BASIC程序。

i=0WHILEi≤5INPUTa[i]WENDDOv=a[5]v=v*x[0]+a[5-n]n=n+1LOOPUNTILn>6END21可编辑ppt用秦九韶算法求这个多项式当时的值。3.已知一个5次多项式为思考：（1）例1计算时需要多少次乘法计算？多少次加法计算？（2）在利用秦九韶算法计算n次多项式当时需要多少次乘法计算和多少次加法计算？练习22可编辑ppt案例3.排序问题你会使用这些字典吗？23可编辑ppt为了便于查询和检索，常常需要根据要求将被查寻的对象按照一定的顺序排列，通常称为排序，你会从这些书籍中查阅你想要的东西吗？24可编辑ppt我们在一个已经排好循序的一系列数中插入一个数据，成为一个新的系列，且仍按原来的规则排序。直接插入排序要将8插入到{1,3,5,7,9,11,13}中，我们怎样考虑？确定8在原系列中的位置，使8小于或等于原系列中右边的数据，大于或等于左边的数据将这个位置空出来，将数据8插进去135791113825可编辑ppt例题分析例3.将数列｛49,38,65,97,76,13,27,49}按小到大的顺序排列我们的想法是：1.先排49，38的顺序：38，492.比较第三个数与它们的大小得到：38，49，653.比较第四个数与2的顺序得到：38，49，65，97n.第n个数与前面数的关系，得到最后的排序：13，27，38，49，49，65，76，97……26可编辑ppt反复使用直接插入排序算法，即首先把第一个数当作一个基准，插入第二个数变成有两个数据的有序列，再插入第三个数，依此类推，就完成了整个无序列的有序化。流程图如下：你会设计它的BASIC算法吗？27可编辑ppt1排序号：数据序号12345678原始数据4938659776132749上述数据我们还可以这样来排序：28可编辑ppt2排序数据序号12345678原始数据4938659776132749现将1号数据49和2号数据38比较，因为49>38所以，49和38的位置互换，变为：数据序号12345678原始数据3849659776132749第一次排序第一步：1号2号排序29可编辑ppt数据序号12345678原始数据3849659776132749第二步：2号3号排序因为49<65所以这俩数的序号不变数据序号12345678原始数据384965977613274930可编辑ppt第三步：比较3、4号数据数据序号12345678原始数据3849659776132749方法同第二步，因为65<97所以数据顺序不变数据序号12345678原始数据384965977613274931可编辑ppt数据序号12345678原始数据3849659776132749数据序号12345678原始数据3849657697132749第四步：比较4、5号数据方法同第一步，因为97>76，所以4、5号数据互换，则：32可编辑ppt第五步：比较5、6号数据：数据序号12345678原始数据3849657697132749数据序号12345678原始数据3849657613972749方法同第二步，97>13则，交换5、6号数据，则：33可编辑ppt第六步：比较6、7号数据数据序号12345678原始数据3849657613972749数据序号12345678原始数据3849657613279749同理，上面的顺序可以变为：同理第七步比较7、8号数据后可以变为：34可编辑ppt这样就完成了第一次排序，它的基本特征是将最大数排到了最右边，然后再从头开始，进行第二次排序，将第二大的数据排到了倒数第二位，反复下去，就可以完成排序。一共要进行7次才能完成。我们叫它冒泡排序（bubblesorting）思考你会用冒泡法将上面的数据按从大到小的顺序排列吗？完成所有的排序需要多少步比较？你还有其他的排序方法将上面的数据按从大到小的顺序排列吗？35可编辑ppt练习请你设计一个数据列为R[1],R[2],…,R[10],要求从小到大的顺序排列？1.画出一次冒泡排序的算法流程图2.画出整个冒泡排序的算法流程图36可编辑ppt一次排序N-1次排完整个排序流程图如图所示37可编辑ppt说明1.冒泡法排序完成n个数据的一次排序需要n-1次比较，完成整个排序需要(n-1)！次比较，对于数据较多时，计算量很大。2.有些数据的冒泡法排序可能用更少的步骤可以完成，后面的步骤可能毫无意义，但计算机必须完成。3.交换数据时注意引入第三方变量。38可编辑ppt案例4.进位制并请这个人算出5个数的和N，在一种游戏中，魔术师请一个人随意想一个三位数把N告诉魔术师，于是魔术师就能说出这个人所想的数现在设N=3194，请你做魔术师，求出数的值将也加到和N上，这样a、b、c就在每一位上都恰好出现两次，所以有分析：①你知道它的原理吗？39可编辑ppt从而3194<222(a+b+c)<3194+1000，而a、b、c是整数所以15≤a+b+c≤18因222

15-3194=136，22216-3194=358，22217-3194=580，22218-3194=802其中只有3+5+8=16能满足①式事实上，这里面应用到了一个知识：进位制40可编辑ppt进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制，等等，也就是说满几进一就是几进制，几进制的基数就是几大于1的整数由于自然数有无限多个，对于每一个自然数如果都用一个独立的名称或符号来读出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一种读数、写数制度--进位制41可编辑ppt十进制数表示实际数值为：K进制数实际表示数为：在日常生活中，我们最熟悉的还是十进制数，据说这和古人曾以手指计数有关为了区别进制，我们就用下标（k）表示k进制数a[n]