第12课时5.4.2算法案例二(最大公约数)已对
第12课时 5.4 算法案例
重点难点
重点：通过案例分析理解辗转相除法与更相减损术求最大公约数的方法，体会算法思想。 难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言.
学习要求
1．理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分
析。
2．基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序.
【课堂互动】
问题：
写出求两个正整数a,b(a>b)的最大公约数的一个算法。 1.辗转相除法
公元前3世纪，欧几里得介绍了求两个正整数a,b(a>b)的最大公约数的方法，求出一列数：0,,,,,,121n n r r r r b a - ，这列数从第三项开始，每一项都是前两项相除所得的余数（即),(12--=n n n r r Mod r ），余数等于0的前一项n r ，即是a 和b 的最大公约数，这种方法称为“欧几里得辗转相除法”。 例1 求两个正数8251和6105的最大公约数．
（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数） 【解】8251＝6105×1＋2146
显然8251和2146的最大公约数也必是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的最大公约数． 【小结】以上我们求最大公约数的方法就是欧几里得辗转相除法．其求最大公约数的步
骤如下： 第一步：用较大的数m 除以较小的数n 得到一个商0q 和一个余数0r ； 第二步：若00r =，则n 为,m n 的最大公约数；若00r ≠，则用除数n 除以余数0r 得到一个商1q 和一个余数1r ；
第三步：若10r =，则1r 为,m n 的最大公约数；若10r ≠，则用除数0r 除以余数1r 得到一个商2q 和一个余数2r ；
……
依次计算直至0n r =，此时所得到的1n r -即为所求的最大公约数. 【练习】求a=204，b=85的最大公约数，步骤为： S1 S2 S3
所以它们的最大公约数为 。
算法描述：计算出a ÷b 的余数r ，若r=0，则b 为a ，b 的最大公约数；若r ≠0，则把前面的除数b 作为新的被除数，把余数r 作为新的除数（a ，b 要重新赋值，a ←b ，b ←r ），继续进行上述运算，直到余数为0(用While 循环语句，循环的执行条件是r ≠0，当r=0时，循环终止)，此时的除数即为所求的最大公约数。
算法如下:
S1 输入两个正整数a,b(a>b)；
S2 若Mod(a ，b)=0，则转S3；否则，r ←Mod(a,b)， a ←b ，b ←r ，转S2。 S3 输出最大公约数b ； 【流程图】
【伪代码】
2. 更相减损法
我国早期也有解决求最大公约数问题的算法，就是更相减损术．
更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母之数，以少减多，更相减损，求其等也，以等数约之．
翻译出来为：
第一步：任意给出两个正数；判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数．
再从这个角度看一下“求a=204，b=85
的最大公约数”的问题，S1步可以等价为等式：34285204+?=。S2步可以等价为等式：1723485+?=。这两步从减法的角度可以理解为：204-85，所得的差与减式中的较小数比较，再用大的数减小的数，循环执行以上步骤,直到结果为0。此时减数就是a 和b 的最大公约数。这一算法根据它的特点，也可以用循环语句完成。
参考代码：
/a 放较大的数，b 放较小的数 If a < b Then m ← a a ← b
b ← m /交换a ，b 中的数
End If /确保a 是a ，b 中较大的数 r ← a – b /两数相减 While r ≠ 0 If b > r Then a ← b b ← r Else a ← r End If
r ← a – b
/确保相减后仍用较大的数减去较小的数 End While Print b
用“更相减损法”求多于两个数的最大公约数就可以显示出其优越性
【小结】比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显． （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到．
【追踪训练】
1.分析下面一段代码的目的： Read m,n
While m/n ≠Int(m/n) c ←m- Int(m/n)×n m ←n n ←c
End While Print n
(Int(x)表示不超过x 的最大整数)
Read a,b
While Mod(a,b)≠0 r ←Mod(a,b) a ←b b ←r End While Print b
开始 b ←r Y
N 结束
输入a ，b
a ←
b r ←Mod(a,b) Mod(a,b) ≠0
输出b
【解】。
2.用辗转相除法求下列各组数的最大公约数。
（1）225；135 （2）98；196
3.用更相减损法求下列各组数的最大公约数。
（31）72；168 （2）153；119
4. 现有长度为360cm和780cm两种规格的钢筋若干.要焊接一批正方形模型.问怎样才能保证正方体体积最大且不浪费?
思路点拨: 正方体的所有棱长都相等,故必须将钢筋剪裁成长度相等的钢筋条;又必须不浪费,这就说明必须剪后无剩余.于是为了保证正方体的体积最大,故剪的钢筋的最大长度为360cm和780cm的最大公约数,可用更相减损术求最大公约数.
【解】
最大公约数的三种算法 复杂度分析 时间计算
昆明理工大学信息工程与自动化学院学生实验报告 （2011 —2012 学年第 1 学期） 课程名称：算法设计与分析开课实验室：信自楼机房444 2011 年10月 12日 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 实验采用三种方法求最大公约数
1、连续整数检测法。 2、欧几里得算法 3、分解质因数算法 根据实现提示写代码并分析代码的时间复杂度： 方法一： int f1(int m,int n) { int t; if(m>n)t=n; else t=m; while(t) { if(m%t==0&&n%t==0)break; else t=t-1; } return t; } 根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2; 方法二：int f2(int m,int n) { int r; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } 根据代码辗转相除得到欧几里得的O(n)= log n 方法三： int f3(int m,int n) { int i=2,j=0,h=0; int a[N],b[N],c[N]; while(i § 13．3 算法案例 一、知识导学 1．算法设计思想： （1）“韩信点兵—孙子问题”对正整数m 从2开始逐一检验条件，若三个条件中有任何一个不满足，则m 递增1，一直到m 同时满足三个条件为止(循环过程用Goto 语句实现) （2）用辗转相除法找出b a .的最大公约数的步骤是：计算出b a ÷的余数r ，若0=r ，则b 为b a ,的最大公约数；若0≠r ，则把前面的除数b 作为新的被除数，继续运算，直到余数为0，此时的除数即为正整数b a ,的最大公约数. 2.更相减损术的步骤：（1）任意给出两个正数，判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.（2）以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数. （3）二分法求方程0)(=x f 在区间[]b a ,内的一个近似解*x 的解题步骤可表示为 S1 取[b a ,]的中点()b a x += 2 10，将区间 一分为二； S2 若()00=x f ，则0x 就是方程的根；否则判别根*x 在0x 的左侧还是右侧： 若()()00>?x f a f ，()b x x ,*0∈，以0x 代替a ； 若()()00 1.3算法案例---秦九韶算法 1、利用秦九韶算法求多项式1153723+-+x x x 在23=x 的值时，在运算中下列哪个值用不到（ ） A 、164 B 、3767 C 、86652 D 、85169 2、利用秦九韶算法计算多项式1876543x f(x )23456++++++x x x x x ＝ 当x=4的值的时候，需要做乘法和加法的次数分别为（ ） A 、6，6 B 、5，6 C 、5，5 D 、6，5 3、利用秦九韶算法求多项式1352.75.38123)(23456-++-++=x x x x x x x f 在6=x 的值，写出详细步骤。 4、下图的框图是一古代数学家的一个算法的程序框图，它输出的 结果s 表示（ ） A 、3210a a a a +++的值 B 、300201032x a x a x a a +++的值 C 、303202010x a x a x a a +++的值 D 、以上都不对 5、已知n 次多项式1011()n n n n n P x a x a x a x a --=++++, 如果在一种算法中，计算0k x （k ＝2，3，4，…，n ）的值需要k －1次 乘法， （1）计算30()P x 的值需要9次运算（6次乘法，3次加法），那么计算0()n P x 的值需要多少次运算？ （2）若采取秦九韶算法：0011(),()()k k k P x a P x xP x a ++==+（k ＝0， 1，2，…， n －1），计算30()P x 的值只需6次运算，那么计算0()n P x 的值共需要多少次运算？ （3）若采取秦九韶算法，设a i =i+1，i=0，1，…，n ，求P 5（2）（写出采取秦九韶算法的计算过程） . 1、查找约数法． 先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数，其中最大的一个就是最大公约数． 例如，求12和30的最大公约数． 12的约数有：1、2、3、4、6、12； 30的约数有：1、2、3、5、6、10、15、30． 12和30的公约数有：1、2、3、6，其中6就是12和30的最大公约数． 2 更相减损术 《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。 3、辗转相除法． 当两个数都较大时，采用辗转相除法比较方便．其方法是： 以小数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数． 例如：求4453和5767的最大公约数时，可作如下除法． 5767÷4453＝1余1314 4453÷1314＝3余511 1314÷511＝2余292 511÷292＝1余219 292÷219＝1余73 219÷73＝3 于是得知，5767和4453的最大公约数是73． 辗转相除法适用比较广，比短除法要好得多，它能保证求出任意两个数的最大公约数．4、求差判定法． 如果两个数相差不大，可以用大数减去小数，所得的差与小数的最大公约数就是原来两个数的最大公约数．例如：求78和60的最大公约数．78－60＝18，18和60的最大公约数是6，所以78和60的最大公约数是6． 如果两个数相差较大，可以用大数减去小数的若干倍，一直减到差比小数小为止，差和小数的最大公约数就是原来两数的最大公约数．例如：求92和16的最大公约数．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公约数是4，所以92和16的最大公约数就是4． 5、分解因式法． 先分别把两个数分解质因数，再找出它们全部公有的质因数，然后把这些公有质因数相乘，得到的积就是这两个数的最大公约数． 例如：求125和300的最大公约数．因为125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公约数是5×5＝25． 6、短除法． 为了简便，将两个数的分解过程用同一个短除法来表示，那么最大公约数就是所有除数的乘积． 例如：求180和324的最大公约数． 因为： 5和9互质，所以180和324的最大公约数是4×9＝36． 7、除法法． 当两个数中较小的数是质数时，可采用除法求解．即用较大的数除以较小的数，如果能够整除，则较小的数是这两个数的最大公约数． 例如：求19和152，13和273的最大公约数．因为152÷19＝8，273÷13＝21．（19和13都是质数．）所以19和152的最大公约数是19，13和273的最大公约数是13． 算法案例 知识讲解 一、更相减损术 1.概念：求两个整数的最大公约数的算法. 2.步骤：以两个数中较大的数减去较小的数，以差数和较小的数构成一对新的数，对这一对数再用大数减小数，以同样的操作一直做下去，直到产生一对相等的数，此数就是这两个数的最大公约数． 3.等值算法：用“更相减损术”设计出来的算法求最大公约数的算法称为“等值算法”，用等值算法可以求任意两个正整数的最大公约数． 4.原理：《九章算法》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数．以具体的例子来说明更相减损术求最大公约数的原理：以求117和182的最大公约数为例：(117182)(11765)(6552)(5213)(1339)(1326)(1313)，，，，，，，， →→→→→→ 每次操作后得到的两个数与前两个数的最大公约数相同，而且逐渐减少，故总能得到相等的两个数，即为所求的最大公约数． 二、辗转相除法 1.概念：辗转相除法又称欧几里得算法，是由欧几里得在公元前300年左右首先提出来的求两个数的最大公约数的算法． 2.步骤：对于给定的两个数，以其中较大的数除以较小的数得到一个余数，将较小的数与余数看成一对新的数，重复上面的步骤，直到余数为零为止，此时上一步中较小的数即为所求的最大公约数． 如：(117182)(11765)(6552)(5213)(130) ，，，，，,故13即为所求． →→→→ 三、秦九韶算法 1.用途：秦九韶算法求多项式的值 2.具体内容：已知一个多项式函数，计算多项式在某点处的函数值的一种算法，是我国古 代数学家秦九韶提出的，具体如下： 对任意一个n 元多项式1110()n n n n f x a x a x a x a --=++++， 改写成如下形式：12110()()n n n n f x a x a x a x a ---=++ ++ 231210(())n n n n a x a x a x a x a ---=++ +++ = 1210((()))n n n 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 个一次多项式的值． 令1(1)(())k n n n k n k v a x a x a x a ----=++++，则递推公式为01n k k n k v a v v x a --=??=+?, 其中12k n =，，，． 到目前为止，此算法仍然是世界上多项式求值的最先进的算法． 3.秦九韶算法与其它算法的比较：1110()n n n n f x a x a x a x a --=++ ++， （1）直接求和法：先计算各个单项式的值，再把它们相加，乘法次数为 (1) (1)212 n n n n ++-+++= ，加法次数n ； （2）逐项求和法：先计算x 的各项幂的值，再分别相乘，计算幂值需要乘法1n -次，将幂值与多项式系数k a 相乘需要乘法n 次，故共需要乘法21n -次，加法n 次． 注：此方法对直接求和法有所改进，但仍然比秦九韶算法计算量大很多． （3）秦九韶算法：计算量仅为乘法n 次，加法n 次． 4.秦九韶算法的特点： 1）化高次多项式求值为一次多项式求值； 2）减少了运算次数，提高了效率； 3）步骤重复执行，容易用计算机实现． 注意：利用秦九韶算法计算多项式的值关键是能正确地将所给多项式改写，然后由内向外逐 算法设计与分析 11信本余启盛 118632011004 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图 （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件matlab .2008 四、实验方法、步骤（或：程序代码或操作过程） 实验采用三种方法求最大公约数 1、连续整数检测法。 2、欧几里得算法 3、蛮力法（短除法） 根据实现提示写代码并分析代码的时间复杂度： 算法一：连续整数检测法。 CommFactor1 输入：两个自然数m和n 输出：m和n的最大公约数 1.判断m和n哪个数小，t=min（m，n） 2.如果m%t==0&&n%t==0 ，结束 2.1 如果t不是m和n的公因子，则t=t-1; 3. 输出t ; 根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2; 算法二：欧几里德算法 CommFactor2 输入：两个自然数m和n 输出：m和n的最大公约数 1. r = m % n; 2. 循环直到r 等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3. 输出n ; 根据代码辗转相除得到欧几里得的: O(n)= log n 算法三：蛮力法（短除法） CommFactor3 输入：两个自然数m和n 输出：m和n的最大公约数 1.factor=1； 2.循环变量i从2-min（m，n），执行下述操作： 2.1 如果i是m和n的公因子，则执行下述操作： 2.1.1 factor=factor*i； 2.1.2 m = m / i; n = n / i; 2.2 如果i不是m和n的公因子，则i=i+1； 3. 输出factor； 根据代码考虑最坏情况他们的最大公约数，循环做了i-1次;最好情况是只做了1次，可以得出: O（n）=n/2; MATLAB程序代码： main.m x=fix(rand(1,1000)*1000); y=fix(rand(1,1000)*1000); for i=1:1000 A(i)=CommFactor2(x(i),y(i)); end x=x'; y=y'; 题组一 选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度高低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）16．最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 18.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 31、下列算法中不能解决0/1背包问题的是（A ） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 32、回溯法搜索状态空间树是按照（C ）的顺序。 A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历 34．实现合并排序利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 40、背包问题的贪心算法所需的计算时间为（ B ） A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）填空题 1.算法的复杂性有时间复杂性和空间复杂性之分。 2、程序是算法用某种程序设计语言的具体实现。 3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。 4.矩阵连乘问题的算法可由动态规划设计实现。 高中数学例题：秦九韶算法 例4．利用秦九韶算法求2345()10.50.166630.041680.00835f x x x x x x =+++++在x=0.2时的值．写出详细计算过程． 【思路点拨】秦九韶算法是我国南宋的数学家秦九韶首先提出来的． （1）特点：它通过一次式的反复计算，逐步计算高次多项式的求值问题，即将一个n 次多项式的求值问题，归结为重复计算n 个一次式1()i i a x a -+．即1210()((()))n n n f x a x a x a x a x a --=++++． （2）具体方法如下：已知一个一元n 次多项式1110()n n n n f x a x a x a x a --=++++0．当x=x 0，我们可按顺序一项一项地计算，然后相加，求得0()f x ． 【答案】1.2214024 【解析】 v 0=0.00835， v 1=v 0x+0.04168=0.00835×0.2+0.04168=0.043 35， v 2=v 1x+0.16663=0.04335×0.2+0.16663=0.1753， v 3=v 2x+0.5=0.1753×0.2+0.5=0.53506， v 4=v 3x+1=0.53506×0.2+1=1.107012， v 5=v 4x+1=1.107012×0.2+1=1.2214024． 【总结升华】秦九韶算法的原理是 01(1,2,3,,) n k k n k v a v v x a k n --=??=+=?． 在运用秦九韶算法进行计算时，应注意每一步的运算结果，像这 种一环扣一环的运算，如果错一步，则下一步，一直到最后一步就会 全部算错．同学们在计算这种题时应格外小心． 举一反三： 【变式1】用秦九韶算法求多项式764 =++++当x=2时 f x x x x x ()85321 的值． 【答案】1397 【解析】 765432 =++?++?+?++=+++++++ ()85030021((((((85)0)3)0)0)2)1 f x x x x x x x x x x x x x x x ． v0=8， v1=8×2+5=21， v2=21×2 4-0=42， v3=42×2 4-3=87， v4=87×2+0=174， v5=174×2+0=348， v6=348×2+2=698， v7=698×2+1=1397， 所以，当x=2时，多项式的值为1397． 【变式2】用秦九韶算法计算多项式65432 f x x x x x x x =++++++ ()654327 在x=0.4时的值时，需做加法和乘法的次数和是（） A．10 B．9 C．12 D．8 【答案】 C Java算法最大公约数和最小公倍数 题目：输入两个正整数m和n，求其最大公约数和最小公倍数。 1.程序分析：利用辗除法。 最大公约数： public class CommonDivisor{ public static void main(String args[]) { commonDivisor(24,32); } static int commonDivisor(int M, int N) { if(N<0||M<0) { System.out.println("ERROR!"); return -1; } if(N==0) { System.out.println("the biggest common divisor is :"+M); return M; } return commonDivisor(N,M%N); } } 最小公倍数和最大公约数： import java.util.Scanner; public class CandC { //下面的方法是求出最大公约数 public static int gcd(int m, int n) { while (true) { if ((m = m % n) == 0) return n; if ((n = n % m) == 0) return m; } } public static void main(String args[]) throws Exception { //取得输入值 //Scanner chin = new Scanner(System.in); //int a = chin.nextInt(), b = chin.nextInt(); int a=23; int b=32; int c = gcd(a, b); System.out.println("最小公倍数：" + a * b / c + "\n最大公约数：" + c); } } 理工大学信息工程与自动化学院学生实验报告 （2011 —2012 学年第 1 学期） 课程名称：算法设计与分析开课实验室：信自楼机房444 2011 年10月 12日 一、上机目的及容 1.上机容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 实验采用三种方法求最大公约数 1、连续整数检测法。 根据实现提示写代码并分析代码的时间复杂度： 方法一： int f1(int m,int n) { int t; if(m>n)t=n; else t=m; while(t) { if(m%t==0&&n%t==0)break; else t=t-1; } return t; } 根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2; 方法二：int f2(int m,int n) { int r; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } 根据代码辗转相除得到欧几里得的O(n)= log n 方法三： int f3(int m,int n) { int i=2,j=0,h=0; int a[N],b[N],c[N]; while(i 【推荐】江苏省13大市2013年高三历次考试数学试题分类汇编13：算法初步 一、填空题 1 ．（连云港市2012-2013学年度第一学期高三期末考试数学试卷）右图是一个算法流程图, 若输入x的值为-4,则输出y的值为__. 【答案】2 2 ．（南京市、 盐城市2013届高三年级第一次模拟考试数学试题）如图所示是一算法的伪代码, 执行此算法时, 输出的结果是 . 【答案】3 (第6题 3 ．（江苏省无锡市2013届高三上学期期末考试数学试卷）右边的程序语句运行后,输出的 S 为____________. 【答案】17 4 ．（南通市2013届高三第一次调研测试数学试卷）已知实数x ∈[1,9],执行如右图所示的 流程图,则输出的x 不小于55的概率为________. 【答案】答案:38. 本题主要考查算法及几何概型等知识. 法一 当输入x =1时,可输出x =15;当输入x =9时,可输出y =79.于是当输入x 的取值范围为[1,9]时,输出x 的取值范围为[15,79],所求概率为 7955379158-=-. 法二 输出值为87x +.由题意:8755x +≥,故69x ≤≤. 开始 结束 Y n ←1 输入x 输出x n ← x ←2x +1 n ≤3 N （第8 5 ．（扬州、南通、泰州、宿迁四市2013届高三第二次调研测试数学试卷）根据如图所示 的伪代码,最后输出的S 的值为____. 【答案】145 6 ．（常州市2013届高三教学期末调研测试数学试题）根据右图所示的算法,可知输出的结 果为______. [来源:https://www.wendangku.net/doc/f9759716.html,] 【答案】11 7 ．（江苏省苏锡常镇四市2013届高三教学情况调研(一)数学试题）根据右图的伪代码,输 出的结果T 为______. 0 1023 21 Pr int n S n While S S S n n End While n ++ ≤ ←←0 ←←4(第题)S ←0 For I From 1 to 28 （第6 基本算法——辗转相除法 问题：输出两个正整数a,b,且0 改进——已知整数a,b及其最大公约数p,则直接可推算出最小公倍数q： q= a*b/p; 源程序2 #include 2019-2020年高中数学第五章第13课时《算法案例三》教案（学生版）苏 教版必修3 重点难点 重点：理解区间二分法的意义,学会分析类似的问题；通过案例分析，体会算法思想， 难点：理解二分法的算法思想和算法表示 学习要求 1．理解区间二分法的意义,二分法主要是采用了循环结构处理问题要会分析类似的问题； 2．能由流程图分析出期所含有的结构并用为代码表示出相应的算法． 3.GoTo语句的认识及其他语句的进一步熟悉 【课堂互动】 问题：用区间二分法写出方程在区间[1，1.5]内的一个近似解（误差不超过0.001）的一个算法。 【算法设计思想】 令函数.如图，如果估计出方程在某区间内有一个根，就能用二分法搜索求得符合误差限制的近似解． 取[a，b]的中点，如果f()=0，那么就是方程的根；否则判断根在的左侧还是右侧，如果在左侧，就用[a，]代替区间 [a，b]。如果在右侧，就用[，b]代替区间[a，b]，如此循环下去，直到|a-b| 10 Read 20 30 40 50 If Then GoTo 120 60 If Then 70 80 Else 90 100 End If 110 If Then GoTo 20 120 Print 【追踪训练】 1.在直角坐标系中作出函数和的图象,根据图象判断方程的解的范围,再用二分法求这个方程的近似解(误差不超过0.001),并写出这个算法的伪代码,画出流程图。 【解】由图像可知方程有一个根在[1，2]内。a←1 b←2 c←0.001 While ≥c ←(a+b)/2 ← ← If =0 Then Exit While If ＜0 Then b← Else a← End If End While Print 流程图如下: C语言求最大公约数和最小公倍数算法假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。 1、辗转相除法 辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： a b=0 gcd(a,b) = gcd(b,a mod b) b!=0 根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下： ①、函数嵌套调用 其算法过程为：前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数 1、大数放a中、小数放b中； 2、求a/b的余数； 3、若temp=0则b为最大公约数； 4、如果temp!=0则把b的值给a、temp的值给a； 5、返回第第二步； 代码： int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ { int temp; /*定义整型变量*/ if(a C语言求最大公约数和最小公倍数算法 C语言求最大公约数和最小公倍数可以说是C语言编程学习中一个重点和难点，它常常作为计算机专业学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据数学定义法、递归调用法等。下面结合我学习以来的笔记整理、总结几种常用的方法进行比较，以便能够更好的理解、应用、共勉。 前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。 1、辗转相除法 辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： a b=0 gcd(a,b) = gcd(b,a mod b) b!=0 根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下： ①、函数嵌套调用 其算法过程为：前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数 1、大数放a中、小数放b中； 2、求a/b的余数； 3、若temp=0则b为最大公约数； 4、如果temp!=0则把b的值给a、temp的值给a； 5、返回第第二步； 代码： int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ { int temp; /*定义整型变量*/ if(a 13.4 课题学习最短路径问题 1．最短路径问题 (1)求直线异侧的两点与直线上一点所连线段的和最小的问题，只要连接这两点，与直线的交点即为所求． 如图所示，点A，B分别是直线l异侧的两个点，在l上找一个点C，使CA＋CB最短，这时点C是直线l与AB的交点． (2)求直线同侧的两点与直线上一点所连线段的和最小的问题，只要找到其中一个点关于这条直线的对称点，连接对称点与另一个点，则与该直线的交点即为所求． 如图所示，点A，B分别是直线l同侧的两个点，在l上找一个点C，使CA＋CB最短，这时先作点B关于直线l的对称点B′，则点C是直线l与AB′的交点． 为了证明点C的位置即为所求，我们不妨在直线上另外任取一点C′，连接AC′，BC′，B′C′，证明AC＋CB＜AC′＋C′B.如下：证明：由作图可知，点B和B′关于直线l对称， 所以直线l是线段BB′的垂直平分线． 因为点C与C′在直线l上， 所以BC＝B′C，BC′＝B′C′. 在△AB′C′中，AB′＜AC′＋B′C′， 所以AC＋B′C＜AC′＋B′C′， 所以AC＋BC＜AC′＋C′B. 【例1】在图中直线l上找到一点M，使它到A，B两点的距离和最小． 分析：先确定其中一个点关于直线l的对称点，然后连接对称点和另一个点，与直线l的交点M即为所求的点． 解：如图所示：(1)作点B关于直线l的对称点B′； (2)连接AB′交直线l于点M. (3)则点M即为所求的点． 点拨：运用轴对称变换及性质将不在一条直线上的两条线段转化到一条直线上，然后用“两点之间线段最短”解决问题. 2.运用轴对称解决距离最短问题 运用轴对称及两点之间线段最短的性质，将所求线段之和转化为一条线段的长，是解决距离之和最小问题的基本思路，不论题目如何变化，运用时要抓住直线同旁有两点，这两点到直线上某点的距离和最小这个核心，所有作法都相同． 警误区利用轴对称解决最值问题应注意题目要求根据轴对称的性质、利用三角形的三边关系，通过比较来说明最值问题是常用的一种方法．解决这类最值问题时，要认真审题，不要只注意图形而忽略题意要求，审题不清导致答非所问． 3．利用平移确定最短路径选址 选址问题的关键是把各条线段转化到一条线段上．如果两点在一条直线的同侧时，过两点的直线与原直线的交点处构成线段的差最大，如果两点在一条直线的异侧时，过两点的直线与原直线的交点处构成的线段的和最小，都可以用三角形三边关系来推理说明，通常根据最大值或最小值的情况取其中一个点的对称点来解决．解决连接河两岸的两个点的最短路径问题时，可以通过平移河岸 实验九 一、实验内容 教材3.9 定义递归函数实现下面的Ackman函数 n+1 m=0 Acm(m,n)= Acm(m-1,1) n=0 Acm(m-1,Acm(m,n-1)) n>0,m>0 教材3.10 用递归法实现勒让德多项式： 1 n=0 Pn= x n=1 ((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n 教程p24 使用欧几里得算法计算两个数的最大公约数，分别用递推和递归两种算法实现 教程p26 编程：将上题以多文件方式组织，在area.h中声明各个area（）函数原型，在area.cpp文件中定义函数，然后在Exp9_2中包含area.h,定义main（） 函数并执行。 二、实验目的 1、掌握函数的嵌套调用好递归调用 2、掌握递归算法 3、了解内联函数、重载函数、带默认参函数的定义及使用方法 4、掌握程序的多文件组织 5、掌握编译预处理的内容，理解带参数宏定义与函数的区别 三、实验步骤 教材3.9 定义递归函数实现下面的Ackman函数 n+1 m=0 Acm(m,n)= Acm(m-1,1) n=0 Acm(m-1,Acm(m,n-1)) n>0,m>0 教材3.10用递归法实现勒让德多项式： 1 n=0 Pn= x n=1 ((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n 教程p24 使用欧几里得算法计算两个数的最大公约数，分别用递推和递归两种算法实现 教程p26 编程：将上题以多文件方式组织，在area.h中声明各个area（）函数原型，在area.cpp文件中定义函数，然后在Exp9_2中包含area.h,定义main（） 函数并执行。 四、实验数据及处理结果 第二课时 1.3.2 算法案例---秦九韶算法 教学要求：了解秦九韶算法的计算过程，并理解利用秦九韶算法可以 减少计算次数、提高计算效率的实质；理解数学算法与计算机算法的 区别，理解计算机对数学的辅助作用. 教学重点：秦九韶算法的特点及其程序设计. 教学难点：秦九韶算法的先进性理解及其程序设计. 教学过程： 一、复习准备： 1. 分别用辗转相除法和更相减损术求出两个正数623和1513的最大 公约数. 2. 设计一个求多项式5432 x=时的值的 ()254367 =--+-+当5 f x x x x x x 算法. （学生自己提出一般的解决方案：将5 x=代入多项式进行计算 即可） 提问：上述算法在计算时共用了多少次乘法运算？多少次加法运算？ 此方案有何优缺点？(上述算法一共做了5＋4＋3＋2＋1＝15次乘法 运算，5次加法运算. 优点是简单、易懂；缺点是不通用，不能解决 任意多项式的求值问题，而且计算效率不高.) 二、讲授新课： 1. 教学秦九韶算法： ①提问：在计算x的幂值时，可以利用前面的计算结果，以减少计 算量，即先计算2x，然后依次计算2x x?，2() ??，2 x x x ???的值， x x x x (()) 这样计算上述多项式的值，一共需要多少次乘法，多少次加法?（上 述算法一共做了4次乘法运算，5次加法运算） ②结论：第二种做法与第一种做法相比，乘法的运算次数减少了， 因而能提高运算效率，而且对于计算机来说，做一次乘法所需的运算 时间比做一次加法要长得多，因此第二种做法能更快地得到结果. ③更有效的一种算法是： 将多项式变形为： ， 5432 =--+-+= ()254367 f x x x x x x 依次计算2555 ?-=， ?+=，10856534 ?-=，55421 ?-=，2153108 ?+= 534572677 故(5)2677 f=. ――这种算法就是“秦九韶算法”. （注意变形，强 调格式） ④练习：用秦九韶算法求多项式432 x=时的 =+-++当4 f x x x x x ()2351 值. C语言求最大公约数和最小公倍数算法总结单位：隆回县职业中等专业学校作者：刘小华 摘要：介绍自己通过学习使用C语言求任意两个数的最大公约数和最小公倍数的基本算法思想、算法过程、代码实现以及分析比较。 关键词：C语言算法最大公约数最小公倍数 中图分类号：TP312 文献标识码：A C语言求最大公约数和最小公倍数可以说是C语言编程学习中一个重点和难点，它常常作为计算机专业学生参加各种考试必须要把握的内容。其算法方面除常用的辗转相除法外、还可以根据数学定义法、递归调用法等。下面结合我学习以来的笔记整理、总结几种常用的方法进行比较，以便能够更好的理解、应用、共勉。 前提：假设求任意两个整数的最大公约数和最小公倍数，采用函数调用形式进行。 1、辗转相除法 辗转相除法（又名欧几里德法）C语言中用于计算两个正整数a,b的最大公约数和最小公倍数，实质它依赖于下面的定理： a b=0 gcd(a,b) = gcd(b,a mod b) b!=0 根据这一定理可以采用函数嵌套调用和递归调用形式进行求两个数的最大公约数和最小公倍数,现分别叙述如下： ①、函数嵌套调用 其算法过程为：前提：设两数为a,b设其中a 做被除数,b做除数，temp为余数 1、大数放a中、小数放b中； 2、求a/b的余数； 3、若temp=0则b为最大公约数； 4、如果temp!=0则把b的值给a、temp的值给a； 5、返回第第二步； 代码： int divisor (int a,int b) /*自定义函数求两数的最大公约数*/ { int temp; /*定义整型变量*/ if(a高中必修1-5错误解题分析系列-《13.3 算法案例》
秦九韶算法习题
最大公约数的算法
算法案例 - 简单 - 讲义
matlab最大公约数 三种算法
13计科算法设计汇总
高中数学例题：秦九韶算法
Java算法最大公约数和最小公倍数
最大公约数的三种算法复杂度分析时间计算
13：算法初步
C语言算法——最大公约数
2019-2020年高中数学 第五章 第13课时《算法案例三》教案(学生版) 苏教版必修3
最大公约数和最小公倍数算法
C语言求最大公约数和最小公倍数算法
13.4 最短路径问题例题与讲解
c++,使用欧几里得算法计算两个数的最大公约数,分别用递推和递归两种算法实现5
人教版高中数学必修三(教案)1.3 秦九韶算法
C语言求最大公约数