算法試验一求最大公约数实验报告.docVIP

昆明理工大学信息工程与自动化学院学生实验报告 （ 2012 — 2013 学年 第 1 学期 ） 课程名称：算法设计与分析 开课实验室：信自楼应用、网络机房445 2012 年10月25日 年级、专业、班 计科102班 学号 201010405219 姓名 朱海斌 成绩 实验项目名称 求最大公约数 指导教师 张晶 教师评语 该同学是否了解实验原理： A.了解□ B.基本了解□ C.不了解□ 该同学的实验能力： A.强 □ B.中等 □ C.差 □ 该同学的实验是否达到要求： A.达到□ B.基本达到□ C.未达到□ 实验报告是否规范： A.规范□ B.基本规范□ C.不规范□ 实验过程是否详细记录： A.详细□ B.一般 □ C.没有 □ 教师签名： 年 月 日 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 算法一算法① 输入m 和n； ② 求m除以n的余数r； ③ 若r等于0，则n为最大公约数，算法结束； 否则执行第④步； ④ 将n的值放在m中，将r的值放在n中； ⑤ 重新执行第②步。连续整数检测算法一? 运算速度为 O(n2)其中 n 为输入数值的位数。 时间复杂度：T(n)=O(n); 基本语句执行次数C(n)=n; 时间复杂度T(n)=O(n)算法一? #includestdio.h int gcd(int m,int n) { int t=(mn?n:m); while(m%t!=0 ||n%t!=0) { if(m%t==0) { if(n%t==0) return t; else t=t-1; } else t=t-1; } printf(%d\n,t); } void main() { int m,n; scanf(%d,m); scanf(%d,n); gcd(m,n); } 算法三：欧几里得算法的减法版本 #includeiostream.h/ int fun(int m,int n) { while(n!=m) { if(mn)m=m-n; else n=n-m; } return m; } void main() { int a,b; cinab; coutfun(a,b); } -4- N 开始 输入m和n r=m % n r=0 m=n；n=r 输出n 结束 Y