算法上机报告李彤辉

《算法上机报告李彤辉》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、西安邮电大学（计算机学院）课内实验报告实验名称：算法实验专业名称：计算机科学与技术班级：计科1102学生姓名：李彤辉学号（8位）：04111038指导教师：陈琳实验日期：2014年05月15日实验一：查找主元素算法思路：一个数组中，如果同时去掉两个不相同的元素，则主元素不变。13323531，需要变量count记录主元素次数，变量send记录主元素值for(inti=1;i0)count--;elseseed=a[i

2、];}for(inti=0;in/2){System.out.println("主元素为："+seed+"总共为："+count);}else{System.out.println("notfind!");}3，主元素个数必须大于数组个数的一半4，运行结果截图实验二：01背包物品valueweight12345678a230356891112b320356891112c5300

3、56691111d430046661010e6400066666如上图所示，背包数量m=5，背包容量w=8，m[num][j]背包容量为j,可选的物品num，num+1。。。intm[][]=newint[6][9];物品重量weight[]={0,3,2,3,3,4};物品价值value[]={0,2,3,5,4,6}算法思路，在m[num][j],背包容量为j，选择物品为i，i+1….n时0-1背包问题最优值max(m(i+1,j),m(i+1,j-w)+vi)j>wim(i,j)=m(i+1,j

4、)0<=j1;i--){jMax=min(weight[i]-1,w);for(intj=0;j<=jMax;j+

5、+)m[i][j]=m[i+1][j];for(intj=weight[i];j<=w;j++)m[i][j]=max(m[i+1][j],m[i+1][j-weight[i]]+value[i]);}m[1][w]=m[2][w];if(w>=weight[1])m[1][w]=max(m[1][w],m[2][w-weight[1]]+value[1]);System.out.println("thebiggestis"+m[1][w]+"w="+w);System.out.println("选择

6、背包是");TraceBack(weight,w,num,value);}publicstaticvoidTraceBack(intweight[],intw,intnum,intx[]){for(inti=1;i

7、结果：实验三：最长单调递增子序列算法思想：数组inta[]={0,1,2,7,4,5};将数组a，排序后intb[]={0,1,2,4,5,7}；数组a，b求最大公共子序列c[]={1，2，4，5}排序算法采用快速排序publicstaticvoidQuicksort(inta[],intp,intr){if(p

8、,intp,intr){intleft=p,right=r;intx=a[p];while(leftx)right--;if(left