《数据结构与算法设计课程设计》由会员分享，可在线阅读，更多相关《数据结构与算法设计课程设计（13页珍藏版）》请在金锄头文库上搜索。
1、内江师范学院数据结构与算法设计课程设计实验报告册编制算法设计课题组审定曾意专业:信息与计算科学班级：2012级 6 班学号：20120241242姓名：杨浩天数学与信息科学学院2014年9月1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理 论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要 求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本 次实验，不得书写实验报告；2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过 程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师 提问等；若学生无故旷课，则本次实验
2、等级计为D；3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和 目的，不得抄袭他人的实验报告；4. 实验成绩评定分为A+、A、A、B+、B、C、D各等级。根据实验准备、 实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如 下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符 合。实验目的：掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。实验准备：1. 在开始本实验之前，请复习相关实验内容；2. 需要一台准备安装Windows XP Professional操作系统和装有VC+6.0的计算机。实验内容：求n至少为多大时，n个1组成的
3、整数能被2013整除。实验过程：1.1算法思想2013=61*33.6个1能够整除33,寻找满足n个1能够整除61的n即可。1.2算法步骤1定义变量y储存余数，1储存1的个数，m为被除数，初始化为111111：2. 如果被除数能够除尽61,输出1；如果被除数不能够除尽61, while继续循f.m=y* 1000000+111111 ,i+;3. 重复2,直到找到满足条件的m为止，输出i;1.3算法实现（C+程序代码）#mcludeusing namespace std;int mainOint vjnj;1=6;111=111111;while（y!=0）m=y*1000000+llllll
4、;v=m%61;i=i+6;coutiendl;return 0;1.4算法分析时间复杂度为O(n);实验总结(由学生填写)：通过该实验发现，任何问题不要盲目的使用蛮力法，一定要化蛮力 为巧力，这样既可以减少程序的时间复杂度，也能得到较精确的结果。并且在以后的解决问 题的过程中，一定要多分析，多思考。实验等级评定：实验名称：蛮力法实验一分式化简（实验二）指导教师:牟廉明，刘芳实验时数：4实验设备：安装了 VC十十的计算机实验日期：年月日实验地点：第五教学楼北802实验目的：掌握蛮力法的基本思想和方法，熟悉搜索法的软件实现。实验准备：1. 在开始本实验之前，请回顾教材的相关内容；2. 需要一台准
5、备安装Windows XP Professional操作系统和装有数学软件的计算机。实验内容：设计算法，将一个给定的真分数化简为最简分数形式，例如，将6/8化简为3/4 o实验过程：1.1算法思想首先对于普通整数；可以先利用欧几里得算法求出最人公约数，然后再讲分子分母用最人公约数作除，即可求出最简真分数。1.2算法步骤输入：约分前的两个整数分子和分母输出：约分后的分子分母1. r=m%n;2. 循环直到r=0;3. m=n; n二r;n=m%n;4. a/n;b/n;5. 输出b/a;1.3算法实现（C+程序代码）#in cludeusing namespace std;int main（）l
6、ong int a, b, r;cout请输入真分数的分母和分子：”；cinab;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;coutlM 分数的最简分数为:,b7，aendl;return 0;1.4算法分析时间复杂度为o(n).实验总结(由学生填写)：此次实验较为简单，也较为基础。但需注意的是，即使是很简单的问题，也需要注意细节，尤其是在定义长整型的时候，不要单独的只定义为整型。实验等级评定：实验目的：通过本次实验，让学生掌握分治法的基本思想和技巧，并学会如何用C+软件来实现
7、.实验准备：1. 在开始本实验之前，请回顾教科书的相关内容；2. 需要一台准备安装Windows XP Professional操作系统和装有C+软件的计算机。实验内容：设计分治算法，实现将数组An中所有元素循环左移k个位置，要求时间 复杂度为o (n),空间复杂度为0(1)。例如，对abcdefgh循环左移3位得到 defghabco实验过程：1.1算法思想对于第6题，用分治法进行求解的话，若是采用循环赋值的方式，如果字符的个数和左移的位数成倍 数关系，那么算法就比较容易实现，但是如果不成比例关系，算法写起来就比较麻烦，所以，用了另一种 方式，进行三次对称交换就可以完成算法。1.2算法步骤1
8、. 输入：一个数组和左移位数2. 编写两个函数，一个是对称交换函数1,另一个是调用函数2,用函数2三次调用函数1,完成整个 对称交换过程。3. 调用函数24. 输出：左移后的数组1.3算法实现(C+程序代码)#iiicludeusing namespace std;void fun(chai- nhiiit k)int temp;mt ij；fbT(i=mj =k; i =k; i+J )if(i=(m-rk)/2)temp=ai; a】=aj；void xun(char a,iiit k,int n)/ (函数2)第二个调用函数，调用函数1fun(a,0,k-l)y/第一次调用函数b将(ab
9、c)对称交换得到(cba),最后a为(cbadefgli) fiin(a,k,n-l);/第二次调用函数 1,将(defgh)Xj称交换得到(hgfbd),最后 a为(cbaligfbd) fiin(a,0,n-l);/第三次调用函数1,将(cbadefgli)对称交换得到(defgliabc),即最后a为(defghabc)int main()char a1000;coutH请输入一个数组:Hendl;gets(a);/用cina;也可以哟，不过配套的比较好看!int k;coutH请输入左移位数:endl;ciiik;int n=strlen(a);xim(akn)；puts(a);/用c
10、outaendl迪可以哟，不过配套的比较好看！return 0;1.4算法分析存在如下递推式，T(ii尸2T(n/2)+a时间复杂性为O(nlog2ii)实验总结(由学生填写)：分治法的主要思想是分而治之，在遇到一个规模比较大问题时， 我们不应该直接入手，通过简单的循环语句解决，而应该对其分段对局部进行考虑，通过对 局部得到整体的结果。但在此次实验中，学会了对分治法的简单应该，但要对其加深巩固， 还应该对此类问题的相关习题多多去练习，多多去领悟。实验等级评定：实验名称：回溯法一0/1背包问题(实验四)指导教师：牟廉明，刘芳实验时数： 4实验设备：安装了 VCH的计算机实验日期：年月日实验地点：
11、第五教学楼北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. 编写函数ki
12、iapsackQ ,用于将物品按单位价值排序编写函数bound(mti),用于计算上界函数编写函数backtrack(int 1),回溯函数，用于搜索二叉树。3. 输出解决方案13算法实现(C+程序代码)#mclude/这个是只找到了一个可行解就返回了值(其实还可能有其他的解)using namespace std;#include/计算程序运行时间的头函数mt 11；/物品数量double c;/背包容量double v100;/各个物品的价值double w100;/各个物品的重量double cw= 0.0;/当前背包重量double cp = 0.0;/当前背包中物品价值double
13、bestp = 0.0;当前最优价值double perp100;/单位物品价值排序后int oideil 00;/物品编号 mtput100;/设置是否装入按单位价值排序void knapsack()int ij;int temporder = 0; double temp = 0.0;for(i=l;i=n;i-H-)perpi=vi/wi;foi(i=l;i=n-l;i+)/冒泡排序思想：比较n-1次，第一次从第一个数到最后一个数，第二次从第二个数 到最后一个数.ford=i+lj=nj+)/S照单位重量价值进行冒泡排序，同时要将重量，价值，序号进行相同排序 if(perpipeip|j
14、)/冒泡排序 perp,order,sortv,sortwtemp = peipi;perpi=perpi;peipj=temp;temporder=ordeii; oideii=orderj; oideifj =temporder; temp = vi; vi=vj; vj=temp;temp=wi; wi=wj; wj=temp;/计算上界函数double bound(mt i)double lefh- c-cw/leftw =背包容量-当前背包容量 double b = cp; /b =当前背包中物品价值 while(i=n& & wi =lefhv) lefhv-=wi;将第1件物品装入背包 g=vi;i+;b=vi/wi *leftw/$U果要切分的情况卞 return b;回溯函数void backtiack(iiit i)double bound(mt i
