算法与设计实验报告.docx
《算法与设计实验报告.docx》由会员分享，可在线阅读，更多相关《算法与设计实验报告.docx（9页珍藏版）》请在冰点文库上搜索。
算法与设计实验报告
算法与分析实验报告
软件工程专业
安徽工业大学
指导老师：
许精明
实验内容
1：
杨辉三角
2：
背包问题
3：
汉诺塔问题
一：
实验目的
1：
掌握动态规划算法的基本思想，学会用其解决实际问题。
2：
通过几个基本的实验，提高算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。
二：
实验内容
1：
杨辉三角
2：
背包问题
3：
汉诺塔问题
实验一：
杨辉三角
问题分析：
①每行数字左右对称，由1开始逐渐变大，然后变小，回到1。
②第n行数之和为2^n。
③下一行每个数字等于上一行的左右两个数字之和。
算法设计及相关源代码：
publicvoidyanghui（intn）{
int[]a=newint[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.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 V（i,j）=max{V（i-1,j）,V（i-1,j-wi）+vi）}j>wi
（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）。
算法设计及相关代码：
publicclassbeibaoProblem{
staticint[]a=newint[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]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{//数组中没有符合当前条件的元素，将前一个数值移除，递归
leftbound=leftbound+b[--t];
for（intf=0;f<5;f++）{
if（a[f]==b[t]）{
flag=++f;
break;
}
}
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++）{
b[i]=0;
}
for（inti=0;i<5;i++）{
totle+=a[i];
}
inserttry（0,20,0）;
for（inti=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塔。
算法设计及相关代码：
publicclassHanoiTest{
staticintstep=0;
/**
*@paramargs
*/
publicstaticvoidmain（String[]args）{
hanioSort（3,"A","B","C"）;
}
/**
*递归函数，用来遍历hanoi步骤
*/
publicstaticvoidhanioSort（intnum,Stringa,Stringb,Stringc）{
if（num==1）{
move（num,a,c）;
}else{
hanioSort（num-1,a,c,b）;
move（num,a,c）;
hanioSort（num-1,b,a,c）;
}
}
publicstaticvoidmove（intnum,Stringa,Stringb）{
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
实验结果：
三：
实验总结
通过这次实验，掌握动态规划算法的基本思想，学会用其解决实际问题，并且提高我算法分析与设计能力，提高动手操作能力和培养良好的编程习惯。
细想，一个高效的程序不仅需要编程的技巧，更需要合理的数据组织和清晰的高效的算法，通过设计出高效的算法，提高程序的效率。
该课程的学习让我掌握了许多算法设计与分析的方法。
拥有了一套属于自己的算法分析思想。
升级会员 