当前位置：文档之家 › 算法案例---辗转相除法与更相减损术

算法案例---辗转相除法与更相减损术

  • 格式：doc
  • 大小：37.50 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

辗转相除法与更相减损术、秦九韶算法 课件

辗转相除法与更相减损术、秦九韶算法 课件

(2)算法步骤 第一步,输入两个正整数m,n(m>n). 第二步,计算m除以n所得的余数r. 第三步,m=n,n=r. 第四步,若r=0,则m,n的最大公约数等于m;
否则,返回第二步.
类型 二 更相减损术及其应用
【典型例题】
1.用更相减损术求123与51的最大公约数时,需做减法的次数
是( )
A.3
B.5
C.6
D.8
2.用更相减损术求104与130的最大公约数. 【解题探究】1.用更相减损术求两个正整数的最大公约数时, 何时停止计算? 2.如果两个数都是偶数,求其最大公约数时,第一步操作是什么? 探究提示:1.当减数与差相等时停止计算. 2.如果两个数都是偶数,第一步是先用2约简.
【解析】1.选D. 123-51=72, 72-51=21, 51-21=30, 30-21=9, 21-9=12, 12-9=3, 9-3=6, 6-3=3, 所以共做了8次减法.
【拓展提升】更相减损术与辗转相除法的对比 (1)尽管两种算法分别来源于东、西方古代数学名著,但是二者 的算理却是相似的,有异曲同工之妙.主要区别在于辗转相除法 进行的是除法运算,即辗转相除;而更相减损术进行的是减法运 算,即辗转相减,但是实质都是一个不断的递归过程. (2)解答同一个题目,一般情况下,用辗转相除法比用更相减损 术运算的次数要少.
【知识点拨】 1.辗转相除法的原理 设m,n是两个正整数(不妨设m>n),用m除以n,若商为q1,余数为 r1(0≤r1<n),则m=n·q1+r1,显然,若q1是m和n的公约数,即q1能 整除m和n,则q1也必然能整除r1,这样q1也是n和r1的公约数,故 求m和n的公约数就是求n和r1的公约数;同理,用n除以r1,得

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (99)

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (99)

[精解详析] (1)101 111 011(2)＝1×28＋0×27＋1×26＋ 1×25＋1×24＋1×23＋0×22＋1×21＋1×20＝379(10)． (2)235(7)＝2×72＋3×71＋5×70＝124(10)． (3)
∴137(10)＝345(6)．
(4)53(8)＝5×81＋3×80＝43(10)． ∴53(8)＝101 011(2)．
[一点通]
1．k进制数化为十进制数的步骤： (1)把k进制数写成不同数位上的数字与k的幂
的乘积之和的形式． (2)按十进制数的运算规则运算出结果．
2．十进制数化为k进制数(除k取余法)的步骤：
6．二进制数101 110(2)转化为八进制数为 ( )
A．45(8)
B．56(8)
C．67(8)
D．78(8)
3．不同进位制的数照样可比较大小．但一 般要转化到同一进位制下比较大小．
[例1] 求228与1 995的最大公约数 [思路点拨] 可以考虑用辗转相除法，也可考虑用更 相减损术． [精解详析] 法一(辗转相除法) 1 995＝8×228＋ 171,228＝1×171＋57,171＝3×57， 所以228与1 995的最大公约数为57.
解析：先化成十进制，再化成八进制 101 110(2)＝1×25＋0×24＋1×23＋1×22＋1×2 ＋0＝46.
∴46＝56(8)． 答案：B
7．下列所给的四个数中，最小的是
()
A．3 732(8)
B．5 555(7)
C．2 011
D．133 210(4)
解析：将各项都化成十进制数再比较大小．
必须从下到上排列；(3)切记在所求数的右下角标明基数．
秦九韶算法
功能 它是一种用于计算 一元n次多项式 的值的方法

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (18)

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (18)
an×果k．n＋如ana－n1a×n－kn1－…1＋a…2a1＋a0a(2k×)＝k2＋a1×k＋a0 .其中 要注意 的是，k的幂的最高次数应是该k进制的位数减去 1，然后逐个减小1，最后是0次幂．
• (2)将十进制化为k进制数的方法叫 除k取余法 ．即用k连续去除该十进制数或所得的商，
直到商是零为止，然后把每次所得的余数倒着 排成一列，就是相应的k进制数．例如，把十进 制数化为二进制数的方法是除2取余法．
• WHILE q<>0
• q＝a\k • r＝a MOD k • b＝b＋r*10^i
列得
• • i＝i＋1 • a＝q • WEND
• PRINT b • END
←求a除以k的整数商 ←求a除以k的余数 ←把余数依次从右到左排
到k进制数b
• (5)k进制数的性质：
• ①在k进制中，具有k个数字符号；例如十 进制，有0,1,2,3,4,5,6,7,8,9十个数字．十六 进制有0～9和A、B、C、D、E、F共十六 个数字．
• 1．把一个n次多项式f(x)＝anxn＋an－1xn－1 ＋…＋a1x＋a0改写成如下形式：
• f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0 • ＝(anxn－1＋an－1xn－2＋…＋a1)x＋a0 • ＝((anxn－2＋an－1xn－3＋…＋a2)x＋a1)x＋a0 • ＝…
行的运算，故用循环语句来实现．
(1)秦九韶算法过程分析：
由于vv0k＝＝vakn－，1x＋an－k. 其中 k＝1,2，…，n. 这样我们便可由 v0 依次求出 v1，v2，…，vn： v1＝v0x＋an－1，v2＝v1x＋an－2，v3＝v2x＋an－3，…，vn＝ vn－1x＋a0. 于是我们用 v 来记录每次一次式计算的结果，最初赋值 v＝an，用 v＝v*x＋an－i 实现递推循环，i 的初值为 1，i＝i＋ 1 记录循环次数，i≤n 控制何时结束循环输出 v.f(x)的系数 ak 用一个循环语句实现输入．

《算法案例：辗转相除法与更相减损术》导学案

《算法案例：辗转相除法与更相减损术》导学案

辗转相除法与更相减损术学习目标：1°理解辗转相除法与更相减损术中蕴含的数学原理，根据原理进行算法分析； 2°能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序； 3°感受算法的意义和价值。

知识情境：1：10 WHILE 语句: 计算机执行语句的过程是20 UNTIL 语句: 计算机执行语句的过程是你能编写一个程序,用二分法求方程220(0)x x -=>的近似解吗?2：我们已经学过求最大公约数的方法，你能求出18与30的公约数吗？如果公约数比较大而且根据我们的观察又不能得到一些公约数，又应该怎样求它们的最大公约数？比如,如何求1424与801的最大公约数？知识生成：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 -即为所求的最大公约数.例题1：求两个正数1424和801的最大公约数.①以上我们求最大公约数的方法就是辗转相除法，也叫欧几里德算法.②由上述步骤可以看出，辗转相除法中的除法是一个反复执行的步骤，且执行次数由余数是否等于0来决定,所以可把它看成一循环体,写出辗转相除法完整的程序框图和程序语言.2. 教学更相减损术：我国早期也有求最大公约数问题的算法，就是更相减损术. 在《九章算术》中有更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母•子之数，以少减多，更相减损，求其等也，以等数约之.翻译为：(1) 任意给出两个正数；判断它们是否都是偶数. 若是，用2约简；若不是，执行第二步.(2) 以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数. 继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.例题2. 用更相减损术求91和49的最大公约数.练一练：：1．求两个正数8251和2146;228和1995;5280和12155的最大公约数.2．用更相减损术求72和168的最大公约数.3．编写一个程序, 求两个正数8251和2146的最大公约数.4．比较辗转相除法与更相减损术的区别(1)都是求的方法，计算上辗转相除法以法为主，更相减损术以法为主，计算次数上法计算次数相对较少，特别当两个数字时计算次数的区别较明显．(2)从结果体现形式来看，辗转相除法体现结果是以则得到，而更相减损术则以而得到．。

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (29)

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (29)
[分析] 1. 七 进 制 数 从 右 边 数 第 二 位 的 数 字 若 是 k(k ＝ 0,1,2,3,4,5,6)，其在十进制中表示的数是多少？
2 ．相同进制中，位数越多的数越大对吗？不同进制中的
数如何比较大小？
第一章 1.3 第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
●自我检测 1．以下各数有可能是五进制数的是( A．15 C．731 B．106 D．21340 五进制数中各个数字均是小于5的自然数，则仅有 )
[答案] D
[解析] 21340满足，故选D.
第一章
1.3
第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
2．将二进制数1101(2)化为十进制数为( A．10 C．12 [答案] D B．11 D．13
第一章
1.3
第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
第一章
1.3
第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
程序： INPUT “a，k，n＝”；a，k，n b＝0 i＝1 t＝a MOD 10 DO b＝b＋t*k^(i－1) a＝a\10 t＝a MOD 10 i＝i＋1 i>n LOOP UNTIL _______ PRINT b END
1)． (2)在k进制中，由低位向高位是按“满k进一”的规则进行 计数． (3)不同进位制都是按位置原则计数的．
第一章 1.3 第2课时
成才之路 ·高中新课程 ·学习指导 ·人教A版 ·数学 ·必修3
[特别提醒]
在k进制数中，从右向左数第i位的数字m，在
十进制中表示m个ki－1.

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (30)

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (30)

3．秦九韶算法
把一个n次多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0改写成如 下形式：
(…((anx＋an－1)x＋an－2)x＋…＋a1)x＋a0， 求多项式的值时，首先计算_最__内__层__括__号__内__一次多项式的值， 即v1＝_a_n_x_＋__a_n_－_1_，然后由内向外逐层计算一次多项式的值， 即 v2＝_v_1_x_＋__a_n_－_2_， v3＝_v_2_x_＋__a_n_－_3_，
(4分) (6分) (8分)
(10分) (12分)
【题后反思】 (1)先将多项式写成一次多项式的形式，然 后运算时从里到外，一步一步地做乘法和加法即可．这样 比直接将x＝2代入原式大大减少了计算量．若用计算机计 算，则可提高运算效率． (2)注意：当多项式中n次项不存在时，可将第n次项看作 0·xn.
自学导引
1．辗转相除法 (1)辗转相除法，又叫欧几里得算法，是一种求两个正整数 的_最__大__公__约__数__的古老而有效的算法． (2)辗转相除法的算法步骤 第一步，给定_两__个__正__整__数__m__，__n_. 第二步，计算_m__除__以__n_所__得__的__余__数__r_. 第三步， _m__＝__n_，__n_＝__r_. 第四步，若r＝0，则m、n的最大公约数等于_m__；否则， 返回_第__二__步___.
… vn＝_v_n_－_1_x_＋__a_0_. 这样，求n次多项式f(x)的值就转化为求__n_个__一__次__多__项__式___的
值．
4．进位制 进位制是人们为了_计__数__和_运__算__方__便__而约定的记数系统， “满k进一”就是k进制，k进制的基数是k. 把十进制转化为k进制数时，通常用除k取余法． 不同进制间的数不能比较大小，对吗？ 提示 不对．不同的进位制是人们为了计数和运算方便而 约定的记数系统，不同进位制的数照样可比较大小，不过 一般要转化到十进制下比较大小更方便一些．

1.3.1算法案例(辗转相除法)

1.3.1算法案例(辗转相除法)

程序框图： 程序框图： 开 始 程序: 程序
INPUT “m,n为正整数且m>n”;m,n DO r = m MOD n m= n n = r LOOP UNTIL r=0 PRINT m END
输入正整数m,n（ 输入正整数m,n（m>n) m,n r=m MOD n
m=n n=r
r=0? 输出m 输出m 结 束 否
f (x) = an xn + an−1xn−1 +L+ a1x + a0
对该多项式按下面的方式进行改写： 对该多项式按下面的方式进行改写：
f (x) = an xn + an−1xn−1 +L+ a1x + a0
= (an xn−1 + an−1xn−2 +L+ a1)x + a0
=L L
= ((an xn−2 + an−1xn−3 +L+ a2 )x + a1)x + a0
思考1:为什么更相减损术能求两个正整数的最 思考1:为什么更相减损术能求两个正整数的最 1: 大公约数？ 大公约数？ 练习:用更相减损术求1457 188的最大公约数 1457与 的最大公约数. 练习:用更相减损术求1457与188的最大公约数. 用更相减损术求84 72的最大公约数 84与 的最大公约数. 例2: 用更相减损术求84与72的最大公约数.
2 18 3 9 3 30 15 5
所以， 与 的最大公约数是 的最大公约数是2× 所以，18与30的最大公约数是 ×3=6 思考2： 的最大公约数， 思考 ：求8251与6105的最大公约数，用上述 与 的最大公约数 方法适合吗？ 方法适合吗？

算法案例第1课时辗转相除法与更相减损术学案课件 新人教A版必修3

算法案例第1课时辗转相除法与更相减损术学案课件 新人教A版必修3

1．辗转相除法 (1)辗转相除的原理： 设m， n是两个整数 (不妨设m>n)，用m除以n，若商为 q1 ，余数为 r1(0≤r1<n) ，则 m ＝ n· q1 ＋ r1 ，显然若 x 是 m 和 n 的 公约数，即x能整除m和n，则x也必然能整除r1，这样x也是 n 和 r1 的公约数，故求 m 和 n 的公约数就是求 n 和 r1 的公约数； 同理，用n除以r1，得n＝r1· q2＋r2(0≤r2<r1)，故求m和n的公 约 数 就 是 求 r2 和 r1 的 公 约 数 ， … ， 依 次 下 去 ， 由 于 m>n>r1>r2>… ，所以到某一步必然有 ri ＝ ri ＋ 1· qi ＋ 2 ，即 ri 恰 能被ri＋1整除，这时ri＋1是ri和ri＋1的最大公约数，它也必然 是ri－1和ri、ri－2和ri－1、…、r1与r2、n和r2、m和n的最大公 约数．
此编写的算法，也称作“欧几里得算法”．
3．对于正整数m与n(m>n)，总能找到整数q和r(0≤r<n)
使得m＝nq＋r成立，这个除法称为带余除法．通常记r＝ mMODn.
重点：算法案例的原理、算法设计及算法思想的体 会． 难点：理解算法案例的内容及具体算法设计的关键步
骤．
一、弄清算法原理，掌握算法程序，经历算法设计过 程，体会算法设计的关键环节，领悟算法思想．
(1)更相减损术求两数最大公约数的过程与算法设计． 对于给定的两个数，用较大的数减去较小的数，接着 把得到的差与较小的数比较，用这时两个数中较大的数减 去较小的数，继续这样的操作 ( 大数减小数 ) ，直到所得的
数相等为止，那么这个数 ( 相等数 ) 就是所求的最大公约
数．
显然，上述过程中大数减去小数是一个重复执行的过

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (100)

算法案例-辗转相除法与更相减损术、秦九韶算法-优质获奖精品课件 (100)

第一章 算法初步
题型三 进位制
例3 (本题满分9分)完成下列进位制之 间的转化: (1)将十进制数30转化为二进制数; (2)将二进制数101111011(2)转化为十进制数.
栏目 导引
【解】 (1) 4分
第一章 算法初步
∴30(10)＝11110(2). 5分 (2)101111011(2)＝1×28＋0×27＋1×26＋ 1×25＋1×24＋1×23＋0×22＋1×21＋ 1×20＝379. 9分
栏目 导引
第一章 算法初步
法二: 由更相减损术, 得 108－45＝63, 63－45＝18, 45－18＝27, 27－18＝9, 18－9＝9, 故108与45的最大公约数是9.
栏目 导引
第一章 算法初步
题型二 秦九韶算法及其应用
例2 用秦九韶算法求多项式 f(x)＝3x5＋8x4－3x3＋5x2＋12x－6 当x＝2时的值. 【解】 根据秦九韶算法, 把多项式改写 成如下形式: f(x)＝((((3x＋8)x－3)x＋5)x＋12)x－6, 按 照从内到外的顺序,
栏目 导引
第一章 算法初步
依次计算当x＝2时一次多项式的值. v0＝3, v1＝v0×2＋8＝3×2＋8＝14, v2＝v1×2－3＝14×2－3＝25, v3＝v2×2＋5＝25×2＋5＝55, v4＝v3×2＋12＝55×2＋12＝122, v5＝v4×2－6＝122×2－6＝238. 所以当x＝2时, 多项式的值为238.
栏目 导引
第一章 算法初步
(3)不同进位制数之间的转化 ①k进制数转化为十进制数 把k进制数转化为十进制数, 写成不同位上 数字与基数幂的乘积之和即可(简称幂积求 和), 即anan－1…a1a0(k)＝an×kn＋an－1×kn－1 ＋…＋a1×k＋a0.例如, 将二进制数11001(2) 化为十进制数: 11001(2)＝1×24＋1×23＋ 0×22＋0×21＋1×20＝16＋8＋1＝25.

078辗转相除法、更相减损术

078辗转相除法、更相减损术

高一数学078 高一年级班教师方雄飞学生课题 1.3.1 算法案例————辗转相除法、更相减损术一、学习目的1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。

2．了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。

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

二、学习重点、难点重点：理解辗转相除法与更相减损术求最大公约数的方法。

理解秦九韶算法的思想。

难点：把辗转相除法与更相减损术、秦九韶算法的方法转换成程序框图与程序语言。

三、学习过程复习回顾直到型循环与当型循环的程序语言分别是什么？知识探究（一）:辗转相除法思考1: 18与30的最大公约数是多少？你是怎样得到的？思考2: 对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？思考3: 又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？例1：用辗转相除法求225和135的最大公约数练习1：利用辗转相除法求两数4081与20723的最大公约数.思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(m>n).第二步，第三步，第四步，第五步，思考5:该算法的程序框图如何表示？思考6:该程序框图对应的程序如何表述？知识探究（二）:更相减损术思考1:设两个正整数m>n，若m-n=k，则m与n的最大公约数和n与k的最大公约数相等.反复利用这个原理，可求得98与63的最大公约数为多少？练习2：用更相减损术求两个正数84与72的最大公约数思考2: 上述求两个正整数的最大公约数的方法称为更相减损术.一般地，用更相减损术求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，给定两个正整数m，n(m>n).第二步，第三步，第四步，第五步，思考3: 该算法的程序框图如何表示？思考4:该程序框图对应的程序如何表述？知识探究（三）:辗转相除法与更相减损术的区别（1）都是求最大公约数的方法，计算上辗转相除法以为主，更相减损术以为主，计算次数上辗转相除法计算次数相对，特别当两个数字大小区别较大时计算次数的区别较明显。

8§131算法案例——辗转相除法与更相减损术.docx

8§131算法案例——辗转相除法与更相减损术.docx

教师课时教案问题与情境及教师活动学生活动思考3：上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m, n的最大公约数，可以用什么算法？其算法步骤如何设计？辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.思考4：你能否把辗转相除法编程？辗转相除法求两个数的最大公约数，其算法步骤可以描述如下：第一步，给定两个正整数m, n.第二步，求余数I•:计算m除以n,将所得余数存放到变量I■中.第三步，更新被除数和余数：m=n, n=r.第四步，判断余数「是否为0.若余数为0,则输出结果；否则转向第二步继续循坏执行.程序框图如下图：程序：过程及方法思考4：你能用当型循环结构构造算法,求两个正整数的最大公约数吗？试画出程序框图和程序.当型循坏结构的程序框图如右图程序:探究二：更相减损术思考1：设两个正整数m>n,若m-n=k,则m 与 n 的最大公约数和n 与k 的最大公约数相 等.反复利用这个原理，可求得98与63 的最大公约数为多少？ 解：由于63不是偶数，把98和63以大数减小数， 并辗转相减，如下图所示. 所以，98和63的最大公约数等于7. 思考2：上述求两个正整数的最大公约数的方法称 为更相减损术•一般地，用更相减损术求两个正整数m, n 的最 大公约数，可以用什么逻辑结构来构造算法？ 更相减损术，就是对于给定的两个正整数，用较大的数减去较小 的数，然后将差和较小的 数构成新的一对数， 继续上面的减法， 直到差和较小的数相等， 此时相等的两数即为原来 两个数的最大公约数. 思考3：你能否把更相减损术编程？ 探究三：辗转相除法与更相减损术的区别（1） 都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少， 特别当两个数字大小区别较大时计算次数的区别较明显。

算法案例(完整版)

算法案例(完整版)

例2 已知10b1（2）=a02（3）,求数字a， b的值.
10b1（2）=1×23+b×2+1=2b+9. a02（3）=a×32+2=9a+2. 所以2b+9=9a+2，即9a-2b=7.
故a=1，b=1.
小 结
1. k进制数使用0～（k-1）共k个数字， 但左侧第一个数位上的数字（首位数字） 不为0. 2.用 an an-1 a2 a1(k ) 表示k 进制数，其中k称为基数，十进制数不标 注基数. 3. 把k进制数化为十进制数的一般算式 是： an an-1 a2 a1(k )
第一步，输入a和n的值. 第二步，令b=0，i=1. i-1 b 第三步， = b + ai ´ 2 ， i=i+1. 第四步，判断i>n 是否成立.若是，则输 出b的值；否则，返回第三步.
同样地，把k进制数 a = an an-1 a2 a1(k )
化为十进制数b的算法和程序框图如何设 计？ 第一步，输入a，k和n的值. 第二步，令b=0，i=1.
“更相减损术”在中国古代数学专著《 九章算术》中记述为：
可半者半之，不可半者，副置分母、 子之数，以少减多，更相减损，求其等 也，以等数约之.
例1 分别用辗转相除法和更相减损 术求168与93的最大公约数. 辗转相除法：168=93×1+75，
93=75×1+18， 75=18×4+3， 18=3×6.
a=rnrn-1„r1r0(2)
知识探究(二):十进制化k进制的算法
思考1:根据上面的分析，将十进制数a化 为二进制数的算法步骤如何设计？ 第一步，输入十进制数a的值. 第二步，求出a除以2所得的商q，余数r. 第四步，若q≠0，则a=q，返回第二步； 否则，输出全部余数r排列得到 的二进制数.

最新人教版普通高中课程标准实验教科书必修3《算法案例——辗转相除法和更相减损术》说课稿

最新人教版普通高中课程标准实验教科书必修3《算法案例——辗转相除法和更相减损术》说课稿

课题：算法案例——辗转相除法和更相减损术教材：人教版普通高中课程标准实验教科书必修3第一章第1.3节1、教材分析与传统教学内容相比，《算法初步》为新增内容，算法是计算机科学的重要基础，算法思想已经渗透到社会的方方面面，算法思想也逐渐成为每个现代人应具有的数学素养。

算法思想即体现了时代的特点，也是中国古代数学灿烂的历史和巨大的贡献在新层次上的复兴。

本节内容是探究古代算法案例――辗转相除法和更相减损术，经历设计算法解决问题的全过程，体会算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理的思考和数学表达能力，巩固算法三种描述性语言（自然语言、图形语言和程序语言），提高学生分析和解决问题的能力。

2、教学目标分析：（1）知识目标：①理解辗转相除法和更相减损术求两个正数的最大公约数的原理；②能用写算法步骤、画流程图和编程序表达辗转相除法；说明：在这里，理解案例中的新的知识是理解算法的必要的前提，但重要的是理解案例中的算法核心思想，而不是强调对案例中新知识的记忆和灵活运用。

（2）能力目标：①培养学生把具体问题抽象转化为算法语言的能力；②培养学生自主探索和合作学习的能力。

（3）情感目标：①使学生进一步了解从具体到一般思想方法。

②体会中国古代数学对世界数学的巨大贡献，培养爱国思想和学习数学的积极性。

3、教学重点与难点分析：（1）教学重点：能用写算法步骤、画流程图和编程序表达辗转相除法及更相减损术。

（体会算法解决问题的全过程）（2）教学难点：用不同逻辑结构的程序框图表达算法；4、教学方法与手段（1）、教法：阅读指导，以问题为载体，有引导的对话，让学生经历知识的形成过程和发展过程，有利于学生活动的充分展开。

（2）、学法：以观察、讨论、思考、分析、动手操作、自主探索、合作学习多种形式相结合，引导学生多角度、多层面认识事物，突破教学难点。

5、教学过程设计分析：辅助工具：ppt课件知识准备：带余除法6、评价分析：（1）、指导思想：①新知识与旧知识相结合的原则；②掌握知识与发展智力、能力相统一的原则；③教师的主导作用与学生的主体作用相结合的原则。

1.3.1 算法案例(辗转相除法)

1.3.1 算法案例(辗转相除法)

***思考：你能根据更相减损术设计程序，求两 个正整数的最大公约数吗？
(1)、算法步骤 第一步：输入两个正整数a,b(a>b); 第二步：若a不等于b ,则执行第三步；否则转 到第五步； 第三步：把a-b的差赋予r; 第四步：如果b>r, 那么把b赋给a,把r赋给b;否 则把r赋给a，执行第二步；
(1)、算法步骤： 第一步：输入两个正整数m,n(m>n). 第二步：计算m除以n所得的余数r.
第三步：m=n,n=r.
第四步：若r＝0,则m,n的最大公约数等于m； 否则转到第二步. 第五步：输出最大公约数m.
(2)、程序框图：
开始
程序：
INPUT “m,n=“;m,n DO r=m MOD n m=n
所以，49和63的最大公约数为7
思考：除了用这种方法外还有没有其它方法？ 例：如何算出8251和6105的最大公约数？
新课讲解：
一、辗转相除法（欧几里得算法）
1、定义： 所谓辗转相除法，就是对于给定的两个 数，用较大的数除以较小的数。若余数不为 零，则将余数和较小的数构成新的一对数， 继续上面的除法，直到大数被小数除尽，则 这时较小的数就是原来两个数的最大公约数。
第五步：输出最大公约数b.
(2)、程序框图
程序
INPUT “a,b=“;a,b WHILE a<>b r=a-b IF b>r THEN a=b b=r ELSE a=r END IF WEND PRINT b END
开始
输入a,b a≠b? 是 r=a-b 否
a=r
否
r<b? 是 a=b b=r 输出b 结束
小结
比较辗转相除法与更相减损术的区别

高中数学例题：辗转相除法与更相减损术

高中数学例题：辗转相除法与更相减损术

高中数学例题：辗转相除法与更相减损术例1．分别用辗转相除法和更相减损术求378与90的最大公约数．【答案】18【解析】用辗转相除法：378=90×4+18，90=18×5．∴378与90的最大公约数是18．用更相减损术：∵378与90都是偶数，∴用2约分后得189和45．189－45=144，144－45=99，99－45=54，54－45=9，45－9=36，36－9=27，27－9=18，18－9=9．∴378与90的最大公约数为2×9=18．【总结升华】比较辗转相除法与更相减损术的区别(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；(2)从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.由该题可以看出，辗转相除法得最大公约数的步骤较少.对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.举一反三：【变式1】（1）用更相减损术求两个正数84与72的最大公约数．（2）利用辗转相除法求3869与6497的最大公约数与最小公倍数．【解析】（1）因为84=21×4，72=18×4，所以21－18=3，18－3=15，15－3=12，12－3=9，9－3=6，6－3=3．所以21和18的最大公约数等于3．所以84和72的最大公约数等于12．【总结升华】先约简，再求21与18的最大公约数，然后乘以约简的4得84与72的最大公约数．（2）6497=3869×1+2628，3869=2628×1+1241，2628=1241×2+146，1241=146×8+73，146=73×2+0．所以3 869与6 497的最大公约数为73，最小公倍数为3 869×6497÷73=344341．例2．求三个数：168，54，264的最大公约数．【思路点拨】运用更相减损术或辗转相除法，先求168和54的最大公约数a，再求a与264的最大公约数．【答案】6【解析】采用更相减损术先求168和54的最大公约数．（168，54）→（114，54）→（60，54）→（6，54）→（6，48）→（6，42）→（6，36）→（6，30）→（6，24）→（6，18）→（6，12）→（6，6）．故168和54的最大公约数为6．采用辗转相除法求6和264的最大公约数．∵264=44×6+0，∴6为264与6的最大公约数，也是这三个数的最大公约数．【总结升华】求最大公约数通常有两种方法：一是辗转相除法；二是更相减损术，对于3个数的最大公约数的求法，则是先求其中两个数的最大公约数m，再求m与第三个数的最大公约数．同样可推广到求3个以上数的最大公约数．举一反三：【变式1】求三个数324，243，135的最大公约数．【答案】27【解析】∵324=243×1+81，243=81×3+0，∴324与243的最大公约数为81．又135=81×1+54，81=54×1+27，54=27×2+0，∴81与135的最大公约数为27．∴三个数324，243，135的最大公约数为27．更相减损术：∵324－243=81，243－81=162，162－81=81，∴81是324和243的最大公约数．又135－81=54，81－54=27，54－27=27，∴27是81与135的最大公约数．∴三个数324，243，135的最大公约数为27．例3.甲、乙、丙三种溶液分别重147g、343g、133g，现要将它们分别全部装入小瓶中，每个小瓶装入液体的质量相同，问每瓶最多装多少？【思路点拨】由题意，每个小瓶最多能装的溶液的质量应是三种溶液质量的最大公约数.【答案】7g【解析】先求147与343的最大公约数.343-147=196，196-147=49，147-49=98，98-49=49，∴147与343的最大公约数是49.再求49与133的最大公约数.133-49=84，84-49=35，49-35=14，35-14=21，21-14=7，14-7=7.∴147，343，133的最大公约数是7.故每瓶最多装7g.【总结升华】本题关键是分析清楚题意，找出三个数的最大公约数.求三个以上(含三个数)的数的最大公约数时，可依次通过求两个数的最大公约数与第三个数的最大公约数来求得.。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

淄博五中高一级部数学学案
孙天军
编号：课题：1.3.1 算法案例（1）--辗转相除法与更相减损术
授课人：备课时间：授课时间：课型：新授课
学案内容
〖学习目标〗
1．通过算法的典型案例，经历设计算法解决问题的全过程，感受算法解决问题的重要作用；
2．理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析,设计出这两种算法的程序框图并写出它们的算法程序；熟练运用这两种算法求最大公约数．
3．进一步体会算法的基本思想，发展有条理地思考与解决问题的能力，提高逻辑思维能力．
〖重点难点〗随记
重点：掌握辗转相除法与更相减损术求最大公约数的方法．
难点：对辗转相除法与更相减损术的算法的基本思想的理解.
〖导学过程〗
板块一：课前自学
1 ．回顾算法的三种表述：自然语言、程序框图（三种逻辑
结构）、程序语言（五种基本语句）．
2．回顾求两个数的最大公约数的方法．
①24与30的最大公约数．
②求较大的两个数210与462的最大公约数．
板块二：新知探究
1 ．问题提出：当两个数公有的质因数（如8251与6105）
较大时，用原来的显然困难，须改进算法，用什么方法好？
2 ．点拨：辗转相除法是解决上述问题的有效方法之一，
此算法是欧几里得在公元前300左右首先提出的，因而，又
叫欧几里得算法．
3．师生探究：
例1．用辗转相除法求8251与6105的最大公约数．
探究1：用辗转相除法求两个正数225和135的最大公约数．
探究2：辗转相除法算法步骤如何？其蕴含的数学原理是什么？
请画出用辗转相除法求两个数的最大大公约数的程序框图，并编写程序？
4．问题提出：除了用上述算法求两个数的最大公约数之外还有没有别的算法？
5．点拨：用“更相减损术”：更相减损术，是我国数学家刘徽的专著《九章算术》中记载的．更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母分子之数，以少减多，更相减损，求其等也，以等数约之．翻译出来为：
第一步：任意给出两个正数；判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数．
6．师生再探：
例2 ．用更相减损术求91与49的最大公约数．
探究3:怎样用更相减损术求182与98的最大公约数?
探究4:用更相减损术求80与36的最大公约数，并用辗转相除法检验结果．探究5:“更相减损术”蕴含的数学原理是什么？
思考: “辗转相除法”与“更相减损术”的区别是什么？
（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以为主，计算次数上辗转相除法计算次数相对，特别当两个数字大小区别较大时计算次数的区别较明显．
（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为则得到，而更相减损术则以减数与差而得到．
板块三：知识拓展
问题提出：如何求三个正整数的最大公约数？
例3．求三个数175、100、75的最大公约数．
板块四：课堂总结
1．“辗转相除法”与“更相减损术”都是求最大公约数有的效方法；
2．计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显；从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到．
3．求三个以上(含三个数)的数的最大公约数时，可依次通过求两个数的最大公约数与第三数的最大公约数来求得．
板块五：当堂反馈
1．用辗转相除法求294和84的最大公约数时，需要做除法的次数是（）A．2 B．3 C．4 D．5
2．两个整数228和1995的最大公约数是（）
A．38 B．57 C．76 D．171
3．用更相减损术求得78与36 的最大公约数为( )
A．24 B．18 C．12 D．6
4．是我国古代数学专著《》中介绍的一种求两数最大公约数的方法．
5．求三个数324、243、135的最大公约数．
6．求四个数84、108、132，156的最大公约数．
7．利用辗转相除法求3869与6497的最大公约数与最小公倍数．
板块六：分层作业：A层做1—3题；B层做1—2题．
1．（1）36与182的最大公约数为；
（2）1978与2008的最大公约数为；
（3）1624与899的最大公约数为；
（4）204与85的最大公约数为；
2．用辗转相除法求下列两数的最大公约数，并用更相减损术检验你的结果（1）300，2007；（2）5280，12155．
3．求三个数168、56、264的最大公约数．
思考题：请设计用“更相减损术”求两个数的最大大公约数的程序．
板块七：课后学习反思：。