实验3算法和算法分析

《实验3算法和算法分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验二算法和算法分析学生姓名专业班级—学号实验成绩指导老师（签名）日期一.实验目的和要求1.通过对算法的分析，了解提高算法的运算速度和降低算法的存储空间之间的矛盾。2.通过对算法复杂度的分析，掌握计算时间复杂度和空间复杂度的基本方法。3.初步掌握测试算法运行时间的基本方法。二.实验内容1、根据算法编写程序已知输入x,y,z三个不相等的整数，试根据如下算法（N・S图）编写一个C语言函数，实现三个数从小到大顺序的输出。输入三个数心打6~~~----〜〜〜x>yx与y交换;：x—yV.人与么交换

2、;；入乙Y""***y>z—*—***y与乙交换;：y.-♦厶输出入”卄乙的值1三个数排序算法的N・S图放最小数《＞匕牛己存放次小数》提示：一个矩形框里的处理可能用一条C语句实现，也可能用多条C语句实现。例如：“x-y：t二x;x二y;y二t;”。并且,N・S图中不包括变量的定义,但在C语言函数中，变量必须先定义再使用。要求：把该程序存放在文件test1_3_1・cpp屮，编译并调试程序，直到正确运行。并请分析：该算法耍进行—3—次比较，在最好的情况卜•需耍交换数据元素0次，在最坏的情况下需要交换数据元素3次。2、测试算法的运行时间在此，我们通

3、过一个比较两个算法执行效率的程序例子，掌握测试算法运行时间的基本方法。这里涉及到C语言中标准的函数库sys/timebcsys/timeb函数库屮提供了处理与吋间相关的函数。其屮函数ftime的功能是获取当前的系统吋间。步骤1：输入两个C语言主程序test1_3_2.cpp和test1_3_3.cppo主文件(test1_3_2.cpp):#inelude#include〃吋间函数voidmain(){1timebt1,t2;2longt;3doublex,sum=1,sum1;4inti,j,n;1

4、printf(”请输入x,n:”)；2scanf(”％lf,%d”,&x,&n);3ftime(&⑴；//求得当前时间4for(i=1;iv二n;i++)5{6surrd=d;7fOrG=1;j<=i;j++)8sum仁sum1*(-1.0/x);9sum+=sum1;10}11ftime(&t2);〃求得当前吋间12t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);〃计算时间差,转换成毫秒13printf(,,sum=%lf用时％ld毫秒”，sum,t);}该算法的N-S图如下所示。为了便于

5、说明程序段与N-S图之间的对应关系，我们将函数体中的语句加上了标号，并与图中相应的处理框、循环框或判断框相对应。主文件(test1_3_3.cpp):#inelude#includevoidmain()timebt1,t2;longt;doublex,sum1=1,sum=1;inti,n;printf("请输入x,n:");scanf(H%lf,%dM,&x,&n);ftime(&t1);//求得当前时间for(i=1;i<二n;i++){sum1*=-1.0/x;sum+=sum1;}ftime(

6、&⑵；//求得当前时间t=(t2.time-t1,time)*1000+(t2.millitm-t1.millitm);〃计算时间差,转换成毫秒printf(',sum=%lf用吋％ld毫秒”，sum,t);}步骤2：请读懂这两个算法，并分析：这两个算法的功能是：计算1!/2+2!/3+・・・+i!/(i+l)+・・・+n!/(n+1)的值,并计算运算所需的时间这两个算法在程序结构上的区别是：使用的算法不同，程序的简洁性，易读性，快捷性也不同。一它们的时间复杂度分别是：test1_3_2.cpp为,test1_3_3.cpp为o(n)。你的

7、判断是：算法—test1_3_3.cpp优于算法_test1_3_2.cpp。步骤3：调试这两个测试程序，并写出运行结果(其中用时与计算机的配置有关)otest1_3_2.cpp的运行结果为：输入x,n：10,1000；输出为：sum=0.909091—用时16毫秒。test1_3_3.cpp的运行结呆为：输入x,n：10,1000；输岀为：sum=O.909091_用时0毫秒。3、编写程序并分析时间复杂度编写高效率的程序计算1!/2+2!/3+・・・+i!/(i+1)+・..+n!/(n+4)的值，把该程序存放在文件test1_3_4.cpp

8、中，并分析：该算法的吋间复杂度为o(23)该算法的时间效率是否已经最优4、填写实验报告内容，实验报告文件取名为report3.doco5、上传实验报告