求最大公约数流程图

昆明理工大学信息工程与自动化学院学生实验报告（２０12—２0１３学年第 1 学期)课程名称：算法设计与分析开课实验室：信自楼机房4４2 2012 年10月18日一、上机目的及内容1。

上机内容求两个自然数m和n的最大公约数。

2。

上机目的（1)复习数据结构课程的相关知识，实现课程间的平滑过渡;(2）掌握并应用算法的数学分析和后验分析方法;(3)理解这样一个观点:不同的算法能够解决相同的问题,这些算法的解题思路不同,复杂程度不同,解题效率也不同。

二、实验原理及基本技术路线图(方框原理图或程序流程图)（1）至少设计出三个版本的求最大公约数算法;（２)对所设计的算法采用大O符号进行时间复杂性分析；(3)上机实现算法，并用计数法和计时法分别测算算法的运行时间;（4)通过分析对比，得出自己的结论.连续整数检测算法流程图:连续整数检测算法时间复杂度T(n）＝Ｏ（log2(n)）欧几里得算法流程图:欧几里得算法时间复杂度 :T（n）＝O（n/２）分解因式时间复杂度：T(n)= O(n／2)+ O(ｌｏg2(ｎ）三、所用仪器、材料（设备名称、型号、规格等或使用软件)1台PC及VＩＳUAL C＋＋6。

0软件四、实验方法、步骤（或：程序代码或操作过程）#iｎｃｌudｅ"ｓtdiｏ.h"#ｉｎclude＜ｉoｓtｒeaｍ>#ｉnclｕde〈mａth。

ｈ>＃include <cｏｎiｏ。

h>＃ｉncluｄe〈tｉｍe.h〉ｉnt jishiqi_0（)；inｔjisｈiｑｉ＿1（）;int jｉshiｑi_２（)；ｉnｔｊｉｓhｉｑｉ_３()；flｏａt ｎow,t0,t1,t2,t3；uｓｉng namesｐａce std;ｉnt ｍ，n,c，ｋ；／/－-———————-—--—-———-----——--－-—-—--－———---－int jｉｓｈiqｉ_0(）//输入时延长的多余时间{intｉ,j；for(ｉ=1；ｉ<=10000;i＋+）ｆor(j＝1;j<=２０000;ｊ++)；ｔ0=(cloｃk（)—nｏw）/CLＯCKS＿PER_SＥC;returｎ0;｝//——-—－-－————--—-—-—-－－————----—－-———-－---——--－——-—－inｔjishiqi＿１()/／分解因式算法所用时间{ﻩｉnt i,ｊ;ｆor(i=1;i<=１0０00；ｉ++)fｏr(j=1;j<=20000;j++);t1=(clock（)—nｏw)/CＬＯCKS_PＥＲ_ＳＥC—t0;pｒinｔf(”分解因式算法所用时间为：％f ms\n",t１)；retｕｒｎ０;｝//——-—-－--－———---—-int jiｓhｉqｉ_２（）//欧几里得算法所用时间{ﻩiｎt ｉ,j；for(ｉ＝１；i〈=10０00;ｉ++）fｏｒ（ｊ=1;j〈=20０00;ｊ++);t３＝(cｌock(）-nｏw)／CLOCＫS_PＥR_SＥC-t0—t1—t2;pｒinｔf（＂欧几里得算法所用时间为：％f ms\n”,t３）;reｔurn0；}//--—-—-－－-——————-——－－—－——-——--－——---—————int ｊiｓhiqi_3(）//连续检测算法所用时间｛int i，j；ｆor(ｉ=１；i〈=1０000;ｉ+＋)for(ｊ=1;j<=2０0０0;j++）;t2=(clock（）—now)/ＣLOCKS_ＰER_SEC—t1－ｔ0;ｐrintf(＂连续检测算法所用时间为:%f ms\n"，t2）;ｒｅtｕrn 0；//=======＝==＝=＝=======＝＝=＝=====＝＝==＝＝=====＝=＝=＝==＝=＝int LＸ(int m，ｉnt n）//连续整数检测{jishiｑi_３（)；ﻩｉntｋ;iｎｔｃ=０；c=（m>ｎ?m：n)；for（ｉnt i=1;i＜=ｃ;i＋+){if（m%i＝=０＆&n％ｉ==0)ｋ＝i；eｌsecontinue;}rｅtuｒn ｋ;}／/——-—-—--－--———－——--——－--——-—-——iｎｔOＪ（intｍ,ｉnt n)/／欧几里得算法｛jiｓｈiｑｉ＿2（）;int r；r=ｍ%n;whiｌe(r!=0）{ｍ=n;ｎ=r；r=m％n;}return n;}／/--—-—————-—--—-—-—————-—－——--——int FJ(inｔm,int n)／／分解质因数法｛jishiqi_1（）；if（m=＝1｜｜n==1) {ｃｏuｔ〈＜”最大公约数为:1”〈〈endl;int a［1０］，b［10],s,t＝2,i=0,ａlｌ,m１,n1,i1,i2;m1=m;n1=ｎ；ｃout＜<m<<”=＂；whilｅ(1）{s=m1%t; //求m1除以t(t为2）的余数sｉf(ｓ==0){ //如果s为0,说明可以整除，则进行下面操作,记录t为质因数其中之一m１＝m1/t;a[i]=t;//把t摆在数组a［］中ｃout<＜t;i++；t=2;aｌl＝1；ｆor(i1=0;i1<i;ｉ1＋+)｛aｌl=aｌl*a［i１]；｝if(ｍ==alｌ）breaｋ; //判断该整数的质因数是否全部求出ｃouｔ<＜”＊"；}eｌsｅｔ++;｝i＝０; /／把i重置为０,进行整数n的求质因数cout〈〈endl；cｏut〈＜n〈<”=”;ｗｈｉle(1){s=n１％ｔ;iｆ(s==0）{n1＝n１／t；b［i]=ｔ；cｏuｔ＜＜t；ｉ＋+；t=２；all=1；for(i2=0;i2<i；i２＋+）{ａlｌ=all*ｂ[i2]；}if(n＝＝alｌ)ｂreak；coｕt〈〈”*";}elsｅt++;}ｃout<＜ｅｎdl;for(int s１=0;s1〈i１;s1++){//利用循环,求出公共质因数fｏr(ｉntｓ2＝0;s2<i２;s２＋+){if(a［s1]==b［s2]){all＝all*ａ[s１］;b[s2]=0；／/已经配对的质因数被清０,避免出现重复性的错误!ｂreak;}｝}cout<<"最大公约数为：”<＜all<〈enｄl;rｅturｎ0；}//---—---—－——－-—-—-——-－——-—－———--———－－—－--－———-ｉnt ｍaｉｎ（)//主函数｛cｈar c；while(１）{cout<〈”======＝＝＝＝===＝＝===＝====＝＝===＝==＝=＝====＝=＝=＝===＝=＝====”〈＜enｄl；couｔ〈＜”求最大公约数的程序”〈〈ｅndl;couｔ<<”１、分解质因数法连续整数检测法欧几里得算法"<〈eｎdl；cｏut<<＂=＝===＝==＝＝==＝=====＝=＝＝＝=＝====＝======＝=＝==＝=====＝====="〈<endl；cin〉〉ｃ；swiｔch(c){case’1’:ｃout〈〈＂请分别输入两个整数"<〈endl；jishiqi_０（);cin＞〉m>〉n；FJ(m,n)；coｕt<〈"最大公约数为:"〈＜LX(m,n）<〈endｌ;cout〈〈"最大公约数为："〈<OJ(m,n)〈<endl;breaｋ;dｅｆauｌｔ:cout<〈”请重新输入！”〈〈endl；}retｕrn0；｝五、实验过程原始记录( 测试数据、图表、计算等）请给出各个操作步骤的截图和说明;六：实验结果、分析和结论(误差分析与数据处理、成果总结等。

求两个数的最大公约数的方法
求两个数的最大公约数的方法有以下几种：
1. 辗转相除法：将较大的数除以较小的数，然后用较小数除上一步得到的余数，再用上一步得到的余数除以当前得到的余数，如此往复，直到余数为0。

最后的除数即为最大公约数。

2. 更相减损术：将较大的数减去较小的数，然后用这个差再减去较小数，如此往复，直到两个数相等。

最后的差（或相等的数）即为最大公约数。

3. 辗转相减法：先求出两个数的最大公约数的一个上界（较小的数），然后用较大的数减去较小的数，再用这个差和较小的数求最大公约数，如此往复，直到两个数相等。

最后的差（或相等的数）即为最大公约数。

4. 质因数分解法：将两个数进行质因数分解，将两个数中的相同的质因数取出来，然后将这些质因数相乘起来即为最大公约数。

其中，辗转相除法是最常用的一种方法。

数学最大公约数最大公约数（Greatest Common Divisor，简称GCD）是指在数学中，两个或多个整数共有约数中最大的一个数。

计算最大公约数对于数学问题的解决具有重要意义，它在各个领域的数学应用中都起着重要的作用。

1、欧几里得算法最大公约数的计算可以使用欧几里得算法。

该算法的原理是通过连续的辗转相除，将较大的数转化为较小的数，直到两个数相等为止。

具体步骤如下：1) 将两个数中较大的一个数除以较小的一个数，得到余数。

2) 将较小的数作为新的被除数，余数作为新的除数，重复步骤1。

3) 当余数为0时，被除数即为最大公约数。

举个例子，计算120和48的最大公约数：1) 120 ÷ 48 = 2 (24)2) 48 ÷ 24 = 2 0所以，120和48的最大公约数为24。

2、最大公约数的性质最大公约数具有以下性质：1) 若a能整除b，且b能整除c，则a能整除c。

这意味着最大公约数具有传递性，对于三个或多个数的最大公约数的计算非常方便。

2) 若a能整除b，且a能整除c，则a能整除b和c的任意线性组合。

这意味着最大公约数的概念可以推广到更一般的数学对象，例如整数的线性组合。

3、最大公约数的应用最大公约数在数学中有广泛的应用，下面介绍几个常见的应用场景：1) 约分分数：最大公约数可以用来简化分数。

通过求分子和分母的最大公约数，将其同时除以最大公约数，可以得到一个约分后的分数。

2) 解方程：最大公约数可以用于解线性同余方程，即形如ax ≡ b (mod m)的方程，其中a、x、b、m为整数，求解x的值。

3) RSA加密算法：最大公约数被广泛应用于RSA加密算法中，以保证加密数据的安全性。

4) 整数分解：通过最大公约数可以将一个整数分解为若干个互质的整数的乘积，这在数论中有重要的应用。

结论最大公约数是数学中一个重要的概念，通过欧几里得算法可以方便地计算两个或多个数的最大公约数。

最大公约数具有多种性质，并在数学的各个领域中得到广泛的应用。

⾼中信息技术（Python）重难点3：最⼤公约数最⼤公约数在教材必修1 P38、P47以及选修1 P120出现，较为困难，其算法流程、迭代以及递归思想都是教材重难点，属于较为经典的必学算法之⼀。

⼀、循环枚举什么是最⼤公约数呢？如果整数n除以m，得出结果是没有余数的整数，就称m是n的约数。

A和B的最⼤公约数指A和B公共约数中最⼤的⼀个。

教材必修1 P91 中介绍我们求⼀个整数x的因⼦可以⼀⼀列举 [1,x] 范围内的所有整数，如果x能被这个范围内的某个整数整除，那么这个数就是整数x的因⼦。

那我们解决时，我们也可以⼀⼀枚举其因⼦，最⼤公约数最⼩为1，最⼤公约数最⼤为数A和B中较⼩数，即枚举范围为 [1,min(A,B)] 。

倒着枚举找到公因⼦即结束循环是⽐较⽅便的，参考代码如下所⽰。

TZOJ7380参考代码1n=int(input())m=int(input())if n<m:min_value = nelse:min_value = mfor i in range(min_value,0,-1):if n%i==0 and m%i==0:print(i)break如果枚举初始值为⼤数并不会影响程序结果，仅会增加循环次数，所以随便选择⼀个输⼊的数作为枚举初始值也是正确的。

TZOJ7380参考代码2n=int(input())m=int(input())for i in range(n,0,-1):if n%i==0 and m%i==0:print(i)break如果从⼩开始枚举，记录下答案最后输出即可。

TZOJ7380参考代码3n=int(input())m=int(input())for i in range(1,n+1):if n%i==0 and m%i==0:ans=iprint(ans)我们还可以分别预处理出A和B的因⼦，并且因⼦枚举范围缩⼩⾄ 1 ⾄⌊x/2⌋，然后再求出最⼤公因⼦。

C语言课程设计专业：电气工程及其自动化班级：电气11姓名：学号：指导教师：兰州交通大学自动化与电气工程学院2012 年7月6日1 基本题目1.1题目编写函数，求取两个整数m,n的最大公约数和最小公倍数。

1.2 题目分析图1 程序流程图1.3 程序# include<stdio.h>int max(int a,int b);int main(){printf("请输入两个整数");int m,n,p;scanf("%d%d",&m,&n);p=m*n;printf("最大公约数为：%d最小公倍数为：%d\n",max(m,n),p/max(m,n));return 0;}int max(int a,int b){int c;while (a!=b){if(a<b){c=a;a=b;b=c;}a=a-b;}return b;}1.4 程序的运行结果图2 基本题目运行结果2 改错题目2.1 改正后程序#include <stdio.h>#include <conio.h>main(){int i=0,j;char ch;while((ch=getch())!='\r'){i++;printf("%c",ch);}printf("you type %d characters\n",i);}2.2 程序运行结果图3 正确程序运行结果3 综合题目3.1 题目综合题目为：《班级通讯录》。

3.2 数据结构对上述题目进行分析，定义结构体数据结构如下：struct Person{char name[10]; //姓名char num[15]; //号码char age[8]; //年龄char adds[20]; //住址struct Person *next;};3.3 程序的主要功能通过该系统实现对通讯录信息进行录入、显示、修改、删除、排序、保存等操作的管理。

数学推导最大公约数的加法和减法最大公约数（Greatest Common Divisor，简称GCD）是数学中常用的概念，它表示两个或多个整数的最大公约数。

在数学中，有多种方法可以求得最大公约数，其中包括通过加法和减法的推导。

本文将介绍使用加法和减法推导最大公约数的方法。

1. 加法推导最大公约数在使用加法推导最大公约数的过程中，我们首先将两个数进行相加，然后不断重复这个过程，直到得到最大公约数为止。

具体步骤如下：1.1 将给定的两个数进行相加：a + b。

1.2 如果 a 和 b 相等，那么它们本身就是最大公约数。

1.3 如果 a > b，那么将 a - b 的结果作为新的 a，b 的值不变，再次执行 1.1 步骤。

1.4 如果 a < b，那么将 b - a 的结果作为新的 b，a 的值不变，再次执行 1.1 步骤。

1.5 重复执行步骤 1.1 - 1.4，直到 a 和 b 相等或者其中一个数为 0。

1.6 最终得到的 a（或 b）就是最大公约数。

2. 减法推导最大公约数在使用减法推导最大公约数的过程中，我们首先将两个数进行相减，然后不断重复这个过程，直到得到最大公约数为止。

具体步骤如下：2.1 将给定的两个数进行相减，结果记为 c。

2.2 如果 c = 0，那么原始的两个数中较大的那个数就是最大公约数。

2.3 如果 c > 0，那么将较大的数减去 c，较小的数不变，再次执行2.1 步骤。

2.4 如果 c < 0，那么将较小的数减去 c 的绝对值，较大的数不变，再次执行 2.1 步骤。

2.5 重复执行步骤 2.1 - 2.4，直到 c = 0。

2.6 最终得到的较大的数就是最大公约数。

使用加法和减法推导最大公约数的方法相对简单易懂，无需涉及复杂的数学运算和算法。

然而，由于每次迭代都只减小一个较小的数，当两个数的差值较大时，算法的效率可能较低。

因此，在实际应用中，更常使用更高效的算法，如欧几里得算法（辗转相除法）或更高级的数论算法。