三种方法求最大公约数200910405429

昆明理工大学信息工程与自动化学院学生实验报告

（2011 —2012 学年第 1 学期）

课程名称：算法设计与分析开课实验室：信自楼应用、网络机房445 2011 年10月 19日年级、专业、班计科094 学号200910405429 姓名徐章林成绩

实验项目名称求最大公约数指导教师吴霖

教师评语该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□

该同学的实验能力： A.强□ B.中等□ C.差□

该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□

实验报告是否规范： A.规范□ B.基本规范□ C.不规范□

实验过程是否详细记录： A.详细□ B.一般□ C.没有□

教师签名：

年月日

一、上机目的及内容

1.上机内容

求两个自然数m和n的最大公约数。

2.上机目的

（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；

（2）掌握并应用算法的数学分析和后验分析方法；

（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。

二、所用仪器、材料（设备名称、型号、规格等或使用软件）

1台PC及VISUAL C++6.0软件

三、实验原理及基本技术路线图（方框原理图或程序流程图）

（1）分解质因数法的流程分析如下图：

（2）连续整数检测法流程分析如下图：

（3）殴几里德流程分析如下图：

四、实验方法、步骤（或：程序代码或操作过程）

/*--------------------用多种方法计算两个数的最大公约数----------------------*/ /*-----------------作者：200910405429--------开发环境：DEV C++----------------*/ #include "stdio.h"

#include "conio.h"

#include"time.h"

/*------------------------以下是分解质因数法--------------------------------*/ int gcd_factor(int a,int b)

{

int k=1,i,temp;

{

temp=a;

a=b;

b=temp;

}

if(a%b==0)

{

return b;

}

else

{

for(i=2;i

{

while(a%i==0&&b%i==0)

{

k=k*i;

a=a/i;/*要除以已经选出来的质因数，以免重复计算*/ b=b/i;

}

}

return k;

}

}

/*-----------------------------以下是更相减损术-----------------------------*/ int gcd_reduction(int a,int b)

{

int temp;

if(a

{

temp=a;

a=b;

b=temp;

}

if(a==b)

return a;

else

return gcd_reduction(b,a-b);

}

/*-----------------------------连续整数检测法-------------------------------*/ int gcd_continuous(int a ,int b)/**/

{

int i,k,temp;

temp=a

for(i=0;i

{

k=temp-i;

if(((a%k)==0)&&((b%k)==0))

{

return k;

break;

}

}

getch();

}

/*------------------------------欧几里德算法--------------------------------*/ int gcd_Euclidean (int a,int b)

{

if (!b)

return a;

else

return gcd_Euclidean (b,a%b);

}

/*---------------------------------主函数-----------------------------------*/ main()

{

int a, b,i=1000;

double start=0,end=0,time[4];

printf("输入两个整数:");

scanf ("%d %d",&a,&b);

while(1)

{

start=clock(); /*以下测算gcd_factor(a,b)的时间*/

while(i>0)

{

gcd_factor(a,b);

i--;

}

end=clock();

time[0]=(end-start);

end=0;

start=clock(); /*以下测算gcd_Euclidean(a,b)的时间*/

while(i>0)

{

gcd_Euclidean(a,b);

i--;

}

end=clock();

time[1]=(end-start);

start=clock(); /*以下测算gcd_continuous(a,b)的时间*/

while(i>0)

{

gcd_continuous(a,b);

i--;

}

end=clock();

time[2]=(end-start);

start=clock(); /*以下测算gcd_reduction(a,b)的时间*/

while(i>0)

{

gcd_reduction(a,b);

i--;

}

end=clock();

time[3]=(end-start);

break;

}

printf("\n\n");

printf("\n\t------几种求最小公约数的算法-----\n");

printf("\n\t*----------------------------------------------*"); printf("\n\t-- 1-----分解质因数法:%d 运行时

间:%lf----",gcd_factor(a,b),time[0]);

printf("\n\t-- 2-----殴几里德:%d 运行时

间:%lf----",gcd_Euclidean(a,b),time[1]);

printf("\n\t-- 3-----连续整数检测:%d 运行时

间:%lf----",gcd_continuous(a,b),time[2]);

printf("\n\t-- 4-----更相减损算术:%d 运行时

间:%lf----",gcd_reduction(a,b),time[3]);

printf("\n\t--- 注：以上运行时间为延迟1000倍所得----------");

printf("\n\t*----------------------------------------------*");

getch();

}

/*----------------------------------程序完----------------------------------*/

五、实验过程原始记录( 测试数据、图表、计算等)

1、程序运行结果：

2、下图是在DEV C++中对各函数运行性能分析的结果:

六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）

通过此次上机。使我复习数据结构课程的相关知识，更进一步地清楚了数据结构和算法之间的联系，并应学习了怎样用算法的数学分析和后验分析方法。通过用不同的方法实现对最大公约数的求解，我理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。

注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。

最大公约数与最小公倍数(正式)

最大公约数与最小公倍数 基本概念： 1、公约数和最大公约数 几个数公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。 例如：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的最大公约数。 一般地我们用（a,b）表示a,b这两个自然数的最大公约数，如（12，30）=6。如果（a,b）=1,则a,b两个数是互质数。 2、公倍数和最小公倍数 几个数公有的倍数，叫做这几个数的公倍数；其中最小的一个，叫做这几个数的最小公倍数。 例如：12的倍数有12，24，36，48，60，72，… 18的倍数有18，36，72，90，… 12和18的公倍数有：36，72…其中36是12和 18的最小公倍数。 一般地，我们用[a,b]表示自然数，a,b的最小公倍数，如[12，18]=36。 3、最大公约数与最小公倍数的求法 A．最大公约数 求两个数的最大公约数一般有以下几种方法 （1）分解质因数法 （2）短除法 （3）辗转相除法 （4）小数缩倍法 （5）公式法 前两种方法在数学课本中已经学过，在这里我们主要介绍辗转相除法。 当两个整数不容易看出公约数时（一般是数字比较大），我们可以合用辗转相除法。B．最小公倍数 求几个数的最小公倍数的方法也有以下几种方法： （1）分解质因数法 （2）短除法 （3）大数翻倍法 （4）a×b=（a,b）×[a,b] 上面的公式表示：两个数的乘积等于这两个数的最大公约数和最小公倍数的乘积。 例1、437与323的最大公约数是多少？

LX1、24871和3468的最小公倍数是多少？ 例2、把一块长90厘米，宽42厘米的长方形铁板剪成边长都是整厘米，面积都相等的小正方形铁板，恰无剩余。至少能剪块。 【分析】根据题意，剪得的小正形的边长必须是90和42的最大公约6。所以原长方形的长要分90÷6＝15段，宽要分42÷6＝７段，至少能剪17×７＝105（块） 解：（１）求90和42的最大公约数 2 90 42

最大公约数的三种算法 复杂度分析 时间计算

昆明理工大学信息工程与自动化学院学生实验报告 （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

2020小学奥数训练题库约数与最大公约数

名思小学奥数训练题库约数与最大公约数13712345678987654321的除本身之外的最大约数是多少？ 138将一个两位数的十位数字减去或加上它的个位数字，所得到的两个数都是78的大于1的约数。求这个两位数。 139有一个自然数，它的最小的两个约数之和是4，最大的两个约数之和是100，求这个自然数。 140有一个自然数，它的最大的两个约数之和是123，求这个自然数。 141求只有 8个约数但不大于30的所有自然数。 142给出一个自然数n，n的所有约数的个数用T(n)表示。(1)求 T(42)；(2)求满足 T(n)=8的最小自然数n；(3)如果T(n)=2，那么n是怎样的数？ 143在1～100中，所有的只有3个约数的自然数的和是多少？ 144如果自然数a和b各自恰好都有5个不同的约数，那么a×b能否恰好有10个不同的约数？ 145☆少年宫游乐厅内悬挂着200个彩色灯泡，这些灯泡或明或暗，十分有趣。这200个灯泡按1～200编号，它们的亮暗规则是： 第一秒，全部灯泡变亮； 第二秒，凡编号为2的倍数的灯泡由亮变暗； 第三秒，凡编号为3的倍数的灯泡改变原来的亮暗状态，即亮的变暗，暗的变亮； 一般地，第n秒凡编号为n的倍数的灯泡改变原来的亮暗状态。 这样继续下去，每4分钟一个周期。问：第200秒时，明亮的灯泡有多少个？ 146100以内约数个数最多的自然数有五个，它们分别是几？ 147一个学生做两个两位数乘法时，把其中的一个乘数的个位数字9误看成7，得出的乘积是756。问：正确的乘积是多少？ 148给出一个自然数n，n的所有约数的和用S(n)表示，求S(24)和S(36)。 149☆对于任意的大于2的自然数n，所有小于n且与n互质的自然数的个数是奇数还是偶数，还是不能肯定？

最大公约数的算法

. 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．

c语言程序设计-求两个数最大公约数

1，写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果。这两个数由键盘输入。 程序设计： #include int hcf(int x,int y) {int t; if(x

#include void g_two(double a,double b,double c) {double x1,x2; x1=(-b+sqrt(b*b-4*a*c))/(2*a); x2=(-b-sqrt(b*b-4*a*c))/(2*a); printf("方程的两个根为：x1=%f\nx2=%f\n",x1,x2); } void g_one(double a,double b,double c) {double x; x=(-b)/(2*a); printf("方程的两个根为：x1=x2=%f\n",x); } void g_zone(double a,double b,double c) { printf("无解\n"); } void main() {void g_two(double,double,double); void g_one(double,double,double); void g_zone(double,double,double); double a,b,c,t; printf("请输入a、b、c的值："); scanf("%lf%lf%lf",&a,&b,&c); t=b*b-4*a*c; if(t>0) g_two(a,b,c); else if(t==0) g_one(a,b,c); else g_zone(a,b,c); } 运行结果：

matlab最大公约数 三种算法

算法设计与分析 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';

c++实现计算任意多个三位数的最大公约数,直到输入-999为止,调用子函数求最大公约数

#pragma warning(disable:4786) #include #include #include #include using namespace std; #ifndef SYSOUT const char *SYSOUT = "999"; //退出标示 const int SYSFAILED = -1; //系统错误码 const int SYSNUMLENGTH = 3; //输入的数据长度限制 #endif //判断用户输入字符是否为数字 bool IsAllNum(const char* resStr); //计算最大公约数 int GetMaxDivissor(set *pSetNum,int nMin); //该函数去除输入前端“0” void GetStingTrim(string *pStr); int main() { //----------------------------------------------------------------------------------------- //程序变量 char szNum[4] = {0}; set setNum; //用户输入数据数组 string buffer; int nMax = 0; //用户输入最大数 int nMin = 0; //用户输入最小数 bool isNum = false; //是否为数字 int count = 0; //记录用户输入数据量 int nTmp = 0; //用于存储临时数据 char szNotice[100] = {0}; //----------------------------------------------------------------------------------------- //用户输入控制 while(strcmp(buffer.c_str(),SYSOUT) != 0) { buffer = ""; memset(szNotice,0,sizeof(szNotice)); sprintf(szNotice,"Please Enter Your %dNum:",count+1); cout<

“最大公约数”练习题(基础教学)

“最大公约数”练习题姓名 基础题 一、在下圈内填上适当的数二、70=2×5×7 30=2×3×5×11 70和330相同的质因数是（）， 70和330的最大公约数是（） 三、（1）24的约数有（），（2）36的约数有（）（3）24和36的公约数有（），（4）24和36的最大公约数有（）四、先把下面两个数分别分解质因数，再求它们的最大公约数。 165=（）×（）×（）195=（）×（）×（）165和195的最大公约数是（）×（）=（） 五、在3、10、18、19、35五个数中： （1）两合数（）和（）是互质数，它们的最大公约数是（）。 （2）两合数（）和（）有公约数5，所以它们不是互质数。 （3）（）和（）是两个不同的质数，一定是（）。 （4）质数（）和合数（）成倍数关系，因此它们的最大公约数是（）。拓展题 一、判断题（对的在括号内打V，错的打X） （1）因为数a和数b是互质数，所以数a和数b没有公约数。（）（2）因为b是a和b的公约数，所以b也是a和b的最大公约数。（）（3）互质的两个数不一定都是质数（）；（4）两个质数的和一定还是质数。（）二、求下面每一组数的最大公约数（用短除法） （1）48和60 （2）55和66 （3）52和39 （4）242和66 （5）14、28和84 （6）18、24、和42 （7）3、7和5 三、直接写出下面每组数的最大公约数 1和9 15和5 6和7 105和315 28和27 11和33 13和17 100和101 四、把长102厘米，宽78 厘米的硬纸，剪成同样大的正方形，并且不能剩余，

剪得正方形边长最长是多少？可以剪成几块？ 五、某班有男生24人，女生16人，在参加植树活动中将全班同学分成若干小组， 要求每组中男生人数相等，女生人数也相等，最多可以分成多少组？每组男女生共有几人？ 六、已知两数积是1734，它们的最大公约数是17，求这两个数。 七、有三根铁丝，一根长7米，一根长20米，一根长30米，要把它们截成同样 长的小段，已知第一根余下1米，第二根余下2米，第三根没有剩余，每段最长多少米？ 综合题 一、填空题 1．有四个（可以相同）小于10的自然数，它们的积是360，已知四个数中只有一个是合数，那么这四个数是（）。 2．最小的自然数，最小的质数，最小的合数之和的2倍是（）。 3．一个数，千位上是最小的质数，百位上是最小的自然数，个位上是最小合数，百分位上是最大数字，其余数位上的数字都是零，这个数应写作（）。4．直接写出下面各组数的最大公约数在括号内。 4和9（）18和9（）2和14（）3和70（）22和33（）21和35（） 5．已知两个数的和是256，它们的最大公约数是16，这两数是（）和（）；（）和（）；（）和（）；（）和（）。 二、判断题 1．任何一个自然数减1，还是个自然数---------------------------------------（）2．12和18的公约数只有3个（）3．同任何非零自然数互质的数是1（）4．奇数不一定是质数，偶数都是合数（）5．互质的两个数没有最大公约数（）6．如果一个非零自然数a小于某个质数b，那么a与b一定互质--------------（）三、选择。 1．a＝2×2×5，b＝2×3×5，a、b最大公约数是（）。 A 2 B 5 C 10 D 15 E 6 2．甲数是乙数的15倍，这两个数的最大公约数是（）。 A 15 B 甲数 C 乙数 D 甲数×乙数 3．两个自然数的最大公约数是12这两个数的全部公约数是（）。 A 1、2、3、12 B 2、3、4、6 C 2、3、4、6、12 D 1、2、3、4、6、12 4．下面哪句话是错的（）。 A 4是16的约数 B 2是质数 C 9是合数 D 两个互质数没有公约数

最大公约数和最小公倍数怎么求

最大公约数和最小公倍数怎么求？ 首先把两个数的质因数写出来，最小公倍数等于它们所有的质因数的乘积（如果有几个质因数相同，则比较两数中哪个数有该质因数的个数较多，乘较多的次数）。 比如：求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．三种数量不等的茶叶价值相等，等分装袋后，每袋价值仍相等，由于每种茶叶的总价值相等，每袋价值也要相等，所以这三种茶叶分装的袋数也一定相同．为了使每袋价值最低，就应使袋数尽可能多，

最大公约数和最小公倍数的比较_教案教学设计

最大公约数和最小公倍数的比较 教学目标 (一)进一步理解并掌握最大公约数和最小公倍数的概念，分清求最大公约数和最小公倍数的相同点和不同点。 (二)培养学生仔细、认真的做题习惯和比较的思维方法。 (三)培养学生观察、分析、比较的能力。 教学重点和难点 最大公约数和最小公倍数异同点的比较。 教学用具 教具：小黑板，投影片。 学具：判断卡，选择卡。 教学过程设计 (一)复习准备 教师： ①什么叫最大公约数和最小公倍数？ ②怎样求最大公约数和最小公倍数？ ③求下面各题的最大公约数和最小公倍数？(口答) 8和1613和262和97和15 教师：对上面几道题你是怎么想的？各有什么特点？你能发现什么规律？ 明确：

①两个数有倍数关系，最大公约数最较小数，最小公倍数是较大数。 ②两个数互质，最大公约数是1，最小公倍数是两个数乘积。 (二)学习新课 1．出示例5。 求28和42的最大公约数和最小公倍数。(要求学生独立完成。) 学生口述教师板书。 28和42的最大公约数是： 2×7=14 28和42的最小公倍数是 2×7×2×3=84 教师：观察上面两道题，谁能说出求最大公约数和求最小公倍数有什么地方相同？什么地方不同？(讨论) 在讨论的基础上，总结出下面的结论。 教师：为什么求最大公约数只要把所有除数乘起来，而求最小公倍数就要把所有除数和商都乘起来呢？ 明确：求最大公约数是两个数公有质因数的积；求最小公倍数既要包含两个数公有质因数，又要包括各自独有的质因数。 教师：既然求两个数的最大公约数和最小公倍数的短除过程是相同的，那么，我们就可以用一个短除式来表示。例5怎样做简便？(由学生

用迭代法求两个数的最大公约数和最小公倍数

用迭代法求两个数的最大公约数和最小公倍数 化工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

Java算法最大公约数和最小公倍数

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

(完整版)最大公约数与最小公倍数练习题

?最大公约数和最小公倍数练习题 一. 填空题。 3. 所有自然数的公约数为（）。 4. 如果m和n是互质数，那么它们的最大公约数是（），最小公倍数是（）。 5. 在4、9、10和16这四个数中，（）和（）是互质数，（）和（）是互质数，（）和（）是互质数。 6. 用一个数去除15和30，正好都能整除，这个数最大是（）。 7. 两个连续自然数的和是21，这两个数的最大公约数是（），最小公倍数是（）。 8. 两个相邻奇数的和是16，它们的最大公约数是（），最小公倍数是（）。 9. 某数除以3、5、7时都余1，这个数最小是（）。 10. 根据下面的要求写出互质的两个数。 （1）两个质数（）和（）。 （2）连续两个自然数（）和（）。 （3）1和任何自然数（）和（）。 （4）两个合数（）和（）。 （5）奇数和奇数（）和（）。 （6）奇数和偶数（）和（）。 二. 判断题。 1. 互质的两个数必定都是质数。（） 2. 两个不同的奇数一定是互质数。（） 3. 最小的质数是所有偶数的最大公约数。（） 4. 有公约数1的两个数，一定是互质数。（） 三. 直接说出每组数的最大公约数和最小公倍数。 26和13（）13和6（）4和6（） 5和9（）29和87（）30和15（） 13、26和52 （）2、3和7（） 四. 求下面每组数的最大公约数和最小公倍数。（三个数的只求最小公倍数） 45和60 36和60 27和72 76和80 42、105和56 24、36和48 五. 动脑筋，想一想： 学校买来40支圆珠笔和50本练习本，平均奖给四年级三好学生，结果圆珠笔多4支，练习本多2本，四年级有多少名三好学生，他们各得到什么奖品？

第五讲 最大公约数与最小公倍数

第五讲 最大公约数与最小公倍数 【知识导引】 一、约数的概念与最大公约数 约数又叫因数(在正整数范围内）整数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的倍数。几个数公有的倍数叫做这几个数的公倍数,其中最小的一个叫做这几个数的最小公倍数。

公约数与最大公约数 教学设计

公约数与最大公约数教学设计 一、情景导入 课件：出示长30分米，宽24分米的长方形。 师：同学们，今天老师请大家帮一个忙，老师有一间厨房要铺地砖，看大屏幕，这就是厨房的形状，长30分米，宽24分米，请同学们协助老师选一选用多大的正方形地砖铺地，才能铺得既整齐又节约呢？告诉老师正方形的边长是几？ 生：1、2、3、6分米。 师：如果老师还想铺快点，你认为哪一种方法最好？ 生：6分米。 师：同学们是怎样想到用边长1、2、3、6分米的正方形在砖铺地砖铺地的？ 生：这些数既是30的约数又是24的约数。 师：同学们的回答是准确的，为什么准确呢？这就是我们这节课将要探讨的内容。 板书：最大公约数 二、新课 师：同学们8的约数有哪些？ 生：1、2、4、8。 师：12的约数有哪些？ 生：1、2、3、4、6、12。

师：请同学们观察一下哪些是8和12公有的约数？ 生：1、2、4。 师：我们把8和12公有的约数1、2、4叫做8和12的公约数。 师：这些公约数中，谁最大？ 生：4。 师：4就是8和12的最大公约数。 师：通过刚才的探索，你能说说什么是公约数，什么是最大公约数。 生：说概念。 师：好，12个数公有的约数叫做这几个数的公约数。其中最大的一个，叫做这几个数的最大公约数。 师：好，看大屏幕，请同学们齐读一遍。 师：当然8除的公约数外，8还有独有的约数8，12还有独有的约数，3、6、12。 师：下面请同学们找出15和18的公约数，再找出它的最大公约数。 师：15的约数有哪些？ 生：…… 师：18的约数有哪些？ 生：1、2、3、6、9、18。 师：15和18的公约数有哪些？

C语言算法——最大公约数

基本算法——辗转相除法 问题：输出两个正整数a,b,且0 void main() { int a,b, p, q; do{ printf("请输入a和b:\n"); scanf("%d%d",&a,&b); } while ( a<0 || b<0 || a>b); p=a; while( a%p!=0 || b%p!=0) p--; printf("这两个数的最大公约数是%d\n",p); q=b; while( q%a!=0 || q%b!=0) q++; printf("这两个数的最小公倍数是%d\n",q); }

改进——已知整数a,b及其最大公约数p,则直接可推算出最小公倍数q： q= a*b/p; 源程序2 #include void main() { int a,b, p, q; do{ printf("请输入a和b:\n"); scanf("%d%d",&a,&b); } while ( a<0 || b<0 || a>b); p=a; while( a%p!=0 || b%p!=0) p--; printf("这两个数的最大公约数是%d\n",p); q= a*b/p; printf("这两个数的最小公倍数是%d\n",q); } 解法1的缺点：效率低。 例如a=1397, b=2413,其最大公约数p=127，为得到p，共循环了1397-127+1=1171次。如何提高效率？