1.3算法案例

输出： 输出：m 结束
PRINT m END
思考：辗转相除法与更相减损术有 什么区别和联系？
区别： 计算上辗转相除法以除法为主，更相减损术以 减法为住； 在计算次数上，辗转相除法计算次数相对较少， 特别当两个数大小差别较大时计算次数的区别 较明显； 从结果输出的时候看，辗转相除法当余数为0 从结果输出的时候看，辗转相除法当余数为0时 输出除数，更相减损术当差和减数相等时输出 差。 联系：都是求最大公约数的方法。因为做一次除法 联系：都是求最大公约数的方法。因为做一次除法 与做若干次减法效果相同，商就是减法的次数， 余数就是最后的差，由此可知二者是完全统一 的！
同理：a,b,c为正整数，若a-b=c，则（a,b）=(b,c)。 同理：a,b,c为正整数， 为正整数 b=c， a,b）=(b,c)。 “更相减损术”（也是求两个正整数的最大公约数的算法） 更相减损术” 也是求两个正整数的最大公约数的算法） 更相减损术 步骤： 步骤： 第一步：任意给定两个正整数；判断他们是否都是偶数。 第一步：任意给定两个正整数；判断他们是否都是偶数。 若是，则用2约简 若不是则执行第二步。 约简； 若是，则用 约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较 第二步：以较大的数减较小的数， 小的数比较，并以大数减小数。继续这个操作， 小的数比较，并以大数减小数。继续这个操作，直到所 得的减数和差相等为止， 得的减数和差相等为止，则这个等数就是所求的最大公 约数。 约数。
讨论：你能根据更相减损术的算法步骤 画出其程序框图并写出程序语句吗? 画出其程序框图并写出程序语句吗?
INPUT m,n
开始 输入： 输入：m,n N m≠n? Y M>n? Y m=m-n N
WHILE m<>n IF m>n THEN m=m-n ELSE n=n-m
n=n-m
END IF WEND
=37
练习：用辗转相除法求下列两数的最大公约数： （1）（225，135） 45 （2）（98，196） 98 24 （3）（72，168） （4）（153，119） 17
思考3：辗转相除直到何时结束？ 思考3 辗转相除直到何时结束？ 主要运用的是哪种算法结构？ 主要运用的是哪种算法结构？
辗转相除法是一个反复执行直到余数等于0停止的步骤， 这实际上是一个循环结构 辗转相除法求两个数的最大公约数，其算法可以描述如下： ① 输入两个正整数m和n； ② 求余数r：计算m除以n，将所得余数存放到变量r中； ③更新被除数和余数：m=n，n=r。 ④判断余数r是否为0：若余数为0则输出结果，否则转 r 向第②步继续循环执行。 如此循环，直到得到结果。
2，4830与3289的最大公约数为_______ 4830与3289的最大公约数为_______ 3，用更相减损术求87与27的最大公约数时， ，用更相减损术求87与27的最大公约数时， 反复相减，直至求出最大公约数，需要进 行减法运算的次数是______ 行减法运算的次数是______ 4，用辗转相除法求87与27的最大公约数，需 ，用辗转相除法求87与27的最大公约数，需 要进行除法运算的次数是_____ 要进行除法运算的次数是_____ 5，46，115，276的最大公约数是____ 46，115，276的最大公约数是____
例3，求三个数319，377，116的最 ，求三个数319，377，116的最 大公约数（计算，不编程）
辗转相除法 更相减损术
练习：
1，下列说法中正确的是（ ） A 辗转相除法是中国古代数学中的算法 B 更相减损术与辗转相除法的算理完全不同 C 辗转相除法与更相减损术相比较，用辗转 相除法求最大公约数最优越 D 辗转相除法与更相减损术，在设计程序时， 都要用到循环结构。
例2、用更相减损术求98与63的最大公约数 用更相减损术求 与 的最大公约数 自己按照步骤求解） （自己按照步骤求解） 由于63不是偶数 不是偶数， 以大数减小数， 解：由于 不是偶数，把98和63以大数减小数，并辗转相减。 和 以大数减小数 并辗转相减。 （98，63） =（63，35） 98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 =（35，28） =（28，7） =（21，7） =（14，7） =（7，7） =
辗转相除法的理论基础: 辗转相除法的理论基础
定理： 已知m,n,r为正整数，若m=nq+r（0≤r<n）（即r=m MOD n）,则（m,n）=(n,r)。
分析：m=nq+r r=m-nq
…… ① …… ②
例1、求8251和6105的最大公约数。 解： （8251，6105） 8251=6105×1+2146 8251=6105 1+2146 =（6105，2146） 6105=2146 ×2+1813 =（2146，1813） 2146=1813 ×1+333 =（1813，333） 1813=333 ×5+148 =（333，148） 333=148 ×2+37 =（148，37） 148=37 ×4
情境创设
韩信是秦末汉初的著名军事家. 韩信是秦末汉初的著名军事家.据说有一次汉高祖 刘邦在卫士的簇拥下来到练兵场, 刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什 么方法,不要逐个报数,就能知道场上的士兵的人数, 么方法,不要逐个报数,就能知道场上的士兵的人数, 韩信先令士兵排成3列纵队,结果有2人多余, 韩信先令士兵排成3列纵队,结果有2人多余,接着 下令排成5列纵队,结果又多出3 下令排成5列纵队,结果又多出3人,随后他又下令 改为7列纵队,这次又剩下2人无法成整行. 改为7列纵队,这次又剩下2人无法成整行.在场的 人都哈哈大笑,以为韩信不能清点出准确的人数, 人都哈哈大笑,以为韩信不能清点出准确的人数,不 料笑声刚落,韩信高声报告共有士兵2333人 料笑声刚落,韩信高声报告共有士兵2333人.众人 听了一楞, 听了一楞,不知道韩信用什么方法这么快就能得到 正确的结果的.今天,我们将以这些古典案例的思想, 正确的结果的.今天,我们将以这些古典案例的思想, 设计出适宜计算机的运行程序, 设计出适宜计算机的运行程序,提高我们对基本算 法结构和算法语句在实际中的运用能力. 法结构和算法语句在实际中的运用能力.
思考4 思考4：你能根据辗转相除法的算法步骤画出它的 程序框图以及相应的程序语句吗? 程序框图以及相应的程序语句吗?
开始 输入： 输入 INPUT m,n ：m,n r=1 r=m MOD n WHILE r<>0 r=m MOD n m=n m=n n=r n=r WEND PRINT m r=0? Y END 输出： 输出：m 结束
探究一, 探究一,辗转相除法
思考2:当两个数的公有质因数较大时 我们怎 思考 当两个数的公有质因数较大时,我们怎 当两个数的公有质因数较大时 样去求两个数的最大公约数呢? 样去求两个数的最大公约数呢 辗转相除法:用于求两个正整数的最大公约数 辗转相除法 用于求两个正整数的最大公约数 的一种算法,是由欧几里得在公元前 是由欧几里得在公元前300年 的一种算法 是由欧几里得在公元前 年 左右首先提出的,因而又叫做欧几里得算法 因而又叫做欧几里得算法. 左右首先提出的 因而又叫做欧几里得算法 定义:所谓的辗转相除法 所谓的辗转相除法,就是对于给定的两个 定义 所谓的辗转相除法 就是对于给定的两个 用较大的数除以较小的数,若余数不为零 数,用较大的数除以较小的数 若余数不为零 用较大的数除以较小的数 若余数不为零, 则将余数和较小的数构成新的数对,继续上 则将余数和较小的数构成新的数对 继续上 面的除法,直到大数被小数除尽 直到大数被小数除尽,则这是较小 面的除法 直到大数被小数除尽 则这是较小 的数就是原来两个数的最大公约数. 的数就是原来两个数的最大公约数
求以下几组正整数的最大公约数。 (注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示 m和n的最大公约数。)
（1）（18，30）6； （2）（24，16） 8； （3）（63，63） （4）（72，8） 8； 63； 7； （5）（301，133 ） 想一想，如何求8251与6105的最大公约数？
N
程序： 程序： INPUT “m，n=”;m,n ， DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
探究二, 探究二,更相减损术
<九章算术> “可半者半之,不可半者,副置分 九章算术> 可半者半之,不可半者,
母、子之数，以少减多，更相减损，求其 子之数，以少减多，更相减损， 等也，以等数约之。” 等也，以等数约之。
开始 输入： 输入：m,n m>n? Y t=m,m=n,n=t i=m+1 i=i-1
穷举法
穷举法（也叫枚举法） 步骤： 从两个数中较小数开始 由大到小列举，直到找到公 约数立即中断列举，得到的 公约数便是最大公约数 。
N
m MOD i=0且n MOD i=0? 且 Y 输出： 输出：i 结束
N
6，下面是求115与276的最大公约数的程序， ，下面是求115与276的最大公约数的程序， 把程序补充完整。 a=115 b=276 DO r=____ a=b b=r LOOP UNTIL r=____ PRINT a END
7，用辗转相除法求176与121的最大公约数， ，用辗转相除法求176与121的最大公约数， 并写出其程序。
探究一, 探究一,辗转相除法
思考1:在小学中我们是如何求出两个正整数 思考 在小学中我们是如何求出两个正整数 的最大公约数的呢? 的最大公约数的呢
算法案例之求最大公约数
例、求18与24的最大公约数： 解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：2×3＝6 短除法