1.算法求最大公约数实验报告格式.doc

昆明理工大学信息工程与自动化学院学生实验报告 （ 2012 — 2013 学年 第 1 学期 ） 课程名称：算法设计与分析 开课实验室：信自楼机房442 2012 年10月 18日 年级、专业、班 计算机科学与技术 学号 201010405109 姓名 刘哲 成绩 实验项目名称 求最大公约数 指导教师 吴霖 教师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强 □ B.中等 □ C.差 □ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □ 教师签名： 年 月 日 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）至少设计出三个版本的求最大公约数算法； 第一种方法：连续整数检测法 t=min{m,n}; m除以t,如果余数是0，则执行步骤3，否则，执行第4步； n除以t，如果余数为0，返回t的值作为结果，否则，执行第4步； t=t-1，转第2步 第二种方法：欧几里得算法 r=m%n; 循环直到r=0 m=n； n=r； r=m%n； 输出n； 第三种方法：分解质因数法 将m分解质因数 将n分解质因数 提取m和n中的公共质因数 将m和n中的公共质因数相乘，乘积作为结果输出 （2）对所设计的算法采用大O符号进行时间复杂性分析； 第一种方法：连续整数检测法 根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好 情况是只做了1次，可以得出O（n）=n/2; 第二种方法：欧几里得算法 根据代码辗转相除得到欧几里得的O(n)= log n 第三种方法：分解质因数法 根据代码分解质因子算法O(n)=n2+n/2 （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； 《由于我没想出算法运行时间怎么计时，我就问了下学长怎么求仅供参考,但程序我已经自己调通了》 为了计算每种算法运行的次数所用的时间，我将代码稍加改动添加代码如下： 其中计数器采用的是没做一次循环就加1； 计时器是记住开始时间和结束时间，用结束时间减开始时间。 #includeiostream.h #includestdio.h #includestdlib.h #includetime.h #define N 100 int w,w2,w3;//用于计数 int f1(int m,int n) { int t; if(mn)t=n; else t=m; while(t) { if(m%t==0n%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=2,j=0,h=0; int a[N],b[N],c[N]; while(in) { 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(%d ,a[i]); i++; w3++; } //printf(\n); i=2; j=0; while(im) { if(m%i==0) { j++; b[j]=i; m=m/i; w3++; } else { i++; w3++; } } j++;