算法试验一求最大公约数实验
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
昆明理工大学信息工程与自动化学院学生实验报告
( 2012 — 2013 学年 第 1 学期 ) 课程名称:算法设计与分析 开课实验室:信自楼应用、网络机房445 2012 年10月25日 年级、专业、计科102班 学号 201010405219 姓名 朱海斌 成绩 班
实验项目名称 指导教师 张晶 求最大公约数
教
该同学是否了解实验原理: A.了解? B.基本了解? C.不了解? 师该同学的实验能力: A.强 ? B.中等 ? C.差 ?
该同学的实验是否达到要求: A.达到? B.基本达到? C.未达到? 评实验报告是否
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
: A.规范? B.基本规范? C.不规范?
实验过程是否详细记录: A.详细? B.一般 ? C.没有 ? 语
教师签名:
年 月 日 一、上机目的及内容
1.上机内容
求两个自然数m和n的最大公约数。
2.上机目的
(1)复习数据结构课程的相关知识，实现课程间的平滑过渡;
(2)掌握并应用算法的数学分析和后验分析方法;
(3)理解这样一个观点:不同的算法能够解决相同的问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
，这些算法的解题思路不同，复杂程度不同，解题效率也不同。
二、实验原理及基本技术路线图(方框原理图或程序流程图)
(1)至少设计出三个版本的求最大公约数算法;
(2)对所设计的算法采用大O符号进行时间复杂性分析;
(3)上机实现算法，并用计数法和计时法分别测算算法的运行时间;
(4)通过分析对比，得出自己的结论。
三、所用仪器、
材料
关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料
(设备名称、型号、规格等或使用软件)
1台PC及VISUAL C++6.0软件
-1-
四、实验方法、步骤(或:程序代码或操作过程)
开始 算法一算法描述:
? 输入m 和n; 输入m和n ? 求m除以n的余数r;
r=m % n ? 若r等于0，则n为最大公约数，算法结束;
Y 否则执行第?步; r=0
N ? 将n的值放在m中，将r的值放在n中;
? 重新执行第?步。 m=n;n=r 连续整数检测算法描述
各个算法时间复杂度和运算速度: 输出n 算法一 运算速度为 O(n2)，其中 n 为输入数值的位数。
结束 算法二 时间复杂度:T(n)=O(n); 基本语句执行次数C(n)=n; 算法三 时间复杂度T(n)=O(n)
五、实验过程原始记录( 测试数据、图表、计算等) 程序代码:
算法一
#include
int CommonFactor(int m, int n) {
int r=m % n;
while (r!=0)
{
m=n;
n=r;
r=m % n;
}
return n;
}
void main( )
{
cout<
int gcd(int m,int n)
{
int t=(m>n?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);
}
算法三:欧几里得算法的减法版本
#include/ int fun(int m,int n)
{
while(n!=m)
{
-3-
if(m>n)m=m-n;
else n=n-m;
}
return m;
}
void main()
{
int a,b;
cin>>a>>b;
cout<
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获)
首先要对这个问题进行分析，选择你所想用的算法，使这个程序能键盘输入自己想求的两个数，回车结束，即可看到该算法求出的最大公约数。对这次试验，我只能用一些简单的代码进行编程，由于我的编程水平有限，我所用的代码也很简单，在算法三中，存在一个问题有待改进，那就是输入的两个数在分解质因数时只能是分解出三个质因数，否则出错。
对于复杂度的求解，可以根据我的结果分析得到欧几里得算法的是最优算法，连续整除法其次，最复杂的是分解质因数算法，再从代码运行的计数器和计算的时间来看所得结果一致，所以得出结论:欧几里得算法最优。不过用代码求解复杂度我没有能够成功，以后还得继续改进和学习。
从这次实验中，我复习了C语言代码，同时也通过算法分许用三种方法求解出了最大公约数这个问题。从这个试验的结果我了解到了算法的优与劣的差别，虽然得到的是同样的结果，但是需要的时间和资源却相差很大，这提示我们在以后写算法的时候要找出最优算法。可见算法分析与设计课程的对计编程的人来说是多么的重要，在以后写程序过程中要时刻提醒自己找最优算法，当然得先学会O(n)的分析。在以后的学习中我要学会多实践、多分析，在不停的改正错误中提高自己。
注:教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。
-4-
-5-
浙公网安备 33021202002483