昆明理工大学 算法 实验一 求最大公约数

昆明理工大学信息工程与自动化学院学生实验报告

（ 2011 —2012 学年 第 1 学期 ）

课程名称：算法分析与设计 开课实验室：信自楼机房445 2011 年10月 12日 年级、专业、班 计科093 学号 200910405310 实验项目名称 教师评求最大公约数 A.了解□ A.强 □ A.达到□ A.规范□ A.详细□ 姓名 孙浩川 成绩 指导教师 张晶 B.基本了解□ B.中等 □ B.基本达到□ B.基本规范□ B.一般 □ C.不了解□ C.差 □ C.未达到□ C.不规范□ C.没有 □ 该同学是否了解实验原理： 该同学的实验能力： 该同学的实验是否达到要求： 实验报告是否规范： 实验过程是否详细记录： 语 教师签名： 年 月 日 一、上机目的及内容

上机内容

求两个自然数m和n的最大公约数。 上机目的

（1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法；

（3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不

同，解题效率也不同。

二、实验原理及基本技术路线图（方框原理图或程序流程图）

（1）至少设计出三个版本的求最大公约数算法；

（2）对所设计的算法采用大O符号进行时间复杂性分析；

（3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。

三、所用仪器、材料（设备名称、型号、规格等或使用软件）

1台PC及VISUAL C++6.0软件

四、实验方法、步骤（或：程序代码或操作过程）

1.连续整数检测

-1-

#include

//连续整数检测 int gcd(int m,int n) {

int t=m>n ? n:m; while(true) {

if(m%t==0) {

if(n%t==0) {

return t; } else t--; }

else t--; } }

void main() {

int m,n;

cout<<\ while(cin>>m>>n) {

cout<<\ cout<

2.欧几里得算法 #include

//欧几里德算法 int gcd(int m,int n) {

int r;

while( n!=0) {

r = m%n; m=n; n=r;

-2-

}

return m; }

void main() {

int m,n;

cout<<\ while(cin>>m>>n) {

cout<<\ cout<

3.分解质因数 #include

//分解质因数法 int FJ(int m,int n) {

if(m==1||n==1) {

cout<<\最大公约数为：1\ } int a[10],b[10],s,t=2,i=0,all,m1,n1,i1,i2; m1=m; n1=n; cout<

-3-

cout<<\ } else t++; } i=0; //把i重置为0，进行整数n的求质因数 cout<

while(1) { s=n1%t; if(s==0) { n1=n1/t; b[i]=t; cout<

-4-