算法与设计实验报告.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
实验结果:
三:
实验总结
通过这次实验,掌握动态规划算法的基本思想,学会用其解决实际问题,并且提高我算法分析与设计能力,提高动手操作能力和培养良好的编程习惯。
细想,一个高效的程序不仅需要编程的技巧,更需要合理的数据组织和清晰的高效的算法,通过设计出高效的算法,提高程序的效率。
该课程的学习让我掌握了许多算法设计与分析的方法。
拥有了一套属于自己的算法分析思想。