算法设计与分析
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';
算法一：
function r=CommFactor1(m,n)
tic;
if m>n)
t=n;
else t=m;
while(t)
if(m%t==0&&n%t==0)break;
else t=t-1;
end
end
r=t
toc;
算法二：
function r=CommFactor2(m,n)
tic;
r=mod(m,n);
while r~=0
m=n;
n=r;
r=mod(m,n);
end
r=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;
end
end
toc;
三种算法时间复杂度比较：（c++语言）#include"iostream.h"
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#define N 100
int w,w2,w3;//用于计数
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;
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(" 方法一最大公约数为：%d\n",k);
k=f2(m,n);
printf(" 方法二最大公约数为：%d\n",k);
k=f3(m,n);
printf(" 方法三最大公约数为：%d\n",k);
printf("\n--------------------\n");
printf("\n计数器显示结果：\n\n\n");
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 (i<1000000)
{
f1(m,n);
i++;
}
finish=clock();
usetime= finish-start;
printf(" 方法一用时%.f*10^(-6) 豪秒\n", usetime);
i=0;
start= clock();
while (i<1000000)
{
f2(m,n);
i++;
}
finish=clock();
usetime= finish-start;
printf(" 方法二用时%.f*10^(-6) 豪秒\n", usetime);
i=0;
start= clock();
while (i<1000000)
{
f3(m,n);
i++;
}
finish=clock();
usetime= finish-start;
printf(" 方法三用时%.f*10^(-6) 豪秒\n", usetime); }
结果：（示例）。