算法实验报告(第38组)

院 系： 计算机科学学院 专 业： 软件工程 年 级： 2009级 课程名称： 算法设计与分析基础 班 号： 5 组 号： 38 指导教师： 邢光林

2011年 11 月 4 日

学号 08065019 姓名 李霖 汪国志 王李健 组员 08065047 08065109 实验名称 算法实验整体框架的构建 1. 实验题目 算法实验主菜单的设计。 2．实验目的 ⑴ 熟悉实验环境VC＋＋6.0 ； 实验室 9#204 ⑵ 复习C、C++语言以及数据结构课程的相关知识，实现课程间的平滑过度； 3. 实验要求 实 验 目 的 或 要 求 1）设计的主菜单可以是图形模式的，也可以是控制台模式的。以控制台为例，主菜单大致如下： －－－－－－－－－－－－－－－－－－－－－－－－－ 《算法设计与分析》实验 －－－－－－－－－－－－－－－－－－－－－－－－－ 1. 算法分析基础——Fibonacci序列问题 2. 分治法在数值问题中的应用——最近点对问题 3. 减治法在组合问题中的应用——8枚硬币问题 4. 变治法在排序问题中的应用——堆排序问题 5. 动态规划法在图问题中的应用——全源最短路径问题 99. 退出本实验 －－－－－－－－－－－－－－－－－－－－－－－－－ 请输入您所要执行的操作（1，2，3，4，5，99）： 2）点击操作后进入相应的实验项目或是相应项目的下一级菜单； 3）可以反复执行，直到退出实验。

void Meun() { printf(\"\\n\\－－－－－－－－－－－－－－－－－－－－－－－－－\\n\"); printf(\"\\n\\ 《算法设计与分析》实验\\n\"); printf(\"\\n\\－－－－－－－－－－－－－－－－－－－－－－－－－\\n\"); printf(\"\\n\\1、算法分析基础——Fibonacci序列问题\\n\"); printf(\"\\n\\2、分治法在数值问题中的应用——矩阵相乘问题\\n\"); printf(\"\\n\\3、减治法在组合问题中的应用——枚硬币问题\\n\"); printf(\"\\n\\4、变治法在排序问题中的应用——堆排序问题\\n\"); printf(\"\\n\\99、退出本实验\\n\"); printf(\"\\n\\－－－－－－－－－－－－－－－－－－－－－－－－－\"); printf(\"\\n\\请输入您所要执行的操作（，，，，，）：\"); } void main() { int a; while(1) { Meun(); //调用菜单函数显示菜单 switch(a) { case 1: { } { } { } { printf(\"\\n\\变治法在排序问题中的应用——堆排序问题\\\\n\"); HEAP(); printf(\"\\n\\减治法在组合问题中的应用——8枚硬币问题\\\\n\"); COINFAKE(); break; printf(\"\\n\\分治法在数值问题中的应用——矩阵相乘问题\\\\n\"); matrix(); break; printf(\"\\n\\Fibonacci序列问题\\\\n\"); fibonacci(); break; 程 序 代 码 scanf(\"%d\case 2: case 3: case 4:

} } } } { } { } break; case 5: printf(\"\\n\\动态规划法在图问题中的应用——全源最短路径问题\\\\n\"); break; case 99: printf(\"你选择退出本实验‘\\n \" ); exit(0); 实 验 结 果 及 分 析

实验名称 算法分析基础——Fibonacci序列问题 实验题目 实验室 9#204 给定一个非负整数n，计算第n个Fibonacci数 实验目的 实 验 目 的 或 要 求 1）理解递归算法和迭代算法的设计思想以及递归程序的调式技术 2）掌握并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法； 3）理解这样一个观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同； 实验要求 1）使用教材2.5节中介绍的迭代算法Fib(n),找出最大的n,使得 第n个Fibonacci数不超过计算机所能表示的最大整数，并给出具体的执行时间； 2）对于要求1),使用教材2.5节中介绍的递归算法F(n)进行计算,同样给出具体的执行时间，并同1)的执行时间进行比较； 3）对于输入同样的非负整数n，比较上述两种算法基本操作的执行次数； 4）对1)中的迭代算法进行改进，使得改进后的迭代算法其空间复杂度为Θ(1)； 5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。

实 验 原 理 （算 法 基 本 思 想） 1、递归法基本思想 递归就是定义一个函数，让它自己调用自己。 Fib（int n） //输入整数n，输出第n个斐波那契数 {if(n=0)return 0; Else if(n=1)return 1; Else return Fib(n-1)+Fib(n-2) } 2、迭代法 这种方法相对于递归法来说在时间复杂度上减小了不少，但代码相对就要复杂些了。 Fib（int n） //输入整数n，输出第n个斐波那契数 {if(n=0)return 0; Else if(n=1)return 1; Else F0←0; F1←1; for(i=2;i//Fibonacci数列 int Fi(int i) { } void Fn() { } void Fib() { } void fibonacci() { double start; start=clock(); Fib(); printf(\"\迭代所用时间是%lf \\n\\n\",clock()-start); start=clock(); int i=1,f[3]={0,1}; printf(\"%d \",f[0]); do { printf(\"%d \",f[1]); f[2]=f[1]+f[0]; f[0]=f[1]; f[1]=f[2]; i++; int i=0,j=0; do { j=Fi(i); if(j>=0) printf(\"%d \",j); ++i; if(i<=1) return i; return Fi(i-1)+Fi(i-2); else 程 序 代 码 }while(j>=0); printf(\"\\n计算机所能计算的最大整数是第%d个fibonacci整数。\\n\",i-1); }while(f[1]>=f[0]); printf(\"\\n\计算机所能表示的最大fibonacci整数是第%d个fibonacci整数。\\n\",i);

} Fn(); printf(\"\递归所用时间是%lf \\n\\n\",clock()-start); 实 验 结 果 及 分 析 通过比较两种方法求Fibonacci数列所用的时间，可以发现迭代法的效率明显高于递归法。同时也明白了不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同。

实验名称 分治法在数值问题中的应用 ——矩阵相乘问题 实验题目 实验室 9#204 设M1和M2是两个n×n的矩阵，设计算法计算M1×M2 的乘积。 实验目的 实 验 目 的 或 要 求 1）提高应用蛮力法设计算法的技能； 2）深刻理解并掌握分治法的设计思想； 3）理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。 实验要求 1）设计并实现用BF方法求解矩阵相乘问题的算法； 2）设计并实现用DAC方法求解矩阵相乘问题的算法； 3）以上两种算法的输入既可以手动输入，也可以自动生成； 4）对上述两个算法进行时间复杂性分析，并设计实验程序验证 分析结果； 5）设计可供用户选择算法的交互式菜单(放在相应的主菜单下)。 实 验 原 理 （算 法 基 本 思 想） 1）蛮力法求解 蛮力法比较简单，直接使用矩阵相乘公式计算矩阵的每行每列的值，很容易就能得出答案 2）分治法求解 分治法思想 将问题实例划分为同一问题的几个较小的实例。对这些较小实例求解，通常使用递归方法，但在问题规模足够小时，也会使用另一种算法。如果有必要，合并这些问题的解，以得到原始问题的解。 求解矩阵相乘的DAC算法，使用了strassen算法。 DAC（A[]，B[]，n） { If n=2 使用7次乘法的方法求得解 Else Divide（A）//把A分成4块 Divide（B）//把B分成4块 调用7次strassen算法求得解的4块 合并这4块得到解并返回 }

//矩阵相乘问题 void PrintIn(Array A,Array B) { int n=A.n; int i,j; printf(\"请输入A数据：\\n\"); for(i=0;i>A.a[i*n+j]; for(j=0;j>B.a[i*n+j]; } void RandomIn(Array A,Array B) { } void PrintOut(Array A) { } void divide(Array d,Array d00,Array d01,Array d10,Array d11) /*分割矩阵*/ { int n=d00.n; int i,j; for(i=0;i} { d00.a[n*i+j]=d.a[2*n*i+j]; d01.a[n*i+j]=d.a[2*n*i+n+j]; d10.a[n*i+j]=d.a[2*n*n+2*n*i+j]; d11.a[n*i+j]=d.a[2*n*n+2*n*i+n+j]; } } Array merge(Array d00,Array d01,Array d10,Array d11) { int n=d00.n; int i,j; Array d; d.a=(int *)malloc(sizeof(int)*(4*n*n)); for(i=0;i} C.n=A.n; return C; Array strassen(Array A,Array B) { int n=A.n; Array C; C.a=(int *)malloc(sizeof(int)*(n*n)); C.n=n; if(n==2) { int m1,m2,m3,m4,m5,m6,m7; m1=(A.a[0]+A.a[3])*(B.a[0]+B.a[3]); m2=(A.a[2]+A.a[3])*B.a[0]; m3=A.a[0]*(B.a[1]-B.a[3]); m4=A.a[3]*(B.a[2]-B.a[0]); m5=(A.a[0]+A.a[1])*B.a[3]; m6=(A.a[2]-A.a[0])*(B.a[0]+B.a[1]); m7=(A.a[1]-A.a[3])*(B.a[2]+B.a[3]); C.a[0]=m1+m4-m5+m7; C.a[1]=m3+m5; C.a[2]=m2+m4; C.a[3]=m1+m3-m2+m6; return C; } else { n=n/2; Array a00,a01,a10,a11; Array c00,c01,c10,c11; Array b00,b01,b10,b11; Array s1,s2,s3,s4,s5,s6,s7; a00.a=(int *)malloc(sizeof(int)* (n*n)); a00.n=n; a01.n=n; a10.n=n; a11.n=n; b00.n=n; b01.n=n; a01.a=(int *)malloc(sizeof(int)* (n*n)); a10.a=(int *)malloc(sizeof(int)* (n*n)); a11.a=(int *)malloc(sizeof(int)* (n*n)); b00.a=(int *)malloc(sizeof(int)* (n*n)); b01.a=(int *)malloc(sizeof(int)* (n*n));

b10.a=(int *)malloc(sizeof(int)* (n*n)); b10.n=n; b11.n=n; b11.a=(int *)malloc(sizeof(int)* (n*n)); divide(A,a00,a01,a10,a11); divide(B,b00,b01,b10,b11); s1=strassen(a00+a11,b00+b11); s2=strassen(a10+a11,b00); s3=strassen(a00,b01-b11); s5=strassen(a00+a01,b11); s4=strassen(a11,b10-b00); s6=strassen(a10-a00,b00+b01); s7=strassen(a01-a11,b10+b11); c00=s1+s4-s5+s7; c01=s3+s5; c10=s2+s4; c11=s1+s3-s2+s6; C=merge(c00,c01,c10,c11); return C; } } Array mul(Array A,Array B) //普通的矩阵乘法计算 { int n=A.n; Array C; C.a=(int *)malloc(sizeof(int)*(n*n)); C.n=n; int i,j,k; for(i=0;icin>>n; A.n=n; B.n=n; A.a=(int *)malloc(sizeof(int)* (n*n)); B.a=(int *)malloc(sizeof(int)* (n*n)); C.a=(int *)malloc(sizeof(int)* (n*n)); C.n=n; printf(\"\\---1 手动输入---\\n\"); printf(\"\\---2 随机生成---\\n\"); printf(\"\\请选择\\n\\n\"); ch=getch(); switch(ch) { case '1': printf(\"手动输入\\n\"); PrintIn(A,B); printf(\"\\n\"); break; case '2': printf(\"自动生成\\n\"); RandomIn(A,B); break; printf(\"按键错误\\n\");break; default: } printf(\"结果数组A中数据为：\\n\"); PrintOut(A); printf(\"结果数组B中数据为：\\n\"); PrintOut(B); cout< } C=mul(A,B); finish = clock(); duration = (double)(finish - start); printf(\"\\n用BF方法得出的结果\\n\"); PrintOut(C); printf( \"用BF方法计算矩阵所花费的时间是：%f ms\\n\", duration ); printf(\"\\n\");break; start = clock(); case '2': C=strassen(A,B); finish = clock(); duration = (double)(finish - start); printf(\"用DAC方法得出的结果\\n\"); PrintOut(C); printf( \"DAC方法计算矩阵所花费的时间是：%f ms\\n\", duration ); printf(\"\\n\");break; exit(0); default: printf(\"按键错误\\n\"); case '3': } printf(\"\\n 你想用另外一种方法吗？请输入(Y/N)?：\"); do { ch=getch(); }while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n'); }while(ch=='Y'||ch=='y');

实 验 结 果 及 分 析 经过这个实验，我明白了蛮力法几乎可以解决所有的问题，但是算法的效率不高。对蛮力法进行改进，经过适当的努力后，算法的效率可以得到提高。

实验名称 减治法在组合问题中的应用——8枚硬币问题 实验题目 实验室 9#204 在8枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不实 验 目 的 或 要 求 知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币。 实验目的 1）深刻理解并掌握减治法的设计思想并理解它与分治法的区别； 2）提高应用减治法设计算法的技能。 3）理解这样一个观点：建立正角的模型对于问题的求解是非常重要的。 实验要求 1）设计减治算法实现8枚硬币问题； 2）设计实验程序，考察用减治技术设计的算法是否高效； 3）扩展算法，使之能处理n枚硬币中有一枚假币的问题。 实 验 原 理 （算 法 基 本 思 想） 减治法主要有三种变种 减去一个常量 减去一个常量因子 减可变规模 与分治法的区别：分治法把实例分为几部分分别求解 减治法把实例的规模减为一个更小的实例求解 A（n）//输入硬币个数n，要求必须有假币且已知假币只有1个（假设更重） {if n=1,这枚就是假币 Else if n=2，较重的那枚是假币 Else 把n个硬币分为3份，2份相等，另一份与这2份的相差个数尽可能小 称2份个数相等的 If这2份重量相等，假币在第3堆中，对第3堆使用该算法 Else 在较重的那堆中，对该堆硬币使用该算法 }

//假币问题 void FakeCoin(int B[N],int n,int l,int h) { int sum1,sum2,ps; if(n==2) } else FakeCoin(B,n,l,l+ps-1); printf(\"硬币数目过少，无法判定假币!\\n\"); if(h==l) printf(\"硬币%d 是假币\\n\",l); if(h-l==1) { } else if(l1) if(B[l]==B[1]) printf(\"硬币%d 是假币\\n\",h); printf(\"硬币%d 是假币\\n\",l); else else else else if(h} void COINFAKE() { } int B[N],n; printf(\"\\n请输入硬币总数n:\"); scanf(\"%d\",&n); printf(\"\\n请输入n个数字：\"); for(int i=1;i<=n;i++) scanf(\"%d\",&B[i]); printf(\"%d \",B[i]); for(i=1;i<=n;i++) printf(\"\\n\"); FakeCoin(B,n,1,n); 实 验 结 果 及 分 析 通过这个实验，理解并掌握了减治法的设计思想并理解了它与分治法的区别。在写这个算法前，一定要建立正确的求解模型。

实验名称 变治法在排序问题中的应用——堆排序问题 实验题目 实验室 9#204 实 验 目 的 或 要 求 用基于变治法的堆排序算法对任意一组给定的数据进行排序 实验目的 1）深刻理解并掌握变治法的设计思想； 2）掌握堆的概念以及如何用变治法把任意给定的一组数据改变成堆； 3）提高应用变治法设计算法的技能。 实验要求 1）设计与实现堆排序算法； 2）待排序的数据可以手工输入(通常规模比较小，10个数据左右），用以检测程序的正确性；也可以计算机随机生成（通常规模比较大，1500－3000个数据左右），用以检验(用计数法)堆排序算法的时间效率。 实 验 原 理 （算 法 基 本 思 想） 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 (1)用大根堆排序的基本思想 （2）大根堆排序算法的基本操作 特点: 堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录 堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。 它是不稳定的排序方法。

//堆排序 void in(int h[N],int n) { } void random(int h[N],int n) { int i; h[i]=rand(); for(i=1;i<=n;i++) printf(\"随机产生要排序的数如下所示:\\n\"); for(i=1;i<=n;i++) printf(\"%d\\",h[i]); } printf(\"\\n\\n\"); int i; printf(\"手动输入要排序的数：\"); for(i=1;i<=n;i++) scanf(\"%d\",&h[i]); 程 序 代 码 //自底向上构造一个堆 void HeapBottomUp(int h[],int n) { int heap,i,k,v,j; for(i=(n/2);i>0;i--) { k=i; v=h[k]; while((heap==0)&&(2*k<=n)) { } j=2*k; if(jh[j]) { } h[k]=h[j]; k=j; h[k]=v; heap=1; else if(h[j]} } void HEAP() { int h[N]={0},i,n,elem,m; double start, finish; char ch=' '; printf(\"\\n\\输入要排序的数的规模：\"); scanf(\"%d\",&n); printf(\"\\n---1 手动输入---\\n\"); printf(\"---2 自动生成---\\n\"); printf(\"请选择:\"); do{ ch=getch(); if(ch=='1') in(h,n); random(h,n); printf(\"\\n输入出错，请重输：\"); if(ch=='2') else }while(ch!='1'&&ch!='2'); start=clock(); m=n; while(m>1) { HeapBottomUp(h,m); //for(i=1;i<=n;i++) //printf(\"%d\\\ //printf(\"\\n\"); //根键（最大）与堆中最后一个键交换 elem=h[1]; h[1]=h[m]; h[m]=elem; m=m-1;//堆的规模减一 //for(i=1;i<=n;i++) } } finish=clock(); printf(\"\\n输出排好的数组元素:\\n\"); printf(\"%d\\",h[i]); printf(\"\\n输出算法执行的时间%f \",finish-start); //printf(\"%d \ //printf(\"\\n\"); for(i=1;i<=n;i++)

实 验 结 果 及 分 析 经过这次实验，理解了变治法的设计思想，同时还掌握了堆的概念以及如何用变治法把任意给定的一组数据改变成堆。

经过这几次的实验，对算法的分析能力有了较大的提高。算法分析对于设计出的每一个具体的算法，利用数字作为工具讨论它的各种复杂度，就是算法分析的主要任务。复杂度分析的结果可以作为评价算法质量的标准之一，有时也可以为改进算法的方向提供参考。分析算法的复杂度需要较强的数学技巧,针对不同的算法,采用不同的分析方法。说说Fibonacci序心 得 体 会 列问题，这个实验让我们更好的理解递归算法和迭代算法的设计思想以及递归程序的调式技术，并应用递归算法和迭代算法效率的理论分析(前验分析)和实际分析(后验分析)方法。这次实验也让我们理解了蛮力法、分治法、减治法、变治法的设计思想，提高应用蛮力法、分治法、减治法、变治法设计算法的技能。并且理解了几个重要观点：不同的算法可以解决相同的问题，这些算法的解题思路不同，复杂程度不同，效率也不同；用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对其进行改进，以提高算法的效率。建立正角的模型对于问题的求解是非常重要的。学习了这门课，我们在以后的编程中，将会关注于程序执行的效率，进而决定我们的算法，而不再是盲目的去编程。这门课也为我们设计算法打下了基础。同时，我们明白了良好的编程习惯有助于我们更快更高效的编写出可运行的程序。 成 绩 评 定 教师签名： 年 月 日