最大公约数的三种算法 复杂度分析 时间计算
-
昆明理工大学信息工程与自动化学院学生实验报告
（
2011
—
2012
学年
第
1
学期
）
课程名称：算法设计与分析
开课实
验室：
信自楼机房
444
2011
年
10
月
12
日
年级、专业、
计科
092
班
实验项目名称
教
师
评
求最大公约数
A.
了解□
A.
强
□
A.
达到□
A.
规范□
A.
详细□
学号
2
姓名
徐兴繁
成绩
指导教师
吴晟
B.
基本了解□
B.
中等
□
B.
基本达到□
B.
基本规范□
B.
一般
□
C.
不了解□
C.
差
□
C.
未达到□
C.
不规范□
C.
没有
□
该同学是否了解实验原理：
该同学的实验能力：
该同学的实验是否达到要求：
实验报告是否规范：
实验过程是否详细记录：
语
教师签名：
年
月
日
一、上机目的及内容
1.
上机内容
求两个自然数
m
和
n
的最大公约数。
2.
上机目的
（
1
）复习数据结构课程的相关知识，实现课程间的平滑过渡
；
（
2
）掌
握并应用算法的数学分析和后验分析方法；
（
3
）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路
不同，复杂程度不
同，解题效率也不同。
二、实验原理及基本技术路线图（方框原理图或程序流程图）
（
1
）至少设计出三个版本的求最大公
约数算法；
（
2
）对所设计的算法采用大
O
符号进行时间复杂性分析；
（
3
）上机实现
算法，并用计数法和计时法分别测算算法的运行时间；
（
4
）通过分析对比，得出自己的结论。
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1
台
PC
及<
/p>
VISUAL C++6.0
软件
四、实验方法、步骤（或：程序代码或操作过程）
实验采用三种方法求最大公约数
-1-
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;<
/p>
方法二：
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
{
if(n%i==0)
-2-
{
j++;
a[j]=i;
n=n/i;
}
else i++;
}
j++;
a[j]=n;
i=1;
int u;
u=j;
while(i<=j)
{
//printf(
i++;
}
i=2;
j=0;
while(i
{
if(m%i==0)
{
j++;
b[j]=i;
m=m/i;
}
else i++;
}
j++;
b[j]=m;
i=1;
while(i<=j)
{
//printf(
i++;
}
int k=1;
for(i=1;i<=j;i++)
{
for(k=1;k<=u;k++)
{
if(b[i]==a[k])
{
h++;
-3-
}
c[h]=a[k];//printf(
a[k]=a[k+1];
break;
}
}
}
k=1;
while(h>1)
{
k=k*c[h]*c[h-1];
h=h-2;
}
if(h==1)
{
k=k*c[1];
return k;
}
else return k;
2
根
据代码分解质因子算法
O(n)=n
+n/2
为了计算每种算法运行的次数所用的时间，我将代码稍加改动添加代码如下
：<
/p>
其中计数器采用的是没做一次循环就加
1
；
计时器是记住开始时间和结束时间，用结束时间减开始时间。
#include
#include
#
include
#include
#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;
}
-4-
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=2,j=0,h=0;
int a[N],b[N],c[N];
while(i
{
if(n%i==0)
{
j++;
a[j]=i;
n=n/i;
w3++;
}
else
{
i++;
w3++;
}
}
j++;
a[j]=n;
i=1;
int u;
u=j;
while(i<=j)
{
//printf(
i++;
w3++;
}
//printf(
i=2;
-5-
-
-
-