实验3 算法和算法分析.doc

浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验三 算法和算法分析 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1. 通过对算法的分析，了解提高算法的运算速度和降低算法的存储空间之间的矛盾。2. 通过对算法复杂度的分析，掌握计算时间复杂度和空间复杂度的基本方法。3. 初步掌握测试算法运行时间的基本方法。二. 实验内容1、 根据算法编写程序已知输入x，y，z三个不相等的整数，试根据如下算法（N-S图）编写一个C语言函数，实现三个数从小到大顺序的输出。三个数排序算法的N-S图 提示：一个矩形框里的处理可能用一条C语句实现，也可能用多条C语句实现。例如：“xy：t=x; x=y; y=t;”。并且，N-S图中不包括变量的定义，但在C语言函数中，变量必须先定义再使用。要求：把该程序存放在文件test1_3_1.cpp中，编译并调试程序，直到正确运行。并请分析：该算法要进行_3_次比较，在最好的情况下需要交换数据元素_0_次，在最坏的情况下需要交换数据元素_3_次。2、测试算法的运行时间在此，我们通过一个比较两个算法执行效率的程序例子，掌握测试算法运行时间的基本方法。这里涉及到C语言中标准的函数库sys/timeb。sys/timeb函数库中提供了处理与时间相关的函数。其中函数ftime的功能是获取当前的系统时间。步骤1：输入两个C语言主程序test1_3_2.cpp和test1_3_3.cpp。主文件 (test1_3_2.cpp) ：# include # include /时间函数 void main()1 timeb t1, t2;2 long t;3 double x, sum=1, sum1;4 int i, j, n;5 printf(请输入x，n：) ;6 scanf(%lf,%d, &x, &n) ;7 ftime(&t1) ;/ 求得当前时间8 for(i=1; i=n; i+)9 10 sum1=1;11 for(j=1; j=i; j+)12 sum1=sum1*(-1.0/x) ;13 sum+=sum1;14 15 ftime(&t2) ;/ 求得当前时间16 t=(t2.time-t1.time)*1000+(litm) ; /计算时间差，转换成毫秒17 printf(sum=%lf 用时%ld毫秒n, sum, t) ; 该算法的N-S图如下所示。为了便于说明程序段与N-S图之间的对应关系，我们将函数体中的语句加上了标号，并与图中相应的处理框、循环框或判断框相对应。主文件 (test1_3_3.cpp) ： # include # include void main() timeb t1, t2; long t; double x, sum1=1, sum=1; int i, 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.time-t1.time)*1000+(litm) ; / 计算时间差，转换成毫秒 printf(sum=%lf 用时%ld毫秒n, sum, t) ; 步骤2：请读懂这两个算法，并分析：这两个算法的功能是： 计算 1!/2 + 2!/3 +.+ i!/(i+1) +.+ n!/(n+1)的值，并计算运算所需的时间 这两个算法在程序结构上的区别是：_使用的算法不同，程序的简洁性，易读性，快捷性也不同。_它们的时间复杂度分别是：test1_3_2.cpp为 o（n3） ， 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毫秒_ 。test1_3_3.cpp的运行结果为： 输入x, n：_10,1000 _； 输出为：_ sum=0.909091_用时0毫秒_。3、编写程序并分析时间复杂度编写高效率的程序计算 1!/2 + 2!/3 +.+ i!/(i+1) +.+ n!/(n+1)的值，把该程序存放在文件test1_3_4.cpp中，并分析：该算法的时间复杂度为 o（n3） 该算法的时间效率是否已经最优 否 4、填写实验报告内容，实验报告文件取名为report3.doc。5、上传实验报告文件report3.doc、源程序文件test1_3_1.cpp、test1_3_2.cpp、test1_3_3.cpp及test1_3_4.cpp到Ftp服务器上自己的文件夹下。三. 实验结果与分析（包括运行结果截图、结果分析等）程序1第四题程序3：四. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录-源程序】第一题：#includeint main(void)int x,y,z,t;scanf(%d%d%d,&x,&y,&z);if(xy)x=x;else t=x; x=y; y=t; if(xz) x=x;else t=x; x=z; z=t; if(yz) z=z;else t=y; y=z; z=t; printf(x=%d,y=%d,z=%dn,x,y,z);return 0;第三题：# include # include void main() timeb t1, t2; long t; double sum1, sum=0; int i,j, n; printf(请输入n: ) ; scanf(%d, &n) ;ftime(&t1) ; for(i=1;i=n;i+) sum1=1;for(j=1;j=i;j+)sum1=sum