算法上机报告李彤辉.docx

西 安 邮 电 大 学 （计算机学院）课内实验报告实验名称： 算法实验 专业名称： 计算机科学与技术班 级： 计科1102 学生姓名： 李彤辉学号（8位）： 04111038指导教师： 陈琳实验日期： 2014年05月15日实验一：查找主元素算法思路：一个数组中，如果同时去掉两个不相同的元素，则主元素不变。13323531，需要变量count记录主元素次数，变量send记录主元素值for(int i=1;i0) count-; else seed=ai; for(int i=0;in/2) System.out.println(主元素为： +seed+ 总共为： +count); else System.out.println(not find!); 3，主元素个数必须大于数组个数的一半4，运行结果截图实验二：01背包物品valueweight12345678a230356891112b320356891112c530056691111d430046661010e6400066666如上图所示，背包数量m=5，背包容量w=8，mnumj 背包容量为j,可选的物品num，num+1。int m = new int69;物品重量weight = 0, 3, 2, 3, 3, 4 ; 物品价值value = 0, 2, 3, 5, 4, 6 算法思路，在mnumj,背包容量为j，选择物品为i，i+1.n时0-1背包问题最优值 max(m(i+1,j),m(i+1,j-w)+vi) jwi m(i,j)= m(i+1,j) 0=jwi public static void Knapsack(int value, int weight, int w, int num) int jMax = min(weightnum - 1, w);for (int j = 0; j = jMax; j+)mnumj = 0;for (int j = weightnum; j 1; i-) jMax = min(weighti - 1, w);for (int j = 0; j = jMax; j+)mij = mi + 1j;for (int j = weighti; j = weight1)m1w = max(m1w, m2w - weight1 + value1);System.out.println(the biggest is + m1w+w=+w);System.out.println(选择背包是);TraceBack(weight, w, num, value);public static void TraceBack(int weight, int w, int num, int x) for (int i = 1; i num; i+) if (miw = mi + 1w)xi = 0;else xi = 1;w = w - weighti;xnum = (mnumw) = 1 ? 1 : 0;for (int j = 1; j = num; j+) System.out.print(xj+ );运行结果：实验三：最长单调递增子序列算法思想：数组int a = 0, 1, 2, 7, 4, 5 ;将数组a，排序后int b= 0,1,2,4,5,7 ；数组a，b求最大公共子序列 c=1，2，4，5排序算法采用快速排序public static void Quicksort(int a, int p, int r) if (p r) int q = Position(a, p, r);Quicksort(a, p, q - 1);Quicksort(a, q + 1, r);private static int Position(int a, int p, int r) int left = p, right = r;int x = ap;while (left right) while (left x)right-;if (left right) aleft = aright;left+;while (left right & aleft x)left+;if (left right) aright = aleft;right-;aleft = x;return left;最长公共子序列a=x1,x2,x3.xm,b=y1,y2,y3yn,最长公告子序列z=z1,z2,z3zk(1),若xm=yn,则zk=xm=ym,则z(k-1)是x(m-1)和y(n-1)最长公共子序列(2),xm!=yn,且zk!=xm，则 z是 x(m-1)和 y最长公共子序列(3) xm!=yn,且zk!=yn，则 z 是,x,和y(m-1)最长公共子序列递推关系 0Cij = ci-1j-1+1 Max(cij-1,ci-1j)static void LCSLength(int m, int x, int y, int c, int b) int i, j;for (i = 1; i = m; i+) cii = 0;for (i = 1; i = m; i+)for (j = 1; j = cij - 1) cij = ci - 1j;bij = 2; else cij = cij - 1;bij = 3;实验四：归并排序非递归算法思路：首先将数组a中相邻元素两量配对，用合并算法将它们排序，构成n/2组长度为2的排好序的子数序列，然后再将它们排序长度为4的排序好子树组段，继续下去，直至整个数组排好序a=4,8,3,7,1,5,6,2;4,8,3,7,1,5,6,23,4,7,8,1,2,5,61,2,3,4,5,6,7,8void MergePass(int x, int y, int s, int n) int i = 0;while (i = n - 2 * s) Merge(x, y, i, i + s - 1, i + 2 * s - 1);i = i + 2 * s;/*剩下的元素个数少于2s*/if (i + s n)Merge(x, y, i, i + s - 1, n - 1);elsefor (int j = i; j = n - 1; j+)yj = xj;void Merge(int c, int d, int l, int m, int r) /* 合并cl:m和cm+1：r到d