算法与设计实验报告.docx

算法与分析实验报告软件工程专业安徽工业大学指导老师：许精明实验内容1：杨辉三角2：背包问题3：汉诺塔问题一：实验目的1：掌握动态规划算法的基本思想，学会用其解决实际问题。2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。二：实验内容1：杨辉三角2：背包问题3：汉诺塔问题实验一：杨辉三角问题分析：每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 第n行数之和为2n。下一行每个数字等于上一行的左右两个数字之和。 算法设计及相关源代码：public void yanghui(int n) int a = new intn;if(n=1)System.out.println(1);else if(n=2) System.out.print(1 + +1);elsea1=1;System.out.println(a1);a2=1;System.out.println(a1+ +a2);for(int i=3;i1;j-)aj=aj+aj-1;for(int j=1;j=i;j+)System.out.print(aj+ );System.out.println();实验结果：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不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi的背包中的价值加上第i个物品的价值vi;(b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。时间复杂度时间复杂度为o(V* T) ，空间复杂度为o(V * T) 。算法设计及相关代码：public class beibaoProblem static int a = new int5; / 背包重量static int b = new int5; / 结果数组static int flag = 0; / 下一个候选项static int bound = 20; / 总重量static int totle = 0; / 每次选择后的总重量/* * param i 元素坐标 * param leftbound 目标重量 * param t */public static void inserttry(int i, int leftbound, int t) if (i 5 & leftbound = totle) if (ai leftbound) / 当前的所选的数大于已选数的总和，不符合条件，选择后的重量数减掉当前所选数，递归totle = totle - ai;i+;inserttry(i, leftbound, t); else / 当前所选的数等于已选数的总和bt = ai;return; else / 数组中没有符合当前条件的元素，将前一个数值移除，递归leftbound = leftbound + b-t;for (int f = 0; f 5; f+) if (af = bt) flag = +f;break;bt = 0;totle = 0;for (int m = flag; m 5; m+) totle += am;inserttry(flag, leftbound, t);return;public static void main(String args) a0 = 11;a1 = 8;a2 = 6;a3 = 7;a4 = 5;for (int i = 0; i 5; i+) bi = 0;for (int i = 0; i 5; i+) totle += ai;inserttry(0, 20, 0);for (int i = 0; i B、A-C、B-C这三个步骤，而被遮住的部份，其实就是进入程序的递回处理递推方法：将n-1个圆盘按要求放在C塔，第n个圆盘放在B塔，现在A塔空。n号圆盘是最大的圆盘，按问题要求我们终于把n号最大的圆盘放在了B塔，这下借助已空的A塔联合BC塔推回来，就可以把n个圆盘按要求放在B塔。算法设计及相关代码：public class HanoiTest static int step = 0; /* * param args */ public static void main(String args) hanioSort(3, A, B, C); /* * 递归函数，用来遍历hanoi步骤 */ public static void hanioSort(int num ,String a ,String b ,String c) if(num = 1) move(num,a,c); else hanioSort(num-1, a, c, b); move(num,a,c); hanioSort(num-1, b, a, c); public static void move(int num ,String a,String b) step + ; System.out.println(第+step+步，盘子+num+从+a+塔移到+b+塔/n); 时间复杂度假设移动n个圆盘需要f(n)次移动首先考虑一个圆盘，只需一步就可以了 f(1)=1现在考虑n个圆盘，假设开始圆盘在A柱，可以先把A柱的上面n-1个圆盘移到B，再将A剩下的一个移到C，最后将B的n-1个移到C。总共需要f(n)=2f(n-1)+1根据两式，可求出f(n)=2n-1 所以O(n)=2n实验结果：三：实验总结通过这次实验，掌握动态规划算法的基本思想，学会用其解决实际问题，