资源描述：
《实验三算法和算法分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验二算法和算法分析学生姓名专业班级学号实验成绩指导老师（签名）日期实验目的和要求1.通过对算法的分析，了解提高算法的运算速度和降低算法的存储空间Z间的矛盾。2.通过对算法复杂度的分析，掌握计算时间复杂度和空间复杂度的基本方法。3.初步掌握测试算法运行吋间的基木方法。二.实验内容1、根据算法编写程序已知输入x,y,z三个不相等的整数，试根据如下算法（N・S图）编写一个C语言函数，实现三个数从小到大顺序的输出。一三个数排序算法的N・S图提示：一个矩形框里的处理对能用一•条C语句实现，也可能用多条C语句实现。例如：“x-y：
2、t=x;x=y;y=t;"。并且,N・S图中不包括变量的定义,但在C语言函数中，变量必须先定义再使用。要求：把该程序存放在文件test1_3_1.cpp中，编译并调试程序，直到正确运行。并请分析：该算法要进行_3次比较，在最好的情况下需要交换数据元素0次，在最坏的情况下需要交换数据元素9次。2、测试算法的运行时间在此，我们通过一个比较两个算法执行效率的程序例子，掌握测试算法运行时间的基本方法。这里涉及到C语言中标准的函数库sys/timebosys/timeb函数库中提供了处理与时间相关的函数。其中函数ftimc的功能是获取当丽的系统时间。步骤1：输入两个C语言主程序test
3、1_3_2.cpp和test1_3_3.cpp。主文件(test1_3_2.cpp):#inelude#inelude〃时间函数voidmain(){1timebt1,t2;2longt;3doublex,sum=1,sum1;4inti,j,n;5printf(H请输入x,n：n);6scanf(H%lf,%d",&x,&n);7ftime(&t1);〃求得当前时间8for(i=1;iv二n;i++)9{10sum仁1;11for(j=1;j<=i;j++)12sum1=sum1*(-1.0/x);13sum+=sum1;14}1
4、5ftime(&t2);//求得当前时间16t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);//计算时间差,转换成毫秒17printf(,,sum=%lf用时％ld毫秒”，sum,t);该算法的N-S图如下所示。为了便于说明程序段与N-S图之间的对应关系，我们将函数体屮的语句加上了标号，并与图屮相应的处理框、循环框或判断框相对应。输入x,n的值求当前时间i=l6—7主文件(test1_3_3.cpp^=rn#include#ineludevoidmain()sum1=1j=lti
5、mebt1,t2;longt;doublex,sum1=1,sum=1;suml=suml*(-1.0/x)…内夕I十sum1inti,n;printf(“请输入x,n:n);scanf(”％lf,%d“，&x,&n);ftime(&t1);for(i=1;i<=n;i++)jT十1计算并输出求解sum所花费的时间…15…16」7sum1*=-1.0/x;sum+=sum1;//求得当前时间}ftime(&t2);t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);//计算时间差,转换成毫秒printf(',sum=%lf用时％l
6、d毫秒”，sum,t);步骤2：请读懂这两个算法，并分析：这两个算法的功能是：计算出l/(-x厂l+l/(-x厂2+…+l/(-x厂n的值并但算出计算的时间这两个算法在程序结构上的区别是：第-个有两个循环结构第二个只有一个它们的时间复杂度分别是：test1_3_2.cpp为,怕st1_3_3.cpp为o你的判断是：算法3优于算法2o调试这两个测试程序,并写出运行结果(其中用时与计算机的配置有关)。test1_3_2.cpp的运行结果为：输入x,n：99,99999；输出为：sum=O.990000_用时469豪秒。test1_3_3.cpp的运行结呆为：输入x,n：99,
7、99999999；输出为：sum二0.990000用吋172毫秒。3、编写程序并分析时间复杂度编写高效率的程序计算1!/2+2!/3+..・+i!/(i+1)+.・•+n!/(n+1)的值,把该程序存放在文件test1_3_4.cpp中，并分析：该算法的时间复杂度为O(n)该算法的时间效率是否已经最优没冇比较。自认为是的4、填写实验报告内容，实验报告文件取名为report3.doco5、上传实验报告文件report3.doc＞源程序文件test1_3_1.cpp、test1_3_2・cpp、test1_
