1.算法-最大公约数的三种算法
昆明理工大学信息工程与自动化学院学生实验报告
（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软件
四、实验方法、步骤（或：程序代码或操作过程）
实验采用三种方法求最大公约数
源代码
#include
#include
#include
#include
#include
int xiangchu(int m,int n);
int xiangjian(int m,int n);
int qiongju(int m,int n);
int duanchu(int m,int n);
void main()
{
double t1,t2,t3,t4,t5,t6;
int m,n;
int i=0;
double usetime1,usetime2,usetime3;
time_t start, end;
printf("请输入两个数:");
scanf("%d%d",&m,&n);
printf("相除法求最大公约数:%d\n",xiangchu(m,n)); t1=clock();
while(i<1000000)
{
xiangchu(m,n);
i++;
}
t2=clock();
usetime1 = t2-t1;
printf("It takes %.f*10^(-6)\n",usetime1);
printf("相减法求最大公约数:%d\n",xiangjian(m,n)); t3=clock();
while(i<1000000)
{
xiangchu(m,n);
i++;
}
t4=clock();
usetime2 = t4-t3;
printf("It takes %.f*10^(-6)\n",usetime2);
printf("短除法求最大公约数:%d\n",duanchu(m,n)); t5=clock();
while(i<1000000)
{
xiangchu(m,n);
i++;
}
t6=clock();
usetime3 = t6-t5;
printf("It takes %.f*10^(-6)\n",usetime3); }
int xiangchu(int m,int n)
{//辗转相除法
int c;
c=m%n;
while(c!=0)
{
m=n;
n=c;
c=m%n;
}
return n;
}
int xiangjian(int m,int n)//相减法
{
while(m!=n)
{
if(m>n)
m-=n;
else
n-=m;
}
return n;
}
int duanchu(int m,int n)//短除法{
int i,factor=1;
for(i=2;i<=m && i<=n;i++)
{
while (m%i==0 && n%i==0)
{
factor=factor*i;
m=m/i;
n=n/i;
}
}
return factor;
}
五、实验过程原始记录( 测试数据、图表、计算等)
六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）
该次实验让我知道了求最大公约的不同种算法，除了以上三种，还有分解质因法和连续整数检测法，也让我学习到了更多的内容，但是唯一不足的地方就是算时间复杂度和空间复杂度我还是不怎么熟悉，还是要多加联系才能提高。
注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。
最大公约数的三种算法 复杂度分析 时间计算
昆明理工大学信息工程与自动化学院学生实验报告 （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 . 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． 算法设计与分析 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 甲班有42名学生，乙班有48名学生，现在要把这两个班的学生平均分成若干个小组，并且使每个小组都是同一个班的学生。每个小组最多有多少名学生？（适于六年级程度） 解：要使每个小组都是同一个班的学生，并且要使每个小组的人数尽可能多，就要求出42和48的最大公约数： 2×3=6 42和48的最大公约数是6。 答：每个小组最多能有6名学生。 例2 有一张长150厘米、宽60厘米的长方形纸板，要把它分割成若干个面积最大，井已面积相等的正方形。能分割成多少个正方形？（适于六年级程度） 解：因为分割成的正方形的面积最大，并且面积相等，所以正方形的边长应是1 50和60的最大公约数。 求出150和60的最大公约数： 2×3×5=30 150和60的最大公约数是30，即正方形的边长是30厘米。 看上面的短除式中，150、60除以2之后，再除以3、5，最后的商是5和2。这说明，当正方形的边长是30厘米时，长方形的长150厘米中含有5个30厘米，宽6 0厘米中含有2个30厘米。 所以，这个长方形能分割成正方形： 5×2=10（个） 答：能分割成10个正方形。 例3 有一个长方体的方木，长是3.25米，宽是1.75米，厚是0.75米。如果将这块方木截成体积相等的小正方体木块，并使每个小正方体木块尽可能大。小木块的棱长是多少？可以截成多少块这样的小木块？（适于六年级程度） 解：3.25米=325厘米，1.75米=175厘米，0.75米=75厘米，此题实际是求325、175和75的最大公约数。 5×5=25 325、175和75的最大公约数是25，即小正方体木块的棱长是25厘米。 因为75、175、325除以5得商15、35、65，15、35、65再除以5，最后的商是3、7、13，而小正方体木块的棱长是25厘米，所以，在75厘米中包含3个25厘米，在175厘米中包含7个25厘米，在325厘米中包含13个25厘米。 可以截成棱长是25厘米的小木块： 3×7×13=273（块） 答：小正方体木块的棱长是25厘米，可以截成这样大的正方体273块。 例4 有三根绳子，第一根长45米，第二根长60米，第三根长75米。现在要把三根长绳截成长度相等的小段。每段最长是多少米？一共可以截成多少段？（适于六年级程度） 最大公约数和最小公倍数怎么求？ 首先把两个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。 比如：求45和30的最小公倍数。 45=3*3*5 30=2*3*5 不同的质因数是2,3,5。3是他们两者都有的质因数，由于45有两个3，30只有一个3，所以计算最小公倍数的时候乘两个3. 最小公倍数等于2*3*3*5=90 又如：计算36和270的最小公倍数。 36=2*2*3*3 270=2*3*3*3*5 不同的质因数是5。2这个质因数在36中比较多，为两个，所以乘两次；3这个质因数在270个比较多，为三个，所以乘三次。 最小公倍数等于2*2*3*3*3*5=540 最大公约数和最小公倍数<练习题> 1．有一级茶叶96克，二级茶叶156克，三级茶叶240克，价值相等．现将这三种茶叶分别等分装袋（均为整数克），每袋价值相等，要使每袋价值最低应如何装袋？ 2．a、b两数的最大公约数是12，已知a有8个约数，b有9个约数，求a与b． 3．两个数的积是6912，最大公约数是24，求：（1）它们的最小公倍数；（2）满足已知条件的自然数是哪几组？ 4．甲、乙、丙三个学生定期向某老师求教，甲每4天去一次，乙每6天去一次，丙每9天去一次，如果这一次他们三人是3月23日都在这个老师家见面，那么下一次三人都在这个老师家见面的时间是几月几日？ 5．求被5除余2，被6除余3，被7除4的大于1000、小于1500的所有自然数． 6．某个数与36的最大公约数是12，与36的最小公倍数是180，求这个数． 7．有三个自然数a、b、c，a与b的最大公约数是2；b和c的最大公约数是4；a和c的最大公约数是6；a、b、c三个数的最小公倍数是60，求这三个数的最小的和是多少？ 答案仅供参考： 1．三种数量不等的茶叶价值相等，等分装袋后，每袋价值仍相等，由于每种茶叶的总价值相等，每袋价值也要相等，所以这三种茶叶分装的袋数也一定相同．为了使每袋价值最低，就应使袋数尽可能多， 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); } } 用迭代法求两个数的最大公约数和最小公倍数 化工09110605 摘要：迭代法是一种循环控制语句和循环结构程序的设计方法。在计算机解决问题的时候，总希望从复杂的问题中找到规律，并归结为简单问题的重复，发挥其擅长重复运算的特点，让它重复执行一组语句，直到满足给定条件为止。因此，c语言提供了重复操作的语句，由这些语句构成的程序称为循环结构。本文就是采用迭代法，利用c语言中提供的重复语句，求得两个数的最大公约数和最小公倍数。 关键词：循环语句；循环结构；迭代法；最大公约数和最小公倍数 Iterative Method with the greatest common divisor and least common multiple of two numbers Chemical 09110605 W ANG Meng Abstract: The iterative method is a loop control statement and loop structure design process.When the computer to solve the problem, hoping to find from the law of complex issues and boil down to a simple repetition of questions, to play the good characteristics of repeat operation, let it repeat a set of statements until the date that satisfies the given conditions. Therefore, c language repeat the statement provided by these statements constitute the program is called loop structure. This is the iterative method, using c language provided by the repeated statement, obtained the greatest common divisor and least common multiple of two numbers. Key words:loop; loop structure; iteration; greatest common divisor and least common multiple 理工大学信息工程与自动化学院学生实验报告 （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 第五讲 最大公约数与最小公倍数 【知识导引】 一、约数的概念与最大公约数 约数又叫因数(在正整数范围内）整数a 能被整数b 整除，a 叫做b 的倍数，b 就叫做a 的约数。最大公约数:如果一个数既是数a 的约数，又是数b 的约数，称为[a,b]的约数。几个数公有的因数，叫做这几个数的公因数,其中最大的一个叫做这几个数的最大公因数。 1. 求最大公约数的方法 ①分解质因数法：先分解质因数，然后把相同的因数连乘起来。 例如：2313711=??，22252237=??，所以(231,252)3721=?=； ②短除法：先找出所有共有的约数，然后相乘。例如：21812 39632 ，所以(12,18)236=?=； ③辗转相除法：每一次都用除数和余数相除，能够整除的那个余数，就是所求的最大公约数。用辗转相除法求两个数的最大公约数的步骤如下：先用小的一个数除大的一个数，得第一个余数；再用第一个余数除小的一个数，得第二个余数；又用第二个余数除第一个余数，得第三个余数；这样逐次用后一个余数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数(如果最后的除数是1，那么原来的两个数是互质的)。例如，求600和1515的最大公约数：151********÷= ；6003151285÷= ；315285130÷= ；28530915÷= ；301520÷= ；所以1515和600的最大公约数是15。 2. 最大公约数的性质 ①几个数都除以它们的最大公约数，所得的几个商是互质数； ②几个数的公约数，都是这几个数的最大公约数的约数； ③几个数都乘以一个自然数n ，所得的积的最大公约数等于这几个数的最大公约数乘以n 。 3. 求一组分数的最大公约数 先把带分数化成假分数，其他分数不变；求出各个分数的分母的最小公倍数a ；求 出各个分数的分子的最大公约数b ；b a 即为所求。 二、倍数的概念与最小公倍数 对于整数m ，能被n 整除（n/m ）,那么m 就是n 的倍数。如15能够被3或5整除，我们就说15是3的倍数，也是5的倍数。几个数公有的倍数叫做这几个数的公倍数,其中最小的一个叫做这几个数的最小公倍数。 论在小学教材中求最大公约数和最小公倍数的方法 班级：08数三班 学号：30308346 姓名：钟世校 初等数论是研究整数最基本性质的一门十分重要的数学基础课程,整除理论是初等数论的基础,其中心内容是最大公约数理论和算术基本定理,而我现在要论述的是求最大公约数和最小公倍数的几种方法 首先,让我们一起在来来了解一下最大公约数与最小公倍数的定义: 最大公约数: 设1a , 2a ,…，n a (n ≥2)是不全为零的整数,如果d| i a (i =1,2,3…,n),则称d 为 1a , 2a ,…，n a 的公约数,全体公约数中最大的一个数称为 1a , 2a ,…，n a 的最大公约数,记作(1a , 2a ,…，n a ). 最小公倍数: 设1a , 2a ,…，n a 是非零整数.若有整数M, 使 i a | M (i =1,2,3…,n ),则称 M 为1a , 2a ,…， n a 的公倍数,公倍数中最小的正数,称为1a , 2a ,…，n a 的最小公倍数,记作[1a , 2a ,…，n a ]。 求最大公约数的方法通常有两种,即用分解质因数法求最大公约数或用辗转相除法求最大公约数（亦称欧几里得算法），而求最小公倍数通常是用分解质因数或利用最大公约数来求最小公倍数,下最面我通过几道例题来演示上述方法. 一、 求最大公约数的方法. ⒈用分解质因数法求最大公约数. 例1. 求2700 、 7560、3960的最大公约数 解：把2700 、7560 、3960分别分解质因数. 得 2700=32 2 35 2?? 7560=3 3 357 2??? 3960= 2 3 352 11 ??? ∴ (2700,7560,3960)= 2 2 352 ??180 = 即2700 、 7560 、3960的最大公约数为180. 基本算法——辗转相除法 问题：输出两个正整数a,b,且0 改进——已知整数a,b及其最大公约数p,则直接可推算出最小公倍数q： q= a*b/p; 源程序2 #include 求最大公约数教案 道真县中等职业学校张学东 教学目标： 1．使学生进一步理解和掌握公约数和最大公约数的意义。 2．使学生理解和掌握用短除法、分解质因数的方法两个数的最大公约数的算理。 教学难点：用分解质因数的方法求两个数的最大公约数的算理。 教学设计： 一约数 【引例】看下面的式子： 18÷6 25÷5 24÷3 99÷11 169÷13这些除式中，商都是整数，余数为0.我们在数的整除中已经知道，这些除式都是整除式。 【小结】如果一个整数a除以整数b（b≠0）除得的商正好是整数而没有余数，那么我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。 上式中6是18的约数，5是25的约数，3是24的约数，11是99的约数，13是169的约数……，显然约数只存在于整除式中，故不是整除式就不存在约数。 二公约数及最大公约数 【引例】看下面的式子： 48÷8 24 ÷8 56÷8 ，显然，这些都是整除式，8是48、 24、56、这些所有整数的约数。 【小结】如果一个整数同时是几个整数的约数，那么就称这个 整数是它们的公约数。 公约数亦称公因数，公约数中最大的我们称它为最大公约数，若a 、b 的最大公约数为c ， 三 公约数与最大公约数的求法 求最大公约数的求法一般有：枚举法、短除法、分解质因数法、 1、短除法： 【讲解】 短除符号就像一个倒过来的除号，短除法就是先写出要求最大公因数的两个数A 、B ，再画一个短除号，接着在原本写除数的位置写两个数公有的质因数Z （通常从最小的质因数开始），然后在短除号的下方写出这两个数被Z 整除的商a 、b ，对a 、b 重复以上步骤，以此类推，直到最后的商互质为止，再把所有的除数相乘，其积即为A 、B 的最大公约数。 例1： 用短除法求12和18的最大公约数。 解:∵ ∴12和18的最大公约数为2×3=6 2、分解质因数法 【讲解】将要求最大公因数的两个数A 、B 分别分解质因数，再从中找出A 、B 公有的质因数，把这些公有的质因数相乘，即得到A 、2 12 18 6 9 3 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 实验九 一、实验内容 教材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、倍数关系的两个数，最大公因数是较小的数，最小公倍数是较大的数。（如；6和12的最大公因数是6，最小公倍数是12。） 2、互质关系的两个数，最大公因数是１，最小公倍数是它们的乘积。（如，5和7的最大公因数时1，最小公倍数是5×7=35） 二、一般情况： 1、求最大公因数 2、求最小公倍数 ◆质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外， 不能被其他自然数整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。 ◆根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列 质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。 最小的质数是2。 ◆互质数为数学中的一种概念，即两个或多个整数的公因数只有1的非零自然数。公因数 只有1的两个非零自然数，叫做互质数。 ◆最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。 a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多 个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。 ◆两个或多个整数公有的倍数叫做它们的公倍数。 ◆两个或多个整数的公倍数里最小的那一个叫做它们的最小公倍数。整数a，b的最小公 倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。 ◆与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为（a，b）。 ◆关于最小公倍数与最大公约数，我们有这样的定理： ◆(a,b)[a,b]=ab(a,b均为整数) 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.main() 2.{ 3.int p,r,n,m,temp; 4.printf("Please enter 2 numbers n,m:"); 5.scanf("%d,%d",&n,&m);//输入两个正整数. 6.if(n 五年级数学教案《求两个数的最大公约数》教学重点理解公约数、最大公约数、互质数的概念。 教学难点理解并掌握求两个数的最大公约数的一般方法。 教学用具投影仪等。 教学过程 一、创设情境 填空：①123=4，所以12能被4（）。4能（）12，12是3的（），3是12的（）。②把18和30分解质因数是，它们公有的质因数是（）。③10的约数有（）。 二、揭示课题 我们已经学会求一个数的约数，现在来看两个数的约数。 三、探索研究 1．小组合作学习 （1）找出8、12的约数来。 （2）观察并回答。 ①有无相同的约数？各是几？ ②1、2、4是8和12的什么？ ③其中最大的一个是几？知道叫什么吗？ （3）归纳并板书 ①8和12公有的约数是：1、2、4，其中最大的一个是4。 ②还可以用下图来表示。 813 24612 8和12的公约数 （4）抽象、概括。 ①你能说说什么是公约数、最大公约数吗？ ②指导学生看教材第66页里有关公约数、最大公约数的概念。（5）尝试练习。 做教材第67页上面的做一做的第1题。 2．学习互质数的概念 （1）找出下列各组数的公约数来：5和78和912和251和9 （2）这几组数的公约数有什么特点？ （3）这几组数中的两个数叫做什么？（看书67页） （4）质数和互质数有什么不同？（使学生明确：质数是一个数，而互质数是两个数的关系） 3．学习例2 （1）出示例2并说明：我们通常用分解质因数的方法来求两个数的最大公约数。 （2）复习的第2题，我们已将18和30分解质因数（如后）18=23330=235 （3）观察、分析。 ①从18和30分解质因数的式子中，你能看出18和30各有哪些约数吗？ ②18和30的公约数就必须包含18和30公有的什么？ ③18和30公有的质因数有哪些？ 1.辗转相除法GCD算法的基本原理 DCD - Greatest Common Divisor 欧几里得定理： 若 a = b * r + q，则 GCD(a,b) = GCD(b,q)。 证明： 假设 c = GCD(a,b) 则存在m使得 a = m * c,b = n * c; 因为 a = b * r + q, 则 q = a - b * r = m * c - n * c * r = (m - n * r) * c; 因为 b = n * c , q = (m - n * r) * c 故要证明GCD(a,b) = GCD(b,q)，即证明 n 与 m - n * r互质 下面证明 m-n×r与n互质： 假设不互质，则存在公约数k使得 m - n * r = x * k, n = y * k. 则: a= m * c = (n * r + x * k) * c = (y * k * r + x * k) * c = (y * r + x) * k * c b = n * c = y * c * k 则GCD(a,b) = k * c,与 c=gcd(a, b) 矛盾 2.辗转相除法算法的实现 2.1递归实现 自己改进 2.2迭代实现 3.更相减损法 更相减损术，是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。 《九章算术》是中国古代的数学专著，其中的“更相减损术”可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。” 翻译成现代语言如下： 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。 第二步：以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小数。继续这个操作，直到所得的减数和差相等为止。 则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。 其中所说的“等数”，就是最大公约数。求“等数”的办法是“更相减损”法。所以更相减损法也叫等值算法。 例如：用更相减损术求260和104的最大公约数。 解：由于260和104均为偶数，首先用2约简得到130和52，再用2约简得到65和26。此时65是奇数而26不是奇数，故把65和26辗转相减： 65-26=39 39-26=13 26-13=13 所以，260与104的最大公约数等于13乘以第一步中约掉的两个2，即13*2*2=52。2.更相减损法算法的实现 2.1递归实现最大公约数的算法
matlab最大公约数 三种算法
小学数学解题方法解题技巧之最大公约数法
最大公约数和最小公倍数怎么求
Java算法最大公约数和最小公倍数
用迭代法求两个数的最大公约数和最小公倍数
最大公约数的三种算法复杂度分析时间计算
第五讲 最大公约数与最小公倍数
论最小公倍数和最大公约数的方法
C语言算法——最大公约数
求最大公约数教学设计
最大公约数和最小公倍数算法
C语言求最大公约数和最小公倍数算法
c++,使用欧几里得算法计算两个数的最大公约数,分别用递推和递归两种算法实现5
求最大公因数和最小公倍数的方法
C语言求最大公约数
求最大公约数和最小公倍数的算法和程序
五年级数学教案《求两个数的最大公约数》
求最大公约数的原理及算法实现
- 1.算法-最大公约数的三种算法
- 求最大公约数算法
- matlab最大公约数 三种算法
- 最大公约数流程图
- 最大公约数和最小公倍数算法
- 算法分析与设计求最大公约数问题实验报告
- 求最大公约数递归算法
- 算法描述-最大公约数
- Java算法最大公约数和最小公倍数
- c++,使用欧几里得算法计算两个数的最大公约数,分别用递推和递归两种算法实现5
- 求最大公约数的原理及算法实现
- 最大公约数的三种算法 复杂度分析 时间计算
- 最大公约数的算法
- 求最大公约数的原理及算法实现
- C语言算法——最大公约数
- 最大公约数的三种算法_复杂度分析_时间计算
- 算法案例1-求最大公约数
- 最大公约数的算法
- 最大公约数的三种算法复杂度分析时间计算
- 求两个正整数最大公约数的算法