资源描述：
《实验三 算法和算法分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、他浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验三算法和算法分析学生姓名专业班级—学号实验成绩指导老师（签名）日期实验目的和要求1.通过对算法的分析，了解提高算法的运算速度和降低算法的存储空间之间的矛盾。2.通过对算法复杂度的分析，掌握计算吋间复杂度和空间复杂度的基本方法。3.初步掌握测试算法运行吋间的基木方法。实验内容1、根据算法编写程序已知输入x,y,z三个不相等的整数，试根据如下算法（N・S图）编写一个C语言函数，实现三个数从小到大顺序的输出。三个数排序算法的N・S图提示：一个矩形框里的处理可能用一条C语句实现，也可能用多条C语句实现。例如：“x-y：t二x;x二
2、y;y二t;”o并且,N・S图中不包括变量的定义,但在C语言函数中，变量必须先定义再使用。要求：把该程序存放在文件test3_1-cpp•P,编译并调试程序，直到正确运行。并请分析：该算法要进行_3_次比较，在最好的情况下需要交换数据元素—0—次，在最坏的情况下需要交换数据元索_3—次。2.测试算法的运行时间在此，我们通过一个比较两个算法执行效率的程序例子，掌握测试算法运行吋间的基本方法。这里涉及到C语言屮标准的函数库sys/timebosys/timeb函数库屮提供了处理与吋间相关的函数。其屮函数ftime的功能是获取当前的系统吋间。步骤1：输入两个C语言主程序test3_2.cp
3、p和test3_3.cpp0主文件(test3_2.cpp):#inelude#include〃吋间函数voidmain(){1timebt1,t2;2longt;3doublex,sum=1,sum1;4inti,j,n;5printf("请输入x,n：”)；6sc8nf(”％lf,%cT,&x,&n);7ftime(&t1);〃求得当前时间8for(i=1;i<=n;i++)9{10sum仁11for(j=1;j<=i;j++)12sum仁sum^TCl.O/x);13sum+=sum1;1}2ftime(&t2);//求得当前时间3t
4、=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);//计算吋间差,转换成毫秒4printf(Msum=%lf用时％ld毫秒比sum,t);}该算法的N-S图如下所示。为了便于说明程序段与N-S图之间的对应关系，我们将函数体屮的语句加上了标号，并与图屮相应的处理框、循环框或判断框相对应。主文件(test3_3.cpp):#include#includevoidmain(){timebt1,t2;longt;doublex,sum1=1,sum=1;inti,n;printfC'W输入x,n:H)
5、:scanf(H%lf,%dH,&x,&n);ftime(&t1);//求得当前吋间for(i=1;i<=n;i++){sum1*=-1.0/x;sum+=sum1;ftime(&t2);//求得当前吋间t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);//计算时间差,转换成毫秒printf(Hsum=%lf用时％ld毫秒F,sum,t);}步骤2：请读懂这两个算法，并分析:这两个算法的功能是:计算1!/2+2!/3+・・・+i!/(i+l)+・・・+n!/(n+l)的值，并计算运算所需的时间(运行前后差)。这两个算法在稈•序结构上的
6、区别是:计算1!/2+2!/3+…+i!/(i+l)+・・・+n!/(n+1)的值的循环语句简洁性，易读性，快捷性。它们的时间复杂度分别是：test3_2.cpp为7+5n+nmi)test33.cdd为7+3n。你的判断是：算法_test3_3・cpp_优于算法_test3_2・cpp。步骤3：调试这対个测试程序，并写出运行结果(其小用吋与计算机的配置有关)。test3_2.cpp的运行结果为：输入x,n：10,1000「；输出为：sum=0.909091—用时16毫秒。test3_3.cpp的运行结果为：输入x,n：10,1000；输出为：sum=0.909091—用时0毫秒3、
7、编写程序并分析时间复杂度编写高效率的程序计算1!/2+2!/3+...+i!/(i+l)+・・・+n!/(n+1)的值,把该程序存放在文件test3_4.cpp中，并分析：该算法的时间效率是否己经最优否4、填写实验报告内容，实验报告文件取名为report3.doco5、上传实验报告文件report3.doc>源程序文件test3_1.cpp>test3_2.cpp、test3_3.cpp及test3_4.cpp到Ftp服务器JL（ftp://10.61.1
