实验03 算法和算法分析

Twinkle 贡献于2015-03-28

作者 liujun  创建于2007-08-30 05:41:00   修改者dell  修改于2014-01-15 15:16:29字数2842

文档摘要: 1.通过对算法的分析,了解提高算法的运算速度和降低算法的存储空间之间的矛盾。2.通过对算法复杂度的分析,掌握计算时间复杂度和空间复杂度的基本方法。3.初步掌握测试算法运行时间的基本方法。实验内容根据算法编写程序已知输入x,y,z三个不相等的整数,试根据如下算法(N-S图)编写一个C语言函数,实现三个数从小到大顺序的输出。
关键词:

浙江大学城市学院实验报告 课程名称 数据结构基础 实验项目名称 实验三 算法和算法分析 学生姓名 专业班级 学号 实验成绩 指导老师(签名 ) 日期 一. 实验目的和要求 1. 通过对算法的分析,了解提高算法的运算速度和降低算法的存储空间之间的矛盾。 2. 通过对算法复杂度的分析,掌握计算时间复杂度和空间复杂度的基本方 法。 3. 初步掌握测试算法运行时间的基本方法。 二. 实验内容 1、 根据算法编写程序 已知输入x,y,z三个不相等的整数,试根据如下算法(N-S图)编写一个C语言函数,实现三个数从小到大顺序的输出。 三个数排序算法的N-S图 提示:一个矩形框里的处理可能用一条C语句实现,也可能用多条C语句实现。例如:“x↔y: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+(t2.millitm-t1.millitm) ; //计算时间差,转换成毫秒 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+(t2.millitm-t1.millitm) ; // 计算时间差,转换成毫秒 printf("sum=%lf 用时%ld毫秒\n", sum, t) ; } 步骤2:请读懂这两个算法,并分析: 这两个算法的功能是: 计算 1 +1/(-x)^1+ 1/(-x)^2 +...+ 1/(-x)^i...+ 1/(-x)^n的值及运行效率。 这两个算法在程序结构上的区别是: test1_3_2.cpp:二层嵌套的for 循环;test1_3_3.cpp:单层的for 循环。 它们的时间复杂度分别是: test1_3_2.cpp为 O(n^2) , test1_3_3.cpp为 O(n) 。 你的判断是:算法____test1_3_3____优于算法____test1_3_2____。 步骤3:调试这两个测试程序,并写出运行结果 (其中用时与计算机的配置有关) 。 test1_3_2.cpp的运行结果为: 输入x, n: 2,10000 ; 输出为: sum=0.666667 用时544毫秒 。 test1_3_3.cpp的运行结果为: 输入x, n: 2,10000 ; 输出为: sum=0.666667 用时0毫秒 。 3、编写程序并分析时间复杂度 编写高效率的程序计算 1!/2 + 2!/3 +...+ i!/(i+1) +...+ n!/(n+1)的值,把该程序存放在文件test1_3_4.cpp中,并分析: 该算法的时间复杂度为 O(n) 该算法的时间效率是否已经最优 是 4、填写实验报告内容,实验报告文件取名为report3.doc。 5、上传实验报告文件report3.doc、源程序文件test1_3_1.cpp、test1_3_2.cpp、test1_3_3.cpp及test1_3_4.cpp到Ftp服务器上自己的文件夹下。 三. 实验结果与分析 四. 心得体会 【附录----源程序】 test1_3_1.cpp #include void main() { int ri,repeat; int i,x,y,z,temp; printf("Ener repeat: "); scanf("%d",&repeat); for(ri=1;ri<=repeat;ri++){ int change=0; printf("\nEnter x,y,z: "); scanf("%d %d %d",&x,&y,&z); if(x>y) { temp=x;x=y;y=temp;change++; } if(x>z) { temp=x;x=z;z=temp;change++; } if(y>z) { temp=y;y=z;z=temp;change++; } printf("After sort: x=%d,y=%d,z=%d\n",x,y,z); printf("Change: %d\n",change); } } test1_3_4.cpp #include #include void main() { timeb t1, t2; long t; int i, n; int ri,repeat; printf("Ener repeat: "); scanf("%d",&repeat); for(ri=1;ri<=repeat;ri++) { double fact=1, sum=0.5; printf("\nEnter n: "); scanf("%d",&n); ftime(&t1); for(i=2;i<=n;i++) { fact*=i; sum+=fact*1.0/(i+1); } ftime(&t2); t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm); printf("sum=%lf 用时%ld毫秒\n",sum,t); } }

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档