算法与设计实验报告

《算法与设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与分析实验报告软件工程专业安徽工业大学指导老师：许精明9实验内容1：杨辉三角2：背包问题3：汉诺塔问题一：实验目的1：掌握动态规划算法的基本思想，学会用其解决实际问题。2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。二：实验内容1：杨辉三角2：背包问题3：汉诺塔问题实验一：杨辉三角问题分析：①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。②第n行数之和为2^n。③下一行每个数字等于上一行的左右两个数字之和。9算法设计及相关源代码：publicvoidyanghui(intn){int[]a=newint

2、[n];if(n==1){System.out.println(1);}elseif(n==2){System.out.print(1+""+1);}else{a[1]=1;System.out.println(a[1]);a[2]=1;System.out.println(a[1]+""+a[2]);for(inti=3;i<=n;i++){a[1]=a[i]=1;for(intj=i-1;j>1;j--){a[j]=a[j]+a[j-1];}for(intj=1;j<=i;j++){System.out.print(a[j]+"");}System

3、.out.println();}9}}实验结果：n=10实验二：0-1背包问题问题分析：：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数:(1)  V(i,0)=V(0,j)=0 (2) V(i,j)=V(i-1,j) jwi(1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第

4、(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi; (b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。时间复杂度时间复杂度为o(V *T)，空间复杂度为o(V*T)。9算法设计及相关代码：publicclassbeibaoProblem{staticint[]a=newint[5]

5、;//背包重量staticint[]b=newint[5];//结果数组staticintflag=0;//下一个候选项staticintbound=20;//总重量staticinttotle=0;//每次选择后的总重量/***@parami元素坐标*@paramleftbound目标重量*@paramt*/publicstaticvoidinserttry(inti,intleftbound,intt){if(i<5&&leftbound<=totle){if(a[i]

6、果数组，从目标重量减掉当前所选数，递归，选择后的重量数减掉当前所选数b[t++]=a[i];totle=totle-a[i];leftbound=leftbound-a[i];i++;inserttry(i,leftbound,t);}elseif(a[i]>leftbound){//当前的所选的数大于已选数的总和，不符合条件，选择后的重量数减掉当前所选数，递归totle=totle-a[i];i++;inserttry(i,leftbound,t);}else{//当前所选的数等于已选数的总和b[t]=a[i];return;}}else{//数组中

7、没有符合当前条件的元素，将前一个数值移除，递归leftbound=leftbound+b[--t];for(intf=0;f<5;f++){if(a[f]==b[t]){flag=++f;break;9}}b[t]=0;totle=0;for(intm=flag;m<5;m++){totle+=a[m];}inserttry(flag,leftbound,t);}return;}publicstaticvoidmain(String[]args){a[0]=11;a[1]=8;a[2]=6;a[3]=7;a[4]=5;for(inti=0;i<5;i+

8、+){b[i]=0;}for(inti=0;i<5;i++){totle+=a[i];}ins