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

1、内江师范学院数据结构与算法设计课程设计实验报告册班级：2012级6班学号：20120241242姓名：杨浩天_编制算法设计课题组审定曾意专业:信息与计算科学数学与信息科学学院2014年9月1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理 论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要 求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本 次实验，不得书写实验报告；2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过 程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师 提问等；若学生无故旷课，则本次实验等

2、级计为 D；3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和 目的，不得抄袭他人的实验报告；4. 实验成绩评定分为 A+、A、A 、B+、B、C、D 各等级。根据实验准备、实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如 下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符 合。实验名称：算法设计基础实验(实验一)指导教师：牟廉明，刘芳实验时数：4实验设备：安装了 VC 卄计算机实验日期：年月日实验地点：第五教学楼北 802实验目的：掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。实验准备：1.在开始本实验之前，请复习相关实验

3、内容；2.需要一台准备安装 Windows XP Piofessional 操作系统和装有 VC+6.0 的计算机。实验内容：求 n至少为多大时，n个 1组成的整数能被 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 继续循坏.m=y*100000gllllll,i 卄；3. 重复 2,直到找到满足条件的 m 为止，输出 1；1.3算法

4、实现( (C+程序代码)#iiicludeusing namespace std;int main()int yjn.i;1=6;m=llllll;while(y!=0)m=y*1000000+llllll;v=m%61;i=i+6;coutiendl;实验名称：算法设计基础实验(实验一)指导教师：牟廉明，刘芳实验时数：4实验设备：安装了 VC 卄计算机实验日期：年月日实验地点：第五教学楼北 802return 0;1.4算法分析时间复杂度为 O(n);实验总结(由学生填写)：通过该实验发现，任何问题不要盲目的使用蛮力法，一定要化蛮力 为巧力，这样既可以减少程序的时间复杂度，也能得到较精确的结

5、果。并且在以后的解决问 题的过程中，一定要多分析，多思考。实验等级评定：_实验名称：蛮力法实验一分式化简（实验二）指导教师:牟廉明，刘芳实验时数：4实验设备：安装了 VC 十十的计算机实验日期：_年月日实验地点：第五教学楼北 802实验目的：掌握蛮力法的基本思想和方法，熟悉搜索法的软件实现。实验准备：1.在开始本实验之前，请回顾教材的相关内容；2.需要一台准备安装 Windows XP Professional 操作系统和装有数学软件的计算机。实验内容：设计算法，将一个给定的真分数化简为最简分数形式，例如，将 6/8化简为3/4 o实验过程：1.1算法思想首先对于普通整数；可以先利用欧几里得算

6、法求出最人公约数，然后再讲分子分母用最人公约数作除，即可求出最简真分数。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+程序代码）#in cludeusing namespace std;int main（）long 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

7、/b;b=n/b;coutvc”原分数的最简分数为:llb7，laendl;return 0;1.4算法分析时间复杂度为 o(n).实验总结(由学生填写)：此次实验较为简单，也较为基础。但需注意的是，即使是很简单的问题，也需要注意细节，尤其是在定义长整型的时候，不要单独的只定义为整型。实验等级评定：_实验名称：分治法实验一循环移位(实验三)指导教师：牟廉明，刘芳实验时数：4实验设备：安装了 VC 十十的计算机实验日期：年月日实验地点：第五教学楼北 802实验目的：通过本次实验，让学生掌握分治法的基本思想和技巧，并学会如何用 C+软件来实现.实验准备：1.在开始本实验之前，请回顾教科书的相关内容

8、；2.需要一台准备安装 Windows XP Professional 操作系统和装有 C+软件的计算机。实验内容：设计分治算法，实现将数组 An中所有元素循环左移 k个位置，要求时间 复杂度为 o (n),空间复杂度为 0(1)。例如，对 abcdefgh 循环左移 3位得到 defghabco实验过程：1.1算法思想对于第 6题，用分治法进行求解的话，若是采用循环赋值的方式，如果字符的个数和左移的位数成倍 数关系，那么算法就比较容易实现，但是如果不成比例关系，算法写起来就比较麻烦，所以，用了另一种 方式，进行三次对称交换就可以完成算法。1.2算法步骤1输入：一个数组和左移位数2. 编写两个

9、函数，一个是对称交换函数 1,另一个是调用函数 2,用函数 2三次调用函数 1,完成整个 对称交换过程。3. 调用函数 24. 输出：左移后的数组1.3算法实现( (C+程序代码)#iiicludeusing namespace std;void fun(chai- m,mt k)int temp;mt ij；=k; i =k; i+J )if(i=(m+k)/2)temp=ai;void xun(char a,iiit k,mt n)/ (函数 2)第二个调用函数，调用函数 1fim(a,09k-l)y/第一次调用函数 b将(abc)对称交换得到(cba)撮后 a为(cbadefgli) f

10、iin(a,k,n-l);/第二次调用函数 1,alj=temp;将(defgh)对称交换得到(hgfbd),最后 a为(cbaligfbd) fiin(a,0,n-l);/第三次调用函数 1,将(cbadefgli)对称交换得到(defghabc),即最后 a为(defghabc) int niaiii()char a1000;coutH请输入一个数组:Hendl;gets(a);/用 cina;也可以哟，不过配套的比较好看!int k;coutH请输入左移位数:endl;ciiik;int n=strlen(a);xim(a,k、n);puts(a);/用 coutaendl迪可以哟，不过

11、配套的比较好看！retiiin 0;1.4算法分析存在如下递推式，T(n)=2T(n/2)+n,时间复杂性为 O(iilog2n)实验总结(由学生填写)：分治法的主要思想是分而治之，在遇到一个规模比较大问题时， 我们不应该直接入手，通过简单的循环语句解决，而应该对其分段对局部进行考虑，通过对 局部得到整体的结果。但在此次实验中，学会了对分治法的简单应该，但要对其加深巩固， 还应该对此类问题的相关习题多多去练习，多多去领悟。_实验等级评定：实验名称：回溯法一 0,1 背包问题(实验四)_指导教师：牟廉明，刘芳实验时数： 4实验设备：安装了 VC 十十的计算机实验日期：_年月日实验地点：第五教学楼

12、北 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. 编写函数

13、 kiiapsackQ ,用于将物品按单位价值排序编写函数 bound(mti),用于计算上界函数编写函数 backtrack(mt 1),回溯函数，用于搜索二叉树。3. 输出解决方案13算法实现( (C+程序代码)#mclude/这个是只找到了一个可行解就返回了值(其实还可能有其他的解)using namespace std;#iiiclude/计算程序运行时间的头函数mt 11；/物品数量double c;背包容量double v100;/各个物品的价值double w100;/各个物品的重量double cw =0.0;/当前背包重量double cp = 0.0;/当前背包中物品价值d

14、ouble bestp = 0.0;当前最优价值double peip100;/单位物品价值排序后int orderfl 00 物品编号int put100;/设置是否装入按单位价值排序 void knapsack()int ij;int temporder = 0; double temp = 0.0;fdr(i=l;i=n;i+)peipi=vi/wi;foi(i=l;i=n-l;i+)/冒泡排序思想：比较 n-1次，第一次从第一个数到最后一个数，第二次从第二个数 到最后一个数.foKi=i+lj=nj+)按照单位重量价值进行冒泡排序，同时要将重量，价值，序号进行相同排序if(perpip

15、eip|j)/冒泡排序 peip,order,soml,somvtemp = peipi;peipi=peipi;peipj=temp;temporder=orderi; oideri=orderj; ordeifj =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& & win)bestp = cp;re

16、tuin;if(cw+wibestp)/符合条件搜索右子数 backtrack(i+l);int niam()clocknTuneStait;/ 开始时间clocknTuneStop;/ 结束时间nTmie Start=c lockQ;int i;/pnntf(”请输入物品的数量和容量：”)； /scanf(”d&c);coutH请输入物品的数量和容屋：； ciiinc;/ prmtfC请输入物品的重量和价值：”)；coutHiW 输入物品的重量和价Hendl;fbr(i=l;i=n;i+)/prmtf(n第1个物品的重量：” j);/ scanfC%lf ；&wi);cout

17、H第个物品的重量和价值：”；cinwivi;/pnntf(价值是：”)；/scanfn%lf&vi);orderi=i;knapsackQ;backtrack(l);prmtf(最人价值为：%lfn,bestp);pnntf(需要装入的物品编号是：”)；fbi(i=l;i=n;i+)lf(putl=l) coutorderiH”；/prmtf(H%d .ordeifi);coutendl;nTmie Stop=clock();cout 程序耗时：H(double)(nTmieStop - nTimeStail)/CLOCKS_PER_SECM秒 endl; return 0;1-4算法分析回溯法