昆明理工大学 算法 实验一 求最大公约数.docx
《昆明理工大学 算法 实验一 求最大公约数.docx》由会员分享，可在线阅读，更多相关《昆明理工大学 算法 实验一 求最大公约数.docx（16页珍藏版）》请在冰点文库上搜索。
昆明理工大学算法实验一求最大公约数
昆明理工大学信息工程与自动化学院学生实验报告
（2011—2012学年第1学期）
课程名称：
算法分析与设计开课实验室：
信自楼机房4452011年10月12日
年级、专业、班
计科093
学号
200910405310
姓名
孙浩川
成绩
实验项目名称
求最大公约数
指导教师
张晶
教师评语
该同学是否了解实验原理：
A.了解□B.基本了解□C.不了解□
该同学的实验能力：
A.强□B.中等□C.差□
该同学的实验是否达到要求：
A.达到□B.基本达到□C.未达到□
实验报告是否规范：
A.规范□B.基本规范□C.不规范□
实验过程是否详细记录：
A.详细□B.一般□C.没有□
教师签名：
年月日
一、上机目的及内容
上机内容
求两个自然数m和n的最大公约数。
上机目的
（1）复习数据结构课程的相关知识，实现课程间的平滑过渡；
（2）掌握并应用算法的数学分析和后验分析方法；
（3）理解这样一个观点：
不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。
二、实验原理及基本技术路线图（方框原理图或程序流程图）
（1）至少设计出三个版本的求最大公约数算法；
（2）对所设计的算法采用大O符号进行时间复杂性分析；
（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间；
（4）通过分析对比，得出自己的结论。
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
1台PC及VISUALC++6.0软件
四、实验方法、步骤（或：
程序代码或操作过程）
1.连续整数检测
#include
//连续整数检测
intgcd（intm,intn）
{
intt=m>n?
n:
m;
while（true）
{
if（m%t==0）
{
if（n%t==0）
{
returnt;
}
elset--;
}
elset--;
}
}
voidmain（）
{
intm,n;
cout<<"Inputmandn:
"<while（cin>>m>>n）
{
cout<<"Output:
"<cout<}
}
2.欧几里得算法
#include
//欧几里德算法
intgcd（intm,intn）
{
intr;
while（n!
=0）
{
r=m%n;
m=n;
n=r;
}
returnm;
}
voidmain（）
{
intm,n;
cout<<"Inputmandn:
"<while（cin>>m>>n）
{
cout<<"Output:
"<cout<}
}
3.分解质因数
#include
//分解质因数法
intFJ（intm,intn）
{
if（m==1||n==1）
{
cout<<"最大公约数为：
1"<}
inta[10],b[10],s,t=2,i=0,all,m1,n1,i1,i2;
m1=m;
n1=n;
cout<while
（1）
{
s=m1%t;//求m1除以t（t为2）的余数s
if（s==0）
{
m1=m1/t;
a[i]=t;//把t摆在数组a[]中
cout<i++;
t=2;
all=1;
for（i1=0;i1{
all=all*a[i1];
}
if（m==all）break;//判断该整数的质因数是否全部求出
cout<<"*";
}
elset++;
}
i=0;//把i重置为0，进行整数n的求质因数
cout<cout<while
（1）
{
s=n1%t;
if（s==0）
{
n1=n1/t;
b[i]=t;
cout<i++;
t=2;
all=1;
for（i2=0;i2{
all=all*b[i2];
}
if（n==all）break;
cout<<"*";
}
elset++;
}
cout<all=1;
for（ints1=0;s1{//利用循环，求出公共质因数
for（ints2=0;s2{
if（a[s1]==b[s2]）
{
all=all*a[s1];
b[s2]=0;
break;
}
}
}
cout<<"最大公约数为：
"<return0;
}
voidmain（）
{
intm,n;
charc;
cout<<"请分别输入两个整数"<cin>>m>>n;
FJ（m,n）;
}
3.计数法和计时法分别测算算法的运行时间
#include
#include"iostream.h"
#include"stdio.h"
#include"stdlib.h"
#include"time.h"
#defineN100
intw1,w2,w3;//用于计数
intf1（intm,intn）//连续整数检测
{
intt=m>n?
n:
m;
while（true）
{
if（m%t==0）
{
if（n%t==0）
{
returnt;
}
elset--;
w1++;
}
elset--;w1++;
}
}
intf2（intm,intn）//欧几里德算法
{
intr;
while（n!
=0）
{
r=m%n;
m=n;
n=r;
w2++;
}
returnm;
}
intf3（intm,intn）//分解质因数法
{
if（m==1||n==1）
{
cout<<"最大公约数为：
1";
}
inta[10],b[10],s,t=2,i=0,all,m1,n1,i1,i2;
m1=m;
n1=n;
//cout<while
（1）
{
s=m1%t;//求m1除以t（t为2）的余数s
if（s==0）
{
m1=m1/t;
a[i]=t;//把t摆在数组a[]中
//cout<i++;
t=2;
all=1;
w3++;
for（i1=0;i1{
all=all*a[i1];
}
if（m==all）break;//判断该整数的质因数是否全部求出
//cout<<"*";
}
elset++;w3++;
}
i=0;//把i重置为0，进行整数n的求质因数
//cout<//cout<while
（1）
{
s=n1%t;
if（s==0）
{
n1=n1/t;
b[i]=t;
//cout<i++;
t=2;
all=1;w3++;
for（i2=0;i2{
all=all*b[i2];
}
if（n==all）break;
//cout<<"*";
}
elset++;w3++;
}
//cout<all=1;
for（ints1=0;s1{//利用循环，求出公共质因数
for（ints2=0;s2{
if（a[s1]==b[s2]）
{
all=all*a[s1];
b[s2]=0;w3++;
break;
}
}
}
//cout<<"最大公约数为：
"<returnall;
}
voidmain（）
{
intm,n;
cout<<"Inputmandn:
"<cin>>m>>n;
intk;
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\n\n"）;
printf（"方法一：
%d\n",w1）;
printf（"方法二：
%d\n",w2）;
printf（"方法三：
%d\n",w3）;
printf（"\n--------------------\n"）;
floata,i;
clock_tstart,finish;
doubleusetime;
i=0;
start=clock（）;
while（i<100000）
{
f1（m,n）;
i++;
}
finish=clock（）;
usetime=finish-start;
printf（"方法一用时%.f*10^（-6）豪秒\n",usetime）;
i=0;
start=clock（）;
while（i<100000）
{
f2（m,n）;
i++;
}
finish=clock（）;
usetime=finish-start;
printf（"方法二用时%.f*10^（-6）豪秒\n",usetime）;
i=0;
start=clock（）;
while（i<100000）
{
f3（m,n）;
i++;
}
finish=clock（）;
usetime=finish-start;
printf（"方法三用时%.f*10^（-6）豪秒\n",usetime）;
}
五、实验过程原始记录（测试数据、图表、计算等）
1.连续整数检测
2.欧几里得算法
3.分解质因数
4.计数法和计时法分别测算算法的运行时间
六、实验结果、分析和结论（误差分析与数据处理、成果总结等。
其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）
第一种，连续整数检测法。
根据代买考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做一次，所以O（n）=n/2。
第二种，欧几里得算法。
根据代码辗转相除得到欧几里得的O（n）=logn。
第三种，分解质因数法。
根据代码分解质成因子算法O（n）=n^2+n/2。
结果分析：
从前面的复杂度O（n）的出欧几里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看结果恰好和前面的复杂度得到的结果一致，所以的出结论：
欧几里得算法最优。
通过对三种计算最大公约数方法的比较，了解了算法设计的初步概念，并对求公约数问题有了更深的认识。
了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大，这提示我们在以后写算法的时候要找出最优算法。
也告诉了我们，算法对于一个程序的重要性，我们要对这门课产生足够的重视。
注：
教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。
升级会员 