1、歡迎同學們歡迎同學們！ 重慶市魚洞中學校 -杜在華輾轉相除法與更相減損術 理解輾轉相除法和更相減損術,能夠利用輾轉相除法和更相減損術求兩個數的最大公約數,通過輾轉相除法和更相減損術案例,進一步體會算法思想.學習重點: 輾轉相除法(歐幾里德算法),更相減損術.學習目標:必修3 P3437動手實踐: 例1自主學習: P34-35 例1.求18和30的最大公約數.解法一:(分解質因數)18=29=233,30=56=523,18和30的最大公約數為gcd(18,30)=23=6.解法二:(短除法:先用兩個數公有的質因數連續去除,一直除到所得的商是互質數為止,然后把所有的除數連乘起來即為最大公約數.)

2、 18 3029 1533 518和30的最大公約數為gcd(18,30)=23=6.深入理解: P34-35 輾轉相除法模仿學習: 例2.用輾轉相除法求下列兩個數的最大公約數:1.帶余除法: 被除數=除數商余數結論:如果n和r的最大公約數為x,那么x一定也是m的約數.故n,r的最大公約數也是m,n的最大公約數.gcd(m,n)=gcd(n,r)例如: 48=676,48=426,42與6的最大公約數6也是48的約數,即 gcd(48,42)=gcd(42,6)=6.2.輾轉相除法:被除數和除數的最大公約數也是除數和余數的最大公約數.(1)225與135;(2)72與168;(3)119與15

3、3.m=nqr即 ,(0rn)合作學習: 例2例2.用輾轉相除法求下列兩個數的最大公約數:(1)225與135;(2)72與168;(3)119與153.解: 225=135190,135=90145,90=4520, gcd(225,135)=gcd(135,90)=gcd(90,45)=45注意:用較大的整數除以較小的整數,直到余數為0.解: 168=72224,72=2430, gcd(72,168)= gcd(72,24)=24解: 153=119134,119=34317,34=1720, gcd(119,153)=gcd(119,34)=gcd(34,17)=17上述求兩個正整數的

4、最大公約數的方法稱為輾轉相除法或歐幾里得算法.合作學習: P35思考思考:你能把輾轉相除法求兩個正整數m,n的最大公約數編成一個計算機程序嗎?第一步,給定兩個正整數m,n(mn).第二步,計算m除以n所得的余數r. 第三步,m=n,n=r.第四步,若r=0,則m,n的最大公約數等于m,否則,返回第二步. 算法:合作學習: P35思考思考:你能把輾轉相除法求兩個正整數m,n的最大公約數編成一個計算機程序嗎?程序框圖:開始輸入m，n求m除以n的余數rm=nn=rr=0？是是輸出m結束否INPUT m，n DO r=m MODn m=n n=rLOOP UNTIL r=0PRINT mEND程序:合

5、作學習: P36思考自主學習: P36-37思考:你能用當型循環結構構造算法,求兩個正整數m,n的最大公約數?試寫出算法步驟、程序框圖和程序.程序框圖:開始輸入m，n求m除以n的余數rm=nn0？否輸出m結束結束是n=r程序:INPUT m，nWHILE n0 r=m MODn m=n n=rWENDPRINT mEND深入理解: P36-37更相減損術模仿學習: 例31.減法: 被減數減數差, 即 ,(ab).a-b=c結論:如果a與b的最大公約數為x,那么x也是c的約數.即x是a,b,c的公約數.故 a,b的最大公約數也是b,c的最大公約數.2.更相減損術:被減數與減數的最大公約數也是減數

6、與差的最大公約數.gcd(a,b)=gcd(b,c)了解:“更相減損術”在中國古代數學專著九章算術中記述為:可半者半之,不可半者,副置分母、子之數,以少減多,更相減損,求其等也,以等數約之. 例3.用更相減損術求下列兩個數的最大公約數:(1)225與135;(2)72與168;(3)119與153.合作學習:例3. 用更相減損術求下列兩個數的最大公約數:(1)225與135;(2)72與168;(3)119與153.解: 22513590,1359045,904545, gcd(225,135)=gcd(135,90)=gcd(90,45)=45注意:用較大的整數減去較小的整數,直到差為0.解

7、: 1687296,9672=24,gcd(72,168)=gcd(72,96)24解: 153-119=34,119-34=85,85-34=51, gcd(119,153)=gcd(119,34)=gcd(34,17)=177224=48,4824=24,2424=0,45450,=gcd(72,24)=gcd(48,24)=51-34=17,34-17=17,17-17=0,=gcd(34,85)=gcd(34,51)勇攀高峰: P37思考思考:你能根據更相減損術設計程序,求兩個正整數的最大公約數嗎?第一步,給定兩個正整數m,n(mn). 第二步,計算m-n所得的差k. 第三步,比較n與

8、k的大小,其中大者用m表示,小者用n表示. 第四步,若m=n,則m,n的最大公約數等于m;否則,返回第二步. 算法步驟:勇攀高峰: P37思考思考:你能根據更相減損術設計程序,求兩個正整數的最大公約數嗎?開始輸入m，nnk？m=n是是輸出m結束mn？k=m-n是是否n=km=k否程序框圖:程序:INPUT m，nWHILE mn k=m-nIF nk THEN m=n n=kELSE m=kEND IFWENDPRINT mEND小結: 1.輾轉相除法,就是對于給定的兩個正整數,用較大的數除以較小的數,若余數不為零,則將余數和較小的數構成新的一對數,繼續上面的除法,直到大數被小數除盡為止,這時的較小的數即為原來兩個數的最大公約數. 2.更相減損術,就是對于給定的兩個正整數,用較大的數減去較小的數,然后將差和較小的數構成新的一對數,繼