资源描述：
《matlab最大公约数 三种算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、算法设计与分析11信本余启盛118632011004一、上机目的及内容1.上机内容求两个自然数m和n的最大公约数。2.上机目的（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；（2）掌握并应用算法的数学分析和后验分析方法；（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。二、实验原理及基本技术路线图（1）至少设计出三个版本的求最大公约数算法；（2）对所设计的算法采用大O符号进行时间复杂性分析；（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；（4）通过分析对比，得出自
2、己的结论。三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++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;根据代码考虑最坏情
3、况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2;算法二：欧几里德算法CommFactor2输入：两个自然数m和n输出：m和n的最大公约数1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;根据代码辗转相除得到欧几里得的:O(n)=logn算法三：蛮力法（短除法）CommFactor3输入：两个自然数m和n输出：m和n的最大公约数1.factor=1；2.循环变量i从2-min（m，n），执行下述操作：2.1如果i是m和n的公因子，则执行下述操作：2.1.1fa
4、ctor=factor*i；2.1.2m=m/i;n=n/i;2.2如果i不是m和n的公因子，则i=i+1；3.输出factor；根据代码考虑最坏情况他们的最大公约数，循环做了i-1次;最好情况是只做了1次，可以得出:O（n）=n/2;MATLAB程序代码：main.mx=fix(rand(1,1000)*1000);y=fix(rand(1,1000)*1000);fori=1:1000A(i)=CommFactor2(x(i),y(i));endx=x';y=y';算法一：functionr=CommFactor1(m,n)tic;ifm
5、>n)t=n;elset=m;while(t)if(m%t==0&&n%t==0)break;elset=t-1;endendr=ttoc;算法二：functionr=CommFactor2(m,n)tic;r=mod(m,n);whiler~=0m=n;n=r;r=mod(m,n);endr=n;toc;算法三：functionfactor=CommFactor3(m,n)tic;factor=1;themax=max(m,n);fori=2:1:themaxwhile(mod(m,i)==0)&&(mod(n,i)==0)factor=f
6、actor*i;m=m/i;n=n/i;endendtoc;三种算法时间复杂度比较：（c++语言）#include"iostream.h"#include"stdio.h"#include"stdlib.h"#include"time.h"#defineN100intw,w2,w3;//用于计数intf1(intm,intn){intt;if(m>n)t=n;elset=m;while(t){if(m%t==0&&n%t==0)break;elset=t-1;w++;}returnt;}intf2(intm,intn){intr;r=m%n;
7、w2=1;while(r!=0){m=n;n=r;r=m%n;w2++;}returnn;}intf3(intm,intn){inti,factor=1;for(i=2;i<=m&&i<=n;i++){while(m%i==0&&n%i==0)//此处不能用if语句{factor=factor*i;m=m/i;n=n/i;w3++;}}returnfactor;}intmain(void){intm,n;printf("请输入m,n:");scanf("%d%d",&m,&n);intk;k=f1(m,n);printf("方法一最大公约
8、数为：%d",k);k=f2(m,n);printf("方法二最大公约数为：%d",k);k=f3(m,n);printf("方法三最大公约数为：%d"
