数据结构与算法设计课程设计

内江师范学院数据结构与算法设计课程设计实 验 报 告 册编制 算法设计课题组 审定 曾意专业： 信息与计算科学 班级： 2012 级 6 班学号： 姓名： 杨浩天 数学与信息科学学院2014年9月说 明1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本次实验，不得书写实验报告；2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师提问等；若学生无故旷课，则本次实验等级计为D；3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和目的，不得抄袭他人的实验报告；4. 实验成绩评定分为A+、A、A-、B+、B、C、D各等级。根据实验准备、实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符合。实验名称： 算法设计基础实验（实验一） 指导教师： 牟廉明，刘芳 实验时数： 4 实验设备：安装了VC+计算机实验日期： 年 月 日 实验地点： 第五教学楼北802实验目的：掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。实验准备：1. 在开始本实验之前，请复习相关实验内容；2. 需要一台准备安装Windows XP Professional操作系统和装有VC+6.0的计算机。实验内容：求n至少为多大时，n个1组成的整数能被2013整除。实验过程：1.1算法思想2013=61*33,6个1能够整除33，寻找满足n个1能够整除61的n即可。1.2 算法步骤1.定义变量y储存余数，i储存1的个数，m为被除数，初始化为；2.如果被除数能够除尽61，输出i; 如果被除数不能够除尽61，while继续循环,m=y*+,i+;3.重复2，直到找到满足条件的m为止，输出i;1.3算法实现（C+程序代码）#includeusing namespace std;int main() int y,m,i; i=6; m=; while(y!=0) m=y*+; y=m%61; i=i+6; coutiendl; return 0;1.4 算法分析时间复杂度为O(n);实验总结（由学生填写）：通过该实验发现，任何问题不要盲目的使用蛮力法，一定要化蛮力为巧力，这样既可以减少程序的时间复杂度，也能得到较精确的结果。并且在以后的解决问题的过程中，一定要多分析，多思考。 实验等级评定： 实验名称： 蛮力法实验分式化简（实验二） 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC+的计算机实验日期： 年 月 日 实验地点： 第五教学楼北802 实验目的：掌握蛮力法的基本思想和方法，熟悉搜索法的软件实现。实验准备：1在开始本实验之前，请回顾教材的相关内容；2需要一台准备安装Windows XP Professional操作系统和装有数学软件的计算机。实验内容：设计算法，将一个给定的真分数化简为最简分数形式，例如，将6/8化简为3/4。实验过程：1.1算法思想首先对于普通整数；可以先利用欧几里得算法求出最大公约数，然后再讲分子分母用最大公约数作除，即可求出最简真分数。1.2 算法步骤输入：约分前的两个整数分子和分母输出：约分后的分子分母1.r=m%n;2.循环直到r=0;3.m=n;n=r;r=m%n;4.a/n;b/n;5.输出b/a;1.3算法实现（C+程序代码）#includeusing namespace std;int main() long int a, b, r;coutab;long int m=a;long int n=b;r = a % b;while (r!=0) a = b;b= r;r = a%b;a=m/b;b=n/b;cout原分数的最简分数为:b/aendl;return 0;1.4 算法分析时间复杂度为o(n).实验总结（由学生填写）： 此次实验较为简单，也较为基础。但需注意的是，即使是很简单的问题，也需要注意细节，尤其是在定义长整型的时候，不要单独的只定义为整型。 实验等级评定： 实验名称： 分治法实验循环移位（实验三） 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC+的计算机 实验日期： 年 月 日 实验地点：第五教学楼北802 实验目的：通过本次实验，让学生掌握分治法的基本思想和技巧，并学会如何用C+软件来实现实验准备：1在开始本实验之前，请回顾教科书的相关内容；2需要一台准备安装Windows XP Professional操作系统和装有C+软件的计算机。实验内容：设计分治算法，实现将数组An中所有元素循环左移k个位置，要求时间复杂度为O（n），空间复杂度为O（1）。例如，对abcdefgh循环左移3位得到defghabc。实验过程：1.1算法思想对于第6题，用分治法进行求解的话，若是采用循环赋值的方式，如果字符的个数和左移的位数成倍数关系，那么算法就比较容易实现，但是如果不成比例关系，算法写起来就比较麻烦，所以，用了另一种方式，进行三次对称交换就可以完成算法。1.2 算法步骤1.输入：一个数组和左移位数2.编写两个函数，一个是对称交换函数1，另一个是调用函数2，用函数2三次调用函数1，完成整个对称交换过程。3.调用函数24.输出：左移后的数组1.3算法实现（C+程序代码）#includeusing namespace std;void fun(char *a,int m,int k) int temp;int i,j;for(i=m,j=k;i=k;i+,j-) if(i=(m+k)/2)temp=ai;ai=aj;aj=temp;void xun(char a,int k,int n)/（函数2）第二个调用函数，调用函数1fun(a,0,k-1);/第一次调用函数1，将(abc)对称交换得到(cba),最后a为(cbadefgh)fun(a,k,n-1);/第二次调用函数1，将(defgh)对称交换得到(hgfed),最后a为(cbahgfed)fun(a,0,n-1);/第三次调用函数1，将(cbadefgh)对称交换得到(defghabc),即最后a为(defghabc)int main()char a1000; cout请输入一个数组:a;也可以哟，不过配套的比较好看！int k;cout请输入左移位数:k; int n=strlen(a);xun(a,k,n);puts(a);/用coutaendl;也可以哟，不过配套的比较好看！return 0;1.4 算法分析存在如下递推式，T(n)=2T(n/2)+n, 时间复杂性为O(nlog2n) 实验总结（由学生填写）： 分治法的主要思想是分而治之，在遇到一个规模比较大问题时，我们不应该直接入手，通过简单的循环语句解决，而应该对其分段对局部进行考虑，通过对局部得到整体的结果。但在此次实验中，学会了对分治法的简单应该，但要对其加深巩固，还应该对此类问题的相关习题多多去练习，多多去领悟。 实验等级评定： 实验名称： 回溯法0/1背包问题（实验四） 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC+的计算机 实验日期： 年 月 日 实验地点：第五教学楼北802 实验目的：熟悉回溯法的基本思想和实现方法，掌握如何用C+实现相关算法。实验准备：1. 在开始本实验之前，请回顾教科书的相关内容；2. 需要一台准备安装Windows XP Professional操作系统和装有C+的计算机。实验内容：给定背包容量W=20，以及6个物品，重量分别为（5，3，2，10，4，2），价值分别为（11，8，15，18，12，6）。请用回溯法求解上述0/1背包问题。实验过程：1.1算法思想首先把物品单价价值排序，并确定上界函数，在搜索二叉树中利用上界函数对其进行剪枝，最终确定最优解。1.2 算法步骤1.定义变量2.编写函数 knapsack() ，用于将物品按单位价值排序编写函数 bound(int i)，用于计算上界函数编写函数 backtrack(int i) ，回溯函数，用于搜索二叉树。3.输出解决方案1.3算法实现（C+程序代码）#include/这个是只找到了一个可行解就返回了值(其实还可能有其他的解)using namespace std;#include/计算程序运行时间的头函数int n;/物品数量double c;/背包容量double v100;/各个物品的价值double w100;/各个物品的重量double cw = 0.0;/当前背包重量double cp = 0.0;/当前背包中物品价值double bestp = 0.0;/当前最优价值double perp100;/单位物品价值排序后int order100;/物品编号int put100;/设置是否装入/按单位价值排序void knapsack() int i,j; int temporder = 0; double temp = 0.0; for(i=1;i=n;i+) perpi=vi/wi; for(i=1;i=n-1;i+)/冒泡排序思想：比较n-1次，第一次从第一个数到最后一个数，第二次从第二个数到最后一个数. for(j=i+1;j=n;j+)/按照单位重量价值进行冒泡排序，同时要将重量，价值，序号进行相同排序 if(perpiperpj)/冒泡排序perp,order,sortv,sortw temp = perpi; perpi=perpi; perpj=temp; temporder=orderi; orderi=orderj; orderj=temporder; temp = vi; vi=vj; vj=temp; temp=wi; wi=wj; wj=temp; /计算上界函数double bound(int i) double leftw= c-cw;/leftw = 背包容量 - 当前背包容量 double b = cp; /b = 当前背包中物品价值 while(i=n&wi=leftw) leftw-=wi;/将第i件物品装入背包 b+=vi; i+; if(in) bestp = cp; return; if(cw+wibestp)/符合条件搜索右子数 backtrack(i+1);int main()clock_t nTimeStart;/开始时间clock_t nTimeStop;/结束时间nTimeStart=clock(); int i; /printf(请输入物品的数量和容量：); /scanf(%d %lf,&n,&c);coutnc; / printf(请输入物品的重量和价值：);cout请输入物品的重量和价值：endl; for(i=1;i=n;i+) /printf(第%d个物品的重量：,i); / scanf(%lf,&wi);cout第iwivi;/ printf(价值是：); /scanf(%lf,&vi); orderi=i; knapsack(); backtrack(1); printf(最大价值为：%lfn,bestp); printf(需要装入的物品编号是：); for(i=1;i=n;i+) if(puti=1)coutorderi ; /printf(%d ,orderi); coutendl;nTimeStop=clock();cout 程序耗时：(double)(nTimeStop - nTimeStart)/CLOCKS_PER_SEC秒 endl; return 0;1.4 算法分析回溯法实际上属于蛮力穷