13.1辗转相除法与更相减损术(精)

•1. 3算法案例第1课时極特相除法与更相濒损术* T «• ** T • -t * * 1 « *KQZZYX课前自主预习• 1.用两数中较人的数减去较小的数, 再用所得差和较小数构成新的一对数，再用______ ^减______ ;数以同样的操作一直做下去，直到所得的两数相等为止，这个数就是这两个数的最大公约数.这个方法称作“更相减损术”，用它编写的算法称作“等值算法”・• 2.古希腊求两个正整数的最大公约数的方法是辗转相除法：用较大数除以较小数所得的余数和较小数构成新的一对数，继续做上面的除法，直到大数被小数除尽, 这个较小的数就是最大公约数.据此编写的算法，也称作“欧几里得算法” •3・对于正整数加与n(m>n),总能找到整数g 和r(O<r<n)使得m=nq+rf^立，这个除法称为带余除法.通常记r=mMODn.ZDNDZS 重点难点展示•重点：算法案例的原理、算法设计及算法思想的体会.•难点：理解算法案例的内容及具体算法设计的关键步骤.XXYDDB学习要点点拨• 一、弄清算法原理，掌握算法程序，经历蠶翳■，聶’体会算法设计的关键环节,• 1 •辗转相除法•(1)辗转相除的原理：・设zn, 〃是两个整数(不妨设m>ri),用加除以〃，若商为务, 余数为厂1(00］<小则m = n・牛+厂1，显然若兀是加和〃的公约数，即x能整除加和弘贝吹也必然能整除厂1，这样x也是〃和厂］的公约数，故求加和〃的公约数就是求〃和厂1的公约数；同理，用〃除以厂1，得n = r x -^2 + ^(0<^<^),故求加和斤的公约数就是求厂2和厂1的公约薮，…，依次下去，由于加>〃>厂］>厂2>…，所以到某一步必然有r z = r/+19q汁"即耳恰能被厂计］整除，这时耳+1是耳和厂j+1的最关公约数，它也必然是耳_1和乙、厂—2和耳_1、…、厂1与厂2、〃和厂2、加和〃的最大公约数.• (2)辗转相除法的算法分析:•由以上辗转相除法的原理可以发现，辗转相除法的基本步骤是用较大的数除以较小的数，考虑到算法中的赋值语句可以对同一变量多次赋值，我们可以把较大的数用变量加表示，把较小的数用变量〃表示，这样式子m = n -q + r(O<r<^)就是一个反复执行的步骤，因此可以用循环结构实现算法.如图.• (3)用辗转相除法求任意两个正整数最大公约数的程序框图. •由于辗转相除法总是用较大的数去除以较小的数，所以首先要对一开始给定的两数的大小进行判断，并将大数赋给加，小数赋给弘然后再执行下面的过程.程序框图如图.（开始）*/输入a，bt 二a 仃二I)b=tEND IF丁二 1WHILE r< >0 「二a MOD b a = b b -rWENDPRINT aEND•2.更相减损术•（1）更相减损术求两数最大公约数的过程与算法设计.•对于给定的两个数，用较大的数减去较小的数，接着把得到的差与较小的数比较，用这时两个数中较大的数减去较小的数，继续这样的操作（夭数减小藪：），直到所得的数相等为止，那么这个数（相等数）就是所求的最大公约数.•显然，上述过程中大数减去小数是一个重复执行的过程，因此只需将大数赋给变量a,小数赋给变量b,那么就可以通过循环结构实现算法.或当时，将d —b赋给b = b,当xb 时，a=a,将赋给b然后再进行比较，依次类推用循环结构实现.•⑵更相减损术求最大公约数的程序设计女口T：•请自行将其直到型循环结构算法写岀来. • 3 •辗转相除法与更相减损术有着相同的算法依据，但要注意运算过程的差别，辗转相除法的上一次运算的除数和余数分别作为下一次运算的被除数和除数，其结果直至余数为零得出.更相减损术在上一次运算结束后，比较减数和差的大小，将大的作为下一次运算的被减数，小的作为减数，直至岀现相等数时得到结果.•由此可见，二者算法是相似的.主要区别在于，辗转相除法进行的是除法运算，即辗转相除，更相减损术进行的是减法运算, 即辗转相减，但其实质都是一个不断的递归过程.另外两者在算法设计上有一个重要的区别点，辗转相除法，下一次进行相除时，由上一次的除数和余数直接相除即可.而更相减损术下一次相减前必须有一个判断大小的过程，以区别谁做被减数.这些内容都是应特别注意的关键环节.• 4.用更相减损术求两正整数的最大公约数时，若两数为偶数，可先约去2,这时莫忘记求得的相等两数乘以约简的数才是所求最夫公约薮.STYYLX 随堂应用练习•一、填空题•1.在对16和12求最大公约数时，整个操作如下：(16,12)—- (4,12)—- (4,8)—-(4,4),由匕可以看出12和16的最大公约数是•［答案］4• 2. 1443与999的最大公约数是_________ •［答案］111•［解析］• (999,1443)——(999,444)——(555,444)一-> (111,444)一一(111,333)—一(111,222)一->( 111,111)•或1443 ・ 999 = 444,999 - 444 = 555,555 - 444 = 111,444 - 111 = 333,333 - 111 = 222,222 - 111 = 111.•自己用辗转相除法写出解答过程.• 3.运算速度快是计算机一个很重要的特点，而算法好坏的一个重要标志是■•［答案］运算次数• 4. 2004与4509的最大公约数为167.・・ 2004 = 22 x3 x 167.450915()3501167•［答案］5012004 2 1002 2 501 3•「.4509 = 33x167 , •••2004与4509的最大公约数为3x167 = 501.•自己用辗转相除法和更相减损术写出解答.•二、解答题• 5.写出从键盘任意输入两个正整数a, b, 输出这两个数的最小公倍数的算法，画出程序框图，写出算法语句.［解析］约数匕程序框图如右图.程序为：INPUT “正整数°, b = p=a*bIF a<b THENEND IFDO从键盘输入两数Q, 再计算两数的最小公倍数b后，先求两数的最大公a-b亠人tP~~k，输出P即可.r/ 输* a,b 7。

第一课时 1.3.1 算法案例---辗转相除法与更相减损术教学要求：理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析； 基本能根据算法语句与程序框图的知识设计出辗转相除法与更相减损术完整的程序框图并写出它们的算法程序.教学重点：理解辗转相除法与更相减损术求最大公约数的方法.教学难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.教学过程：一、复习准备：1. 回顾算法的三种表述：自然语言、程序框图（三种逻辑结构）、程序语言（五种基本语句）.2. 提问：①小学学过的求两个数最大公约数的方法？（先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.）口算出36和64的最大公约数. ②除了用这种方法外还有没有其它方法？6436128=⨯+ ，36∴和28的最大公约数就是64和36的最大公约数，反复进行这个步骤，直至842=⨯，得出4即是36和64的最大公约数.二、讲授新课：1. 教学辗转相除法：例1：求两个正数1424和801的最大公约数.分析：可以利用除法将大数化小，然后逐步找出两数的最大公约数. （适用于两数较大时） ①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的. 利用辗转相除法求最大公约数的步骤如下：（1）用较大的数m 除以较小的数n 得到一个商0S 和一个余数0R ；（2）若0R ＝0，则n 为m ，n的最大公约数；若0R ≠0，则用除数n 除以余数0R 得到一个商1S 和一个余数1R ；（3）若1R ＝0，则1R 为m ，n 的最大公约数；若1R ≠0，则用除数0R 除以余数1R 得到一个商2S 和一个余数2R ；……依次计算直至n R ＝0，此时所得到的1n R -即为所求的最大公约数.②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定，所以我们可以把它看成一个循环体，它的程序框图如右图：（师生共析，写出辗转相除法完整的程序框图和程序语言）练习：求两个正数8251和2146的最大公约数. （乘法格式、除法格式）2. 教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：（1）任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数. 例2：用更相减损术求91和49的最大公约数.分析：更相减损术是利用减法将大数化小，直到所得数相等时，这个数（等数）就是所求的最大公约数. （反思：辗转相除法与更相减损术是否存在相通的地方）练习：用更相减损术求72和168的最大公约数.3. 小结：辗转相除法与更相减损术及比较①都是求最大公约数的方法，辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少；②结果上，辗转相除法体现结果是以相除余数为0得到，而更相减损术则以减数与差相等而得到.三、巩固练习：1、练习：教材P35第1题 2、作业：教材P38第1题第二课时 1.3.2 算法案例---秦九韶算法教学要求：了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数、提高计算效率的实质；理解数学算法与计算机算法的区别，理解计算机对数学的辅助作用. 教学重点：秦九韶算法的特点及其程序设计.教学难点：秦九韶算法的先进性理解及其程序设计.教学过程：一、复习准备：1. 分别用辗转相除法和更相减损术求出两个正数623和1513的最大公约数.2. 设计一个求多项式5432()254367f x x x x x x =--+-+当5x =时的值的算法. （学生自己提出一般的解决方案：将5x =代入多项式进行计算即可）提问：上述算法在计算时共用了多少次乘法运算？多少次加法运算？此方案有何优缺点？(上述算法一共做了5＋4＋3＋2＋1＝15次乘法运算，5次加法运算. 优点是简单、易懂；缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高.)二、讲授新课：1. 教学秦九韶算法：① 提问：在计算x 的幂值时，可以利用前面的计算结果，以减少计算量，即先计算2x ，然后依次计算2x x ⋅，2()x x x ⋅⋅，2(())x x x x ⋅⋅⋅的值，这样计算上述多项式的值，一共需要多少次乘法，多少次加法?（上述算法一共做了4次乘法运算，5次加法运算）② 结论：第二种做法与第一种做法相比，乘法的运算次数减少了，因而能提高运算效率，而且对于计算机来说，做一次乘法所需的运算时间比做一次加法要长得多，因此第二种做法能更快地得到结果.③ 更有效的一种算法是：将多项式变形为：5432()254367((((25)4)3)6)7f x x x x x x x x x x x =--+-+=--+-+，依次计算2555⨯-=，55421⨯-=，2153108⨯+=，10856534⨯-=，534572677⨯+= 故(5)2677f =. ――这种算法就是“秦九韶算法”. （注意变形，强调格式）④ 练习：用秦九韶算法求多项式432()2351f x x x x x =+-++当4x =时的值. （学生板书→师生共评→教师提问：上述算法共需多少次乘法运算？多少次加法运算？）⑤ 如何用秦九韶算法完成一般多项式1110()n n n n f x a x a x a x a --=++++ 的求值问题？改写：11101210()(()))n n n n n n n f x a x a x a x a a x a x a x a x a ----=++++=+++++ .首先计算最内层括号内一次多项式的值，即11n n v a x a -=+，然后由内向外逐层计算一次多项式的值，即212n v v x a -=+，323n v v x a -=+， ，10n n v v x a -=+.⑥ 结论：秦九韶算法将求n 次多项式的值转化为求n 个一次多项式的值，整个过程只需n 次乘法运算和n 次加法运算；观察上述n 个一次式，可发出k v 的计算要用到1k v -的值，若令0n v a =，可得到下列递推公式：01,(1,2,,)n kk n k v a v v x a k n --=⎧⎨=+=⎩ . 这是一个反复执行的步骤，因此可用循环结构来实现.⑦ 练习：用秦九韶算法求多项式5432()52 3.5 2.6 1.70.8f x x x x x x =++-+-当5x =时的值并画出程序框图.2. 小结：秦九韶算法的特点及其程序设计三、巩固练习：1、练习：教材P35第2题 2、作业：教材P36第2题第三课时 1.3.3 算法案例---进位制教学要求：了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换；学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k 去余法，并理解其中的数学规律.教学重点：各种进位制之间的互化.教学难点：除k 取余法的理解以及各进位制之间转换的程序框图及其程序的设计. 教学过程：一、复习准备：1. 试用秦九韶算法求多项式52()42f x x x =-+当3x =时的值，分析此过程共需多少次乘法运算？多少次加法运算？2. 提问：生活中我们常见的数字都是十进制的，但是并不是生活中的每一种数字都是十进制的.比如时间和角度的单位用六十进位制,电子计算机用的是二进制，旧式的秤是十六进制的，计算一打数值时是12进制的......那么什么是进位制？不同的进位制之间又有什么联系呢？二、讲授新课：1. 教学进位制的概念：① 进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几. 如：“满十进一”就是十进制，“满二进一”就是二进制 . 同一个数可以用不同的进位制来表示，比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的. 表示各种进位制数一般在数字右下脚加注来表示，如上例中：(2)(8)(16)1110017139==② 一般地，任意一个k 进制数都可以表示成不同位上数字与基数的幂的乘积之和的形式，即110110()110110...(0,0,...,,)n n n n k n n n n a a a a a k a a a k a k a ka k a k ----<<≤<=⨯+⨯+⨯+⨯ . 如：把(2)110011化为十进制数，(2)110011=1⨯25+1⨯24+0⨯23+0⨯22+1⨯21+1⨯20=32+16+2+1=51. 把八进制数(8)7348化为十进制数，3210(8)7348783848883816=⨯+⨯+⨯+⨯=.2. 教学进位制之间的互化：①例1：把二进制数(2)1001101化为十进制数.（学生板书→教师点评→师生共同总结将非十进制转为十进制数的方法）分析此过程的算法过程，编写过程的程序语言. 见P34②练习：将(5)2341、(3)121转化成十进制数.③例2、把89化为二进制数.分析：根据进位制的定义，二进制就是“满二进一”，可以用2连续去除89或所得商，然后取余数. （教师板书）上述方法也可以推广为把十进制化为k 进制数的算法,这种算法成为除k 取余法. ④练习：用除k 取余法将89化为四进制数、六进制数.⑤例3、把二进制数(2)11011.101化为十进制数.解：43210123(2)11011.101121202121212021227.625---=⨯+⨯+⨯+⨯+⨯+⨯+⨯+⨯=.（小数也可利用上述方法化进行不同进位制之间的互化. ）变式：化为八进制→方法：进制互化3. 小结：进位制的定义；进位制之间的互化.三、巩固练习：1、练习：教材P35第3题 2、作业：教材P38第3题第四课时 1.3.4 生活中的算法实例教学要求：通过生活实例进一步了解算法思想.教学重点：生活实例的算法分析.教学难点：算法思想的理解.教学过程：一、复习准备：1. 前面学习了哪几种算法案例？每种算法的作用及操作方法是怎样的？2. 算法思想在我们的生活中无处不在，如何利用我们所学习的知识解决生活中的实际问题？二、讲授新课：1. 霍奇森算法：提问：同学们经常会面对一个共同的问题，就是有时有太多的事情要做. 例如，你可能要面临好几门课的作业的最后期限，你如何合理安排以确保每门课的作业都能如期完成？如果根本不可能全部按期完成，你该怎么办？（霍奇森算法可以使得迟交作业的数目减到最小. 这一算法已经广泛应用于工业生产安排的实践中.）例如：当你拿到下面这组数据后，你会如何安排你的时间，以确保每门课的作业都能如期完成？可用自然语言描述为：①把这些作业按到期日的顺序从左到右排列，从最早到期的到最晚到期的；②假设从左到右一项一项做这些作业的话，计算出从开始到完成某一项作业时所花的时间. 依次做此计算直到完成了所列表中的全部作业而没有一项作业会超期，停止；或你算出某项作业将会超期，继续第三步；③考虑第一项将会超期的作业以及它左边的所有作业，从中取出花费时间最长的那项作业，并把它从表中去掉；④回到第二步，并重复第二到四步，直到做完.2. 孙子问题：韩信是秦末汉初的著名军事家. 据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场，刘邦问韩信有什么办法，不要逐个报数，就能知道场上士兵的人数.韩信先令士兵排成了3列纵队进行操练，结果有2人多余；接着他立刻下令将队形改为5列纵 队，这一改又多出3人；随后他又下令改为7列纵队，这一次又剩下2人无法成整行. 由此得出共有士兵2333人. 如何用现在的算法思想分析这一过程？《孙子算经》中给出了它的具体解法，其步骤是：选定57⨯的倍数，被3除余1，即70；选定37⨯的一个倍数，被5除余1，即21；选定35⨯的一个倍数，被7除余1，即15. 然后按下式计算702213152105m p =⨯+⨯+⨯-，式中105为3,5,7的最小公倍数，p 为适当的整数，使得0105m <≤，这里取2p =.求解“孙子问题”的一种普通算法：第一步：2m =.第二步：若m 除以3余2，则执行第三步；否则1m m =+，执行第二步.第三步：若m 除以5余3，则执行第四步；否则1m m =+，执行第二步.第四步：若m 除以7余2，则执行第五步；否则1m m =+，执行第二步.第五步：输出m .3. 小结：算法的基本思想.三、巩固练习： 作业：教材P38第3题。

高中数学知识点总结 第 1 页 共 1 页 高中数学知识点总结：辗转相除法与更相减损术
辗转相除法与更相减损术
1、辗转相除法。

也叫欧几里德算法，用辗转相除法求最大公约数的步骤如下：
（1）：用较大的数m 除以较小的数n 得到一个商
0S 和一个余数0R ；（2）：若0R ＝0，则n 为m ，n 的最大公约数；若
0R ≠0，则用除数n 除以余数0R 得到一个商1S 和一个余数1R ；（3）：若
1R ＝0，则1R 为m ，n 的最大公约数；若1R ≠0，则用除数0R 除以余数1R 得到一个商2S 和一个余数2R ；…… 依次计算直至n R ＝0，此时所得到的1n R 即为所求的最大公约数。

2、更相减损术
我国早期也有求最大公约数问题的算法，就是更相减损术。

在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之。

翻译为：（1）：任意给出两个正数；判断它们是否都是偶数。

若是，用2约简；若不是，执行第二步。

（2）：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。

继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。

例2 用更相减损术求98与63的最大公约数.
分析：（略）
3、辗转相除法与更相减损术的区别：
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

辗转相除法与更相减损术 已知a、b求a与b的最⼤公因数与最⼩公倍数？先说最⼤公因数 我们先把a、b改写成多个素数的幂相乘。

⽐如a=36和b=54，那么a=2^2*3^2，b=2^1*3^3。

根据定义最⼤公因数就是取a、b分解出的相同素数的最⼩指数相乘，即2^1*3^2=18。

辗转相除法就是⽤a、b中的⼤数对⼩数取余，再把余数和⼩数中的较⼩数取余，⼀直这样做，直到刚好整除，余数为0。

⽐如36与54，先算54%36=18，再算36%18=0，结束，这⾥的18即为所求。

　int gcd(int x,int y){if(x%y==0)return y;elsereturn zhanzhuan(y,x%y);} 然后是更相减损术。

⼀种实现是把a、b中的⼤数减⼩数，然后把⼩数与差中的⼤数减⼩数，直到减到减数和差⼀样，此时的差即为所求。

⽐如36与54，先算54-36=18，再算36-18=18，此时18=18,18就是最⼤公因数了。

int gcd(int a,int b){while(a!=b){if(a>b)a=a-b;if(a<b)b=b-a;}return a;}以上两种算法复杂度略⽞学，有时快有时慢的……这⾥还有⼀种更相减损术的代码，复杂度是log级别的。

int gcd(int a,int b){int F=1;while(a!=b){if(a<b)swap(a,b);if(a&1)if(b&1)a-=b;else b/=2;elseif(b&1)a/=2;else a/=2,b/=2,F*=2;}return a*F;}因为当a、b为奇数时相减，得到偶数，然后执⾏其他三个操作。

也就是说每执⾏两步操作，必然除掉了⼀个2。

然后再说最⼩公倍数。

⼀种正常的算法是把a、b改写成多个素数的幂相乘。

⽐如a=36和b=54，那么a=2^2*3^2，b=2^1*3^3。

长江中学高二数学导学案二十六班级：组别：姓名：编写人：周智勇审核人：龙子勇时间：2017年11月7<<1.3.1辗转相除法与更相减损术>>导学案学习目标：1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。

2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。

3. 在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。

4.通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。

在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。

【重点】辗转相除法和更相减损术的算法思想【难点】根据辗转相除法和更相减损术设计算法程序学习过程：【自主学习】1．辗转相除法：古希腊求两个正整数的最大公约数的方法是 ______ ：用______除以______所得______和较小的数构成新的一对数，继续做上面的除法，直到大数被小数除尽，这个较小的数就是最大公约数。

2．辗转相除法的基本步骤是用较大的数除以较小的数，若把较大的数用变量a表示，把较小的数用变量b表示，则可反复执行式子 ______ 实现循环结构的算法。

3．更相减损术：用两数中______ 减去______，再用______和______ 构成新的一对数，再用______减______，以同样的操作一直做下去，直到所得的两数______为止。

4. 更相减损术算法中，若把大数赋给a，小数赋给b，则当a﹥b时，将______ 赋给 a，b=b;当a﹤b时，a=a,将______ 赋给b，然后再进行比较，依次类推用循环结构实现。

【合作探究】探究1 用辗转相除法求两个正数8251和6105的最大公约数，画出程序框图并把它编成一个计算机程序。