数学与计算机学院实验报告
一、实验项目信息
项目名称: 动态规划法实验实验时间: 2016/04/27 实验学时: 03 学时
实验地点: 工科楼二、实验目的及要求
理解动态规划法的设计思想、 掌握动态规划法的求解步骤、 掌握用动态规划法解题的算法框架。
三、实验环境
计算机Windows 7
MyEclipse Professional 2014 JAVA8
四、实验内容及实验步骤
动态规划法求解最大子段和问题:
划分:先对规模k的问题求解然后再求k+1问题(既k=1然后k=2......) 代码:
#Adder.java
package com.chanheng;
public class Adder {
int[] b= new int[100];//定义辅助数组 int max;//从辅助数组里面找出最大的值的变量
public int add(int[] a){ b[0]=a[0]; max=b[0]; for(int i=1;i
if(b[i-1]>0)
b[i]=b[i-1]+a[i]; else b[i]=a[i]; if(b[i]>max)max=b[i];
}
return max; } /**
* 找出组成最大字段和的段 * @param a */
public void getArray(int[] a){ int i,j,k,sum=0; int[] c= new int[100]; for(i=0;i
while(j>=0){ sum+=a[j];
if(sum==max)break; j--; }
k=i-j;
for(int x=0;x
}
for(int x=0;x
System.out.print(c[x]+" ");
} }
}
#Tester.java
package com.chanheng; import java.util.Scanner;
public class Tester { public static void main(String[] args) { // TODO Auto-generated method stub
new Scanner(System.in);
int[] a = new int[10];
System.out.println("please input 10 number:"); for(int i=0;i
}
Adder ad =new Adder();
System.out.println("最大字段和是:"+ad.add(a)); System.out.println("**最大字段和的组成数组*******"); ad.getArray(a); }
}
五、实验结果分析
结果正确并能找出最大字段和的部分。
六、实验总结
通过这次实验可以进一步了解动态规划法的原理和求解工作原理。深入理解如何对一个问
题进行划分成子问题。动态规划法一般是使用循环来求解,从规模小的问题求解然后再对规模次大的问题求解(利用已有的次小问题的答)。求解过程中可能使用到辅助空间或数组。
七、教师评价
数学与计算机学院实验报告
一、实验项目信息
项目名称: 动态规划法实验实验时间: 2016/04/27 实验学时: 03 学时
实验地点: 工科楼二、实验目的及要求
理解动态规划法的设计思想、 掌握动态规划法的求解步骤、 掌握用动态规划法解题的算法框架。
三、实验环境
计算机Windows 7
MyEclipse Professional 2014 JAVA8
四、实验内容及实验步骤
动态规划法求解最大子段和问题:
划分:先对规模k的问题求解然后再求k+1问题(既k=1然后k=2......) 代码:
#Adder.java
package com.chanheng;
public class Adder {
int[] b= new int[100];//定义辅助数组 int max;//从辅助数组里面找出最大的值的变量
public int add(int[] a){ b[0]=a[0]; max=b[0]; for(int i=1;i
if(b[i-1]>0)
b[i]=b[i-1]+a[i]; else b[i]=a[i]; if(b[i]>max)max=b[i];
}
return max; } /**
* 找出组成最大字段和的段 * @param a */
public void getArray(int[] a){ int i,j,k,sum=0; int[] c= new int[100]; for(i=0;i
while(j>=0){ sum+=a[j];
if(sum==max)break; j--; }
k=i-j;
for(int x=0;x
}
for(int x=0;x
System.out.print(c[x]+" ");
} }
}
#Tester.java
package com.chanheng; import java.util.Scanner;
public class Tester { public static void main(String[] args) { // TODO Auto-generated method stub
new Scanner(System.in);
int[] a = new int[10];
System.out.println("please input 10 number:"); for(int i=0;i
}
Adder ad =new Adder();
System.out.println("最大字段和是:"+ad.add(a)); System.out.println("**最大字段和的组成数组*******"); ad.getArray(a); }
}
五、实验结果分析
结果正确并能找出最大字段和的部分。
六、实验总结
通过这次实验可以进一步了解动态规划法的原理和求解工作原理。深入理解如何对一个问
题进行划分成子问题。动态规划法一般是使用循环来求解,从规模小的问题求解然后再对规模次大的问题求解(利用已有的次小问题的答)。求解过程中可能使用到辅助空间或数组。
七、教师评价