算法实验报告.doc

中南大学
算法设计与分析实验报告
学生姓名: 胡家威
学号: 0909090807
专业班级: 计科0902班
指导老师: 沙莎
学院: 信息科学与工程学院
完成时间: 2012年1月7日
目录
实验一:分治法解MaxMin 3
实验二:动态规划解矩阵连乘 6
实验三:贪心法解背包问题和装载问题 9
实验四:回溯法解N皇后问题 15
实验一:分治法解MaxMin
分治法的思想:将输入规模为n的问题分成k(一般取k=2)个子问题,子问题相互独立,与原问题性质相同。先分别对k个子问题求解,再将子问题的解合并成原问题的解。由于子问题还很大,故采用递归技术对子问题不断分割,直至子问题可直接简单地解出。
分析:按照分治算法的思想,首先设想如果将这组数据分成两组,分别求出它们相应的最大值和最小值,然后比较,那么最大值更大的就是全部数据的最大值,最小值更小的就是全部数据的最小值,同理,继续往下拆分,直到只有一个元素的情况,那么最大值和最小值都是它了!这样,问题就这么自顶向下的解决了!
测试数据和结果
测试数据保存在文件中:
结果:
package ;
import ;
import ;
import ;
import ;
/**
* 最大最小问题:在n个元素中找出最大元素和最小元素
*/
public class MaxMin {
public static int n;// 数组的个数
public static int[] p;// 保存元素值
public static int max;// 最大值
public static int min;// 最小值
public static void main(String[] args) throws Exception {
// 从文件中读取数据
InputStream inputStream = ("");
BufferedReader reader = new BufferedReader(new InputStreamReader(inputStream));
String lineString = ();
Scanner scanner = new Scanner(lineString);
n = ();
p = new int[n];
lineString = ();
scanner = new Scanner(lineString);
for (int i = 0; i < n; i++) {
p[i] = ();
}
MaxMinData data = doMaxMin(0, n - 1);
("最大值是:" + );
("最小值是:" + );
}
源码
// i,j存放数据的范围,初值为0,n-1
public static MaxMinData doMaxMin(int i, int j) {
MaxMinData data = new MaxMinData();
if (i == j) {
= p[i];
= p[i];
return data;
}
if ((j - i) == 1) {
if (p[i] > p[j]) {
= p[i];
= p[j];
} else {
= p[j];
= p[i];
}
return data;
}
int mid = (i + j) / 2;
MaxMinData data1 = doMaxMin(i, mid);
MaxMinData data2 = doMaxMin(mid + 1, j);
if ( > ) {
= ;
} else {
= ;