matlab最大公约数 三种算法.doc

算法设计与分析 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.mx=fix(rand(1,1000)*1000);y=fix(rand(1,1000)*1000);for i=1:1000 A(i)=CommFactor2(x(i),y(i);endx=x;y=y;算法一：function r=CommFactor1(m,n) tic;if mn)t=n;else t=m;while(t) if(m%t=0&n%t=0)break; else t=t-1;endendr=ttoc;算法二： function r=CommFactor2(m,n)tic;r=mod(m,n);while r=0 m=n; n=r; r=mod(m,n);endr=n;toc;算法三： function factor=CommFactor3(m,n)tic;factor=1;themax=max(m,n);for i=2:1:themax while (mod(m,i)=0)&(mod(n,i)=0) factor=factor*i; m=m/i; n=n/i; endendtoc;三种算法时间复杂度比较：（c+语言）#includeiostream.h#includestdio.h#includestdlib.h#includetime.h#define N 100int w,w2,w3;/用于计数int f1(int m,int n)int t;if(mn)t=n;else t=m;while(t) if(m%t=0&n%t=0)break;else t=t-1;w+;return t;int f2(int m,int n)int r;r=m%n;w2=1;while(r!=0)m=n; n=r; r=m%n;w2+;return n;int f3(int m,int n) int i, 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+; return factor;int main(void) int m,n;printf( 请输入m,n :n);scanf(%d%d,&m,&n);int k;k=f1(m,n); printf( 方法一最大公约数为： %dn,k);k=f2(m,n);printf( 方法二最大公约数为： %dn,k);k=f3(m,n);printf( 方法三最大公约数为： %dn,k);printf(n-n);printf(n计数器显示结果：nnn); printf(方法一： %d n,w2); printf(方法二： %d n,w); printf(方法三： %d n,w3);printf(n-n);float a,i; clock_t start,finish; double usetime;i=0; start= clock(); while (i1000000)f1(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法一用时%.f*10(-6) 豪秒n, usetime);i=0; start= clock(); while (i1000000)f2(m,n);i+;finish=clock(); usetime= finish-start; printf( 方法二用时%.f*10(-6) 豪秒n, usetime); i