范文一:辗转相除法
编辑本段证明
简单的想法
设两数为a 、b(b<a) ,求它们最大公约数(a,b) 的步骤如下:用b 除a ,得a =bq......r 1(0≤r)。若r1=0,则(a,b) =b ;若r1≠0,则再用r1除b ,得b =r1q......r2 (0≤r2).若r2=0,则(a,b) =r1,若r2≠0,则继续用r2除r1,??如此下去,直到能整除为止。其最后一个非零余数即为(a,b) 。
原理及其详细证明
在介绍这个方法之前,先说明整除性的一些特点(下文的所有数都是正整数,不再重覆),我们可以这样给出整除性的定义:
对于二个自然数a 和b ,若存在正整数q ,使a=bq,则a 能被b 整除,b 为a 的因子,a 为b 的倍数。
如果a 能被c 整除,并且b 也能被c 整除,则c 为a 、b 的公因数(公有因数)。
由此我们可以得出以下推论:
推论1、如果a 能被b 整除(a=qb),若k 为正整数,则ka 也能被b 整除(ka=kqb)
推论2、如果a 能被c 整除(a=hc),b 也能被c 整除(b=tc),则(a±b)也能被c 整除
因为:将二式相加:a+b=hc+tc=(h+t)c 同理二式相减:a -b=hc-tc=(h-t)c
所以:(a±b)也能被c 整除
推论3、如果a 能被b 整除(a=qb),b 也能被a 整除(b=ta),则a=b 因为:a=qb b=ta a=qta qt=1 因为q 、t 均为正整数,所以t=q=1 所以:a=b
辗转相除法是用来计算两个数的最大公因数,在数值很大时尤其有用,而且应用在电脑程式上也十分简单。其理论如下:
如果 q 和 r 是 m 除以 n 的商及余数,即 m=nq+r,则
gcd(m,n)=gcd(n,r)。
证明是这样的: 设 a=gcd(m,n),b=gcd(n,r)
证明:
∵a为m,n 的最大公约数,
∴m能被a 整除,且n 也能被a 整除,
∴由推论1得:qn 也能被a 整除,
∴ 由推论2得:m-qn 也能被a 整除,
又 ∵m-qn=r,
∴r也能被a 整除,即a 为n 和r 的公约数(注意:还不是最大公约数) ∵b为n 和r 的最大公约数,a 为n 和r 的公约数 ∴a≤b, 同理 ∵b为n, r的最大公约数, ∴n能被b 整除,且r 也能被b 整除, ∴由推论1得:qn 也能被b 整除, ∴由推论2得:qn+r也能被b 整除, 又∵m=qn+r, ∴m也能被b 整除,即b 为m 和n 的公约数,(注意:还不是最大公约数)
∵a为m,n 的最大公约数,b 为m 和n 的公约数,
∴b≤a,
由以上可知:
a≤b与b≤a同时成立,
故可得
a=b,
证毕。
例如计算 gcd(546, 429)
gcd(546, 429) 546=1*429+117 =gcd(429, 117) 429=3*117+78 =gcd(117, 78) 117=1*78+39 =gcd(78, 39) 78=2*39 =39
编辑本段计算机算法
自然语言描述
辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的:
1. 若 r 是 a ÷ b 的余数, 则
gcd(a,b) = gcd(b,r)
2. a 和其倍数之最大公因子为 a。
另一种写法是:
1. a ÷ b,令r 为所得余数(0≤r<b )
若 r = 0,算法结束;b 即为答案。
2. 互换:置 a←b,b←r,并返回第一步。
流程图
流程图(当型)
伪代码
这个算法可以用递归写成如下:
function gcd(a, b) { if b<>0 return gcd(b, a mod b); else return a; }
c 语言实现
/* 辗转相除法(递归)*/
#include if(n == 0) return m; else return Gcd(n,m%n); } int main(void ) { int m,n; printf("Enter the two figures:"); scanf("%d %d",&m,&n); printf("Gcd:%d\n",Gcd(m,n)); return 0; } 程序: INPUT m,n DO r=mMODn m=n n=r LOOP UNTIL r=0 PRINT m END pascal 实现 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ; 数据举例 其中“a mod b”是指取 a ÷ b 的余数。 例如,123456 和 7890 的最大公因子是 6, 这可由下列步骤看出: a b a mod b 123456 7890 5106 7890 5106 2784 5106 2784 2322 2784 2322 462 2322 462 12 462 12 6 12 6 0 时间复杂度 辗转相除法的运算速度为 O(n2),其中 n 为输入数值的位数。 编辑本段辗转相除法求不定方程的特解 辗转相除法可以求出不定方程的一组整数解。 设不定方程为a x+b y=c,其中a,b,c 为整数且lcm(a,b)|c a,b 辗转相除的算式为 b=q(1) a+r(2) a=q(2) r(2)+r(3) r(2)=q(3) r(3)+r(4) ... r(n-2)=q(n-1)r(n-1)+r(n) r(n-1)=q(n)r(n) 其中r(n)为lcm(a,b),不妨令b=r(0),a=r(1),r(n+1)=0 第i 个算式为 r(i-1)=q(i)r(i)+r(i+1) 所以r(i+1)=r(i-1)-q(i)(ri) (*) 用公式(*)可以得到r(n)=lcm(a,b)关于a,b 的线性组合sa+tb=lcm(a,b) 所以不定方程a x+b y=c的一组特解为 x=sc/lcm(a,b) y=tc/lcm(a,b) 例如: 不定方程为326x+78y=4 求(163,39)的算式为 326=4*78+14 14=326-4*78 78=5*14+8 8=78-5*14 14=1*8+6 6=14-1*8 8=1*6+2 2=8-1*6 6=3*2 所以 2 =8-6=8-(14-8) =2*8-14=2*(78-5*14)-14 =2*78-11*14=2*78-11*(326-4*78) =46*78-11*326 即2=(-11)*326+46*78 所以4=(-22)*326+72*78 所以x=-22,y=72是不定方程326x+78y=4的一组特解 注:q(i),r(i),括号中的是下标,lcm 是求最小公倍数 辗转相除法与更相减损术 一 教材分析 1 教材背景 算法是新课标教材新增加的内容,从古至今算法思想都能在解决问题中得到体现,他不仅是数学及应用的重要组成部分,也是信息技术的重要基础。随着信息技术的发展,算法思想已成为数学素养的一部分, 所以学习算法是非常必要的。 2 本节课的地位及作用 本节课是1.3的第1节课, 这部分的学习是算法语句的综合应用. 二 学情分析 本次课之前学生已经会求一些数的最大公约数了,但是对数字比较大时而且不容易直观的看出它们的因数。辗转相除法可能会让文科学生比较难理解。对于转换成程序框图,学生已经对程序框图比较熟悉,所以这个方面对于学生来说不是什么大问题。 三 重点难点 重点: 理解辗转相除法与更相减损术求最大公约数的方法。 难点: 把辗转相除法与更相减损术的方法转换成程序框图与程序语言。. 四 教学目标 1、知识与技能 (1). 理解辗转相除法与更相减损术中蕴含的数学原理,并能根据这些原理进行算法分析。 (2). 基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。 2、过程与方法 在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法,比较它们在算法上的区别,并从程序的学习中体会数学的严谨,领会数学算法计算机处理的结合方式,初步掌握把数学算法转化成计算机语言的一般步骤。 3、情态与价值 通过阅读中国古代数学中的算法案例,体会中国古代数学对世界数学发展的贡献。 五 课型与教法 课型:新授课 课时:1课时 教法:讲练结合、演示法等 六 教学过程 1课题导入 问题1:求18与30的最大公约数? 问题2:如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求8251与6105的最大公约数? 2研探新知 (一). 辗转相除法 例1 求两个正数8251和6105的最大公约数。 (分析:8251与6105两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据已有的知识即可求出最大公约数) 解:8251=6105×1+2146 显然8251的最大公约数也必是2146的约数,同样6105与2146的公约数也必是8251的约数,所以8251与6105的最大公约数也是6105与2146的最大公约数。 6105=2146×2+1813 2146=1813×1+333 1813=333×5+148 333=148×2+37 148=37×4+0 则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法,它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下: 第一步:用较大的数m 除以较小的数n 得到一个商q 0和一个余数r 0; 第二步:若r 0=0,则n 为m ,n 的最大公约数;若r 0≠0,则用除数n 除以余数r 0得到一个商和一q 1个余数r 1; 第三步:若r 1=0,则r 1为m ,n 的最大公约数;若r 1≠0,则用除数r 0除以余数r 1得到一个商q 2和一个余数r 1; ?? 依次计算直至r n =0,此时所得到的r n -1即为所求的最大公约数。 问题3:利用辗转相除法求两数4081与20723的最大公约数. (答案:53) (二). 更相减损术 我国早期也有解决求最大公约数问题的算法,就是更相减损术。 更相减损术求最大公约数的步骤如下:可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也,以等数约之。 翻译出来为: 第一步:任意给出两个正数;判断它们是否都是偶数。若是,用2约简;若不是,执行第二步。 第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。 例2 用更相减损术求98与63的最大公约数. 解:由于63不是偶数,把98和63以大数减小数,并辗转相减,即:98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以,98与63的最大公约数是7。 问题4:用更相减损术求两个正数84与72的最大公约数。 (答案:12) (三). 比较辗转相除法与更相减损术的区别 (1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到 (四). 辗转相除法与更相减损术计算的程序框图及程序 利用辗转相除法与更相减损术的计算算法,我们可以设计出程序框图以及BSAIC 程序来在计算机上实现辗转相除法与更相减损术求最大公约数,下面由同学们设计相应框图并相互之间检查框图与程序的正确性. (1)辗转相除法的程序框图及程序 程序框图: 程序: INPUT “m=”;m INPUT “n=”;n IF m<="" while="" n="x" mod="" r="m" if="" end="" m="n" x="m" then="">0 r=m MOD n m=n n=r WEND PRINT m END 问题5:你能写出更相减损术的程序框图及程序吗? 3:例题讲解 教科书36面例1 4:课堂练习 用辗转相除法求下列各组数的最大公约数,并用更相减损术验证。 (1)225;135 (2)98;196 (3)72;168 (4)153;119 5. 课堂小结: 辗转相除法与更相减损术求最大公约数的计算方法 辗转相除法与更相减损术完整算法程序的编写 辗转相除法与更相减损术的区别 6. 课后作业 七 板书设计 八 课后记 学 术 论 文 题 目: 辗转相除法 学号: 学校: 专业: 班级: 姓名: 指导老师: 时间: 摘要:求最大公约数是一个较为经典的问题。利用辗转相减算法, 一次可以求出任意多个数的最大公约数,并编程序实现。其效率较传统的辗转相除算法有很大程度的提高。 关键词:辗转相除法,辗转相减法,最大公约数,递归 Subject : Euclidean algorithm Author : Science and technology in jiangxi normal college professional of math in class one ZengYanping Abstract: For companies is a relatively classic problems. Using Euclidean algorithm, can ask subtraction of more than a number of companies, and programming. The efficiency is the traditional Euclidean algorithm is XiangChu greatly improved. Keywords: euclidean algorithm euclidean subtraction companies recursion 正文:㈠;定义:首先用较大数作为被除数,用较小数作除数进行除法运算, 若余数不为0,再把上次的除数作为下次的被除数,把上次余数作为下次的除数,继续去除,知道余数为0为止,此时的除数即为两数的最大公约数。因此算法需连续多除法运算,故形象地命名为“辗转相除法”。 设a ,b 是任意两个正整数,由带余数除法,我们有下面的系列等式: a=bq 1+r 1,0 r n -2=r n -1q n +r n ,0 因为每进行一次带余数除法,余数就至少减一,而b 是有限的,所以我们最多进行b 次带余数除法,总可以得到一个余数是零的等式,即r n +1=0 (1)式所指出的计算方法,叫作辗转相除法。 ㈡;定理:(1)若a ,b 是任意两个整数,则(a ,b )就是(1)中最后一个不等于零的余数,即(a ,b )=r n 证:由课本2,3定理即得 r n =(0, r n )=(r n +1, r n ) =(r n , r n -1)=……… =(r 1,b)=(a,b) 证完 由于r n 能够用辗转相除法直接算出,所以辗转相除法给出了求两整数的最大公因数的实际可行的算法. 由定理2,3及(1)我们还可以得到 推论 4.1 a ,b 的公因数与(a ,b )的因数相同 (2)设a ,b 是任意两个不全为零的整数,(ⅰ)若m 是任意正整数,则(am ,bm )=(a ,b )m. (ⅱ) 若&是a ,b 的任一公因数,则( a b (a , b ) a b ,)=,特别(,)&&(a , b ) (a , b ) & =1 证:当a ,b 有一为零时,定理显然成立,今设a ,b 都不为零. (ⅰ)由定理1,(am ,bm )=(a m ,b m ),(a ,b )m=(a ,b )m, 因此不妨假定a ,b 都是正数, 在(1)里,把各式两边同乘以m ,即得 am=(bm) q 1+r 1m ,0 由定理4得(am ,bm )=r n m=(a,b)m ,因而(ⅰ)获证. (ⅱ)由(ⅰ)及定理1, ( b a a b ,)&=(&,, &)=(a ,b )=(a ,b )&&&b a b (a , b ) ,)= &&& 故 ( 当 &=(a ,b )时,上式即为( a b ,)=1 证完 (a , b ) (a , b ) 又若 (a 1,a 2)=d 2,(d 2,a 3)=d 3,……,(d n -1,a n )=d n (2) 于是我们有 (3) 若a 1,a 2,……,a n 是n 个整数,则(a 1,a 2,……,a n ) =d n 证:由(2),d n |a n ,d n |d n -1,但d n -1|d n -2,故d n |a n -1,d n |d n -2,由此类推,最后得到d n |a n ,d n |a n -1,……,d n |a 1,即d n 是a 1,a 2,……, a n 的一个公因数,又设d 是a 1,a 2,……,a n 的任一公因数,则d |a 1,d |a 2,由推论4.1, d |d 2,同样由推论4.1,d |d 3,由此类推,最后得d |d n . 因而d ≤d ≤d n . 故d n 是a 1,a 2,……,a n 的最大公因数。 ㈢:例题 (1) a=-1859,b=1573,用辗转相除法求两数的最大公因数,即 (-1859,1573) 解:1859=1*1573+286 1573=5*286+143 286=2*143 所以(—1859,1573)=143 (2) 已知数列{a n }满足a 1=1且8a n +1a n —16a n +1+2a n +5=0(n ≥1),记 b n = 11 a n - 2 (n ≥). ① 求b 1,b 2,b 3,b 4 的值; ② 求数列{b n }的通项公式及数列{a n b n }的前n 项和 解: ① a 1=1,故b 1= 1320 ,故b 4= 203 7311 =2;a 2=,故b 2=;a 3=,故b 3==4;841---28242 1 a 4= 由8a n +1a n —16a n +1+2a n +5=0(n ≥1)采用辗转相除法得: ② 8a n +1a n —16a n +1+2a n +5=(a n +1— (8a n —16)+6a n —3=0 又a n +1— 1111=,a n —=, 2b n +12b n 1 ). 2 则 16 (8a n —16)+=0 ① b n +1b n 11 + ② b n 2 又a n = 将②代入①式得 ( 8 —12)* b n +6b n +1=0 b m 4, 3 即b n +1=2b n —∴b n +1— 4442=2(b n —),b 1—=≠0 3333 24?? ∴?b n -?是首项为,公比q=2的等比数列, 33??41n =*2, 3314 即b n =*2n +(n ≥1), 33 11 由b n =得a n b n =b n +1, 2a n - 2 故b n — 故a 1b 1+a 2b 2+a 3b 3+………+a n b n 1 =(b 1+b 2+……..+ b n )+n 21 (1-2n ) 5 =+n 1-231 =(2n +5n -1) 3 (3)令F 是有理数域,求F [x ]的多项式 f(x)= x 4-2x 3-4x 2+4x -3 g(x)= 2x 3-5x 2-4x +3 的最大公因式 对f(x)与g(x)施行辗转相除法。为了避免分数系数,在做除法时,可以用F 的一个不等于零的数乘被除式或除式。而且不仅在每一次除法开始时可以这样做,就是在进行除法的过程中也可以这样做。这样商式自然会受到影响,但每次求得的余式与正确的余式只能差一个零因式。这对求最大公因式来说是没有什么关系的。 把f(x)先乘以2,再用g(x)来除: 2x 4-4x 3-8x 2+8x -62x 3-5x 2-4x +3 x +12x 4-5x 3-4x 2+3x x 3-5x 2-4x +3 (乘以2) 2x 3-8x 2+10x -12 323 x -1 5 -3x 2+14 这样,得到第一余式 r 1(x ) =-3x 2+14x -15 把g(x)乘以3,再用r 1(x ) 去除: 6x 3-15x 2-12x +93x 2+14x -15 32 -2x -136x -28x +30x x 2-4x 2+ 9 13 (乘以3) x 2-12x 6+ 39 27 2 95 56x -16 8 约去公因子56后,得出第二余式 r 2(x ) =x -3 再以r 2(x ) 除r 1(x ) ,计算结果r 1(x ) 被r 2(x ) 整除; -3x 2+14 x -15=x (-3) -(x 3+ 5) 所以r 2(x ) 就是f(x)与g(x)的最大公因式: (f(x),g(x))=x-3. 关于两个多项式的最大公因式,我们也有下面的与整数的最大公因式平行的重要定理。 参考文献 [1] 闵嗣鹤. 严士健. 初等数论. 高等教育出版社第三版[M] 2003.12 [2] 张禾瑞 郝炳新编 第五版 高等代数第二章 第四节 (3)辗转相除法(即连分式法) 当人们运用多项式作函数插值时, 得到的是一个连续无限次可导的函数,这当然再理想不过。但是,事物总是一分为二的,用它来逼近在某点邻域内无界的函数就不合理了。此时采用有理分式作函数插值将是方便、有效、可行的。这就是辗转相除法(即连分式法). 先举一例。 2例 1 用辗转相除法求 R(x)=( 2x4 + x3 +3x2+5x+10 )/( (x-x+1) 的连分式。 解 22x -x+1 | 2x4 + x3 +3x2+5x+10 4 -2x 3 +2x 2 | 3x 3 +x2 +5x+10 32+3x | 4x 2 + 2x +10 2-4x +4 6x+ 6 (余式) 2R(x)=2x2+3x+4+(6x+6)/(x -x+1) =2x2+3x+4+ 6/[(x 2-x+1)/(x +1)] 再用辗转相除法将(x 2-x+1)/(x +1)化为 x -(2x -1)/(x +1),便得R(x) 的连分式: R(x)=2x2+3x+4+6/[ x-(2x -1)/(x +1)] =2x2+3x+4+6/{x-1/[(x+1)/(2x -1)]} =2x2+3x+4+6/{ x-2/[1+3/(2x -1)]}. 教案 辗转相除法 教学目标:了解辗转相除法和更相减损术秦九韶算法,能对辗转相除法进行算理分析,学会应用算法解题。 教学重点:理解辗转相除法与更相减损术求最大公约数的方法. 教学难点:把辗转相除法与更相减损术的方法转换成程序框图与程序语言. 课 型:新授课 教学手段:多媒体 教学过程: 一、创设情境 前面我们学习了孙子定理的相关算法,知道我国古代劳动者有着过人的聪明才智,为世界数学的发展做出了重要的贡献。中国古代还有很多算法案例,本节课我们继续介绍这方面的内容。 二、活动尝试 在初中,我们已经学过求最大公约数的知识,你能求出18与30的公约数吗? 我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求204与85的最大公约数?古人对此有自己的算法。 三、师生探究 1.辗转相除法 例1 求两个正数a=204和b=85的最大公约数。 分析:204与85两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据已有的知识即可求出最大公约数 解:204=85×2+34 显然204的最大公约数也必是85的约数,同样204与85的公约数也必是34的约数,所以204与85的最大公约数也是85与34的最大公约数。 85=34×2+17 34=117×2+0 则17为204与85的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法,它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下: 第一步:用较大的数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; …… 依次计算直至rn=0,此时所得到的rn-1即为所求的最大公约数。 2.更相减损术 我国早期也有解决求最大公约数问题的算法,就是更相减损术。 更相减损术求最大公约数的步骤如下:可半者半之,不可半者,副置分母分子之数,以少减多,更相减损,求其等也,以等数约之。 翻译出来为: 第一步:任意给出两个正数;判断它们是否都是偶数。若是,用2约简;若不是,执行第二步。 第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。 例2 用更相减损术求91与49的最大公约数. 解:由于49不是偶数,把91和49以大数减小数,并辗转相减, 即:91-48=42 49-42=7 42-7=35 35-7=28 28-7=21 21-7=14 14-7=7 所以,91与49的最大公约数是7。 四、数学理论 1. 欧几里得辗转相除法找出a,b的最大公约数的步骤是: (1)计算a÷b的余数r,若r=0,则b为a,b的最大公约数; (2)若r=0,则把前面的除数b作为新的被除数,把r作为新的除数,继续运算,直到余数为0,此时的除数即为a,b的最大公约数. 2.更相减损术找出a,b的最大公约数的步骤是 (1)任意给出两个正数;判断它们是否都是偶数。若是,用2约简;若不是,执行第二步。(2)以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数。继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数。 3.比较辗转相除法与更相减损术的区别 (1)都是求最大公约数的方法,计算上辗转相除法以除法为主,更相减损术以减法为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与差相等而得到 4. 辗转相除法的程序框图及程序伪代码 程序框图: 程序:Read a,b While Mod(a,b)≠0 r←Mod(a,b) a←b b←r End While Print b 五、巩固运用 例1.求78和36的最大公约数 利用辗转相除法步骤: 计算出78?36的余数6,再将前面的除数36作为新的被除数,36?6=6,余数为0,则此时的除数6即为78和36的最大公约数。 利用更相减损之术步骤: 78-36=42 42-36=6 36-6=30 30-6=24 24-6=18 18-6=12 12-6=6 6即为78和36的最大公约数 例2.写出图示流程图所表达算法的伪代码,并求出最后输出的n的值 10 m←147 20 n←84 30 r←Mod(m,n) 40 If r=0 Then Go To 70 50 m←n,n←r 60 Go To 30 70 Print n 80 End If 六、回顾反思 辗转相除法是当大数被小数除尽时,结束除法运算,较小的数就是最大公约数.更相减损术是当大数减去小数的差等于小数时减法停止.较小的数就是最大公约数.求三个以上(含三个数)的数的最大公约数时,可依次通过求两个数的最大公约数与第三数的最大公约数来求得. 七、课后练习 1.用辗转相除法求294和84的最大公约数时,需要做除法的次数是( ) A.2 B.3 C.4 D.5 2.两个整数228和1995的最大公约数是( ) A. 38 B.57 C.76 D.171 3. 4.117与182的最大公约数是 5.利用辗转相除法求3869与6497的最大公约数与最小公倍数。 6.用伪代码写出求平方后小于1000的所有正整数的算法,并画出流程图。 参考答案: 1. A 2. B 3. 更相减损术 九章算术 4. 13 5.6497=3869×1+2628 3869=2628×1+1241 2628=1241*2+146 1241=146×8+73 146=73×2+0 所以3869与6497的最大公约数为73,最小公倍数为3869×6497/73=344341 6. I←1 S←I2 While S≤1000 Print I I←I+1 End While 范文二:辗转相除法教案
范文三:辗转相除法
范文四:辗转相除法
范文五:辗转相除法教案