实验3 算法和算法分析

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

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

2、C语句实现，也可能用多条C语句实现。例如：“x↔y：t=x;x=y;y=t;”。并且，N-S图中不包括变量的定义，但在C语言函数中，变量必须先定义再使用。要求：把该程序存放在文件test1_3_1.cpp中，编译并调试程序，直到正确运行。并请分析：该算法要进行___3___次比较，在最好的情况下需要交换数据元素____0__次，在最坏的情况下需要交换数据元素__3____次。2、测试算法的运行时间在此，我们通过一个比较两个算法执行效率的程序例子，掌握测试算法运行时间的基本方法。这里涉及到C语言中标准的函数库sys/timeb

3、。sys/timeb函数库中提供了处理与时间相关的函数。其中函数ftime的功能是获取当前的系统时间。步骤1：输入两个C语言主程序test1_3_2.cpp和test1_3_3.cpp。主文件(test1_3_2.cpp)：#include#include//时间函数voidmain(){1timebt1,t2;2longt;3doublex,sum=1,sum1;4inti,j,n;5printf("请输入x，n：");6scanf("%lf,%d",&x,&n);7ftime(

4、&t1);//求得当前时间8for(i=1;i<=n;i++)9{10sum1=1;11for(j=1;j<=i;j++)12sum1=sum1*(-1.0/x);13sum+=sum1;14}15ftime(&t2);//求得当前时间16t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);//计算时间差，转换成毫秒17printf("sum=%lf用时%ld毫秒",sum,t);}该算法的N-S图如下所示。为了便于说明程序段与N-S图之间的对应关系，我们将函数体中的语句加上

5、了标号，并与图中相应的处理框、循环框或判断框相对应。主文件(test1_3_3.cpp)：#include#includevoidmain(){timebt1,t2;longt;doublex,sum1=1,sum=1;inti,n;printf("请输入x，n:");scanf("%lf,%d",&x,&n);ftime(&t1);//求得当前时间for(i=1;i<=n;i++){sum1*=-1.0/x;sum+=sum1;}ftime(&t2);//求得当前时间t=(t2.

6、time-t1.time)*1000+(t2.millitm-t1.millitm);//计算时间差，转换成毫秒printf("sum=%lf用时%ld毫秒",sum,t);}步骤2：请读懂这两个算法，并分析：这两个算法的功能是：计算1!/2+2!/3+...+i!/(i+1)+...+n!/(n+1)的值，并计算运算所需的时间这两个算法在程序结构上的区别是：_____________使用的算法不同，程序的简洁性，易读性，快捷性也不同。___________________________________________

7、_____________________________它们的时间复杂度分别是：test1_3_2.cpp为o（n^3），test1_3_3.cpp为o(n)。你的判断是：算法___test1_3_3.cpp____优于算法_test1_3_2.cpp______。步骤3：调试这两个测试程序，并写出运行结果(其中用时与计算机的配置有关)。test1_3_2.cpp的运行结果为：输入x,n：__________10,1000______________________；输出为：_____sum=0.909091___用时16

8、毫秒_______。test1_3_3.cpp的运行结果为：输入x,n：____10,1000_____________________________；输出为：_______sum=0.909091___用时0毫秒_________________。3、编写程序并分析时间复杂度编写高效率