算法与分析实验报告软件工程专业
安徽工业大学
指导老师：许精明
实验内容
1：杨辉三角
2：背包问题
3：汉诺塔问题
一：实验目的
1：掌握动态规划算法的基本思想，学会用其解决实际问题。
2：通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。
二：实验内容
1：杨辉三角
2：背包问题
3：汉诺塔问题
实验一：杨辉三角
问题分析：
①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。
②第n行数之和为2^n。
③下一行每个数字等于上一行的左右两个数字之和。
算法设计及相关源代码：
public void yanghui(int n) {
int[] a = new int[n];
if(n==1){
System.out.println(1);
}else if(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(int i=3;i<=n;i++){
a[1]=a[i]=1;
for(int j=i-1;j>1;j--){
a[j]=a[j]+a[j-1];
}
for(int j=1;j<=i;j++){
System.out.print(a[j]+" ");
}
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) j<w i
V(i,j)=max{V(i-1,j) ,V(i-1,j-w i)+v i) } j>w i
(1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的
最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；
第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-w i的背包中的价值加上第i个物品的价值v i;(b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。
显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。
时间复杂度
时间复杂度为o(V* T) ，空间复杂度为o(V * T) 。
算法设计及相关代码：
public class beibaoProblem {
static int[] a = new int[5]; // 背包重量
static int[] b = new int[5]; // 结果数组
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 (a[i] < leftbound) { // 当前的所选的数小于已选数的总和，将
当前所选的数放入结果数组，从目标重量减掉当前所选数，递归，选择后的重量数减掉当前所选数
b[t++] = a[i];
totle = totle - a[i];
leftbound = leftbound - a[i];
i++;
inserttry(i, leftbound, t);
} else if (a[i] > leftbound) { // 当前的所选的数大于已选数的总和，不符合条件，选择后的重量数减掉当前所选数，递归
totle = totle - a[i];
i++;
inserttry(i, leftbound, t);
} else { // 当前所选的数等于已选数的总和
b[t] = a[i];
return;
}
} else { // 数组中没有符合当前条件的元素，将前一个数值移除，递归
leftbound = leftbound + b[--t];
for (int f = 0; f < 5; f++) {
if (a[f] == b[t]) {
flag = ++f;
break;
}
}
b[t] = 0;
totle = 0;
for (int m = flag; m < 5; m++) {
totle += a[m];
}
inserttry(flag, leftbound, t);
}
return;
}
public static void main(String[] args) {
a[0] = 11;
a[1] = 8;
a[2] = 6;
a[3] = 7;
a[4] = 5;
for (int i = 0; i < 5; i++) {
b[i] = 0;
}
for (int i = 0; i < 5; i++) {
totle += a[i];
}
inserttry(0, 20, 0);
for (int i = 0; i < 5; i++) {
System.out.println(b[i]);
}
}
}
实验结果：
实验三：汉诺塔问题
玩法规制
1.有三根杆子A,B,C。
A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上
问题分析：
如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。
如果盘数超过2个，将最后一个盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->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)=2^n-1 所以O(n)=2^n
实验结果：
三：实验总结
通过这次实验，掌握动态规划算法的基本思想，学会用其解决实际问题，并且提高我算法分析与设计能力，提高动手操作能力和
培养良好的编程习惯。
细想，一个高效的程序不仅需要编程的技巧，更需要合理的数据组织和清晰的高效的算法，通过设计出高效的算法，提高程序的效率。
该课程的学习让我掌握了许多算法设计与分
析的方法。
拥有了一套属于自己的算法分析思想。