AlgorithmExperiment
算法分析课实验 分治法的核心思想是将问题分为若干子问题去，使规模一步步缩小，最终分到一步就能得出结果。要注意每个子问题需要性质相同而且相互不重复。 采用分治法完成如下任务：
i. 中位数问题
问题描述
设X[ 0 : n - 1]和Y[ 0 : n – 1 ]为两个数组，每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。
编程任务
利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。
数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示每个数组有n个数。接下来的两行分别是X，Y数组的元素。
结果输出
程序运行结束时，将计算出的中位数输出到文件output.txt中。
输入文件示例1
input.txt
3
5 15 18
3 14 21输出文件示例1
output.txt
14.5输入文件示例2
input.txt
4
5 15 18 24
3 10 21 30输出文件示例2
output.txt
16.5实现提示
比较两个序列的中位数大小，如果两个数相等，则该数为整个2n个数据的中位数，否则通过比较，分别减少两个序列的查找范围，确定查找的起止位置，继续查找。
直接折半存在的问题
第一次折半
5 1518 243 10
21 30
第二次折半
5 151824
31021 30
当X Y中各自有偶数个时，折半操作可能会去除掉正确结果。如示例2 所示，第一直接折半将去掉5，15，21，30这四个数。第二次折半去掉3，24。得出最终结果(18+10)/2 = 14。然而简单排序后发现正确的中位数应该是(15+18)/2 = 16.5。显然直接折半的过程中，去掉了正确结果的一部分15，所以判断能否直接折半非常有必要。
ii. Gray码问题
问题描述
Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的串，相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。
编程任务
利用分治策略试设计一个算法对任意的n构造相应的Gray码。
数据输入
由文件input.txt提供输入数据n。
结果输出
程序运行结束时，将得到的所有编码输出到文件output.txt中。
输入文件示例
input.txt
3输出文件示例
output.txt
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0实现提示
把原问题分解为两个子问题，分别对两个子问题的每个数组后一位加0和1。
代码实现
中位数问题
package MidNum;
import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
public class MidNum {
public static ArrayList<Integer> ReadInput() throws IOException {
BufferedReader in = null;
try {
in = new BufferedReader(new FileReader("src\\MidNum\\in.txt"));
String sb;
ArrayList<Integer> nums = new ArrayList<Integer>();
while (in.ready()) {
sb = (new String(in.readLine()));
String[] s;
s = sb.split(" ");
for(String i : s){
nums.add(Integer.parseInt(i));
}
}
in.close();
return nums;
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return null;
}
// 求单个数组的中位数
public static double mid(ArrayList<Integer> arrayList){
int len = arrayList.size();
int mid = len/2;
if(mid*2 == len){
return (arrayList.get(mid) + arrayList.get(mid-1))/2.0;
}else {
return (double)arrayList.get(mid);
}
}
// 取数组的一半，front为真则取前一半，反之取后一半
public static ArrayList<Integer> half(ArrayList<Integer> arrayList, boolean front, boolean safe){
int len = arrayList.size();
int mid = len/2;
ArrayList<Integer> list = new ArrayList<Integer>();
if(front) {
if (mid * 2 == len) {
for (int i = 0; i < mid; i++) {
list.add(arrayList.get(i));
}
if(!safe){
// 不能直接折半则保留中间的数
list.add(arrayList.get(mid));
}
} else {
for (int i = 0; i <= mid; i++) {
list.add(arrayList.get(i));
}
}
return list;
} else {
if (mid * 2 == len) {
if (!safe){
// 不能直接折半则保留中间的数
list.add(arrayList.get(mid-1));
}
for (int i = mid; i < len; i++) {
list.add(arrayList.get(i));
}
} else {
for (int i = mid; i < len; i++) {
list.add(arrayList.get(i));
}
}
return list;
}
}
// 判断能否直接折半
public static boolean safe_to_cut(ArrayList<Integer> X, ArrayList<Integer> Y){
int len = X.size();
int mid = len/2;
if (mid*2 == len){
int x1 = X.get(mid-1);
int x2 = X.get(mid);
int y1 = Y.get(mid-1);
int y2 = Y.get(mid);
if (mid(X) > mid(Y)) {
if (x2 < y2) {
return false;
}
if (x1 < y1){
return false;
}
}
else if (mid(X) < mid(Y)){
if (y2 < x2){
return false;
}
if (y1 < x1){
return false;
}
}
}
return true;
}
// 计算合并后的中位数
public static double getMid(ArrayList<Integer> X, ArrayList<Integer> Y){
double mid_x = mid(X);
double mid_y = mid(Y);
ArrayList<Integer> array = null;
// 如果X Y只有一个数，则返回他们平均数
if (X.size() == 1 && Y.size() == 1){
return (mid_x + mid_y)/2.0;
}
// 如果X Y 各自剩余2个 考虑到折半安全问题，剩余2个时可能已经不能再次折半
if (X.size() == 2 && Y.size() == 2){
array = new ArrayList<Integer>();
array.addAll(X);
array.addAll(Y);
array.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
return (array.get(1) + array.get(2))/2.0;
}
if (mid_x > mid_y){
// 如果X的中位数大于Y的，取X的前半部分，Y的后半部分
if (safe_to_cut(X, Y)) {
// 如果可以直接折半
X = half(X, true, true);
Y = half(Y, false, true);
} else {
X = half(X, true, false);
Y = half(Y, false, false);
}
return getMid(X, Y);
} else if ( mid_x == mid_y){
// 如果X Y中位数相等，返回这个值
return (double) mid_x;
} else {
// 如果X的中位数小于Y的，取X的后半部分，Y的前半部分
if (safe_to_cut(X, Y)) {
// 如果可以直接折半
X = half(X, false, true);
Y = half(Y, true, true);
} else {
X = half(X, false, false);
Y = half(Y, true, false);
}
return getMid(X, Y);
}
}
public static void output(double x) throws IOException {
BufferedWriter out = new BufferedWriter(new FileWriter("src\\MidNum\\out.txt"));
out.write(String.format("%f", x));
out.close();
}
public static void main(String[] args) {
// 读取输入
ArrayList<Integer> nums = null;
try {
nums = ReadInput();
} catch (IOException e) {
e.printStackTrace();
}
// 将输入写入X Y
ArrayList<Integer> X = new ArrayList<Integer>();
ArrayList<Integer> Y = new ArrayList<Integer>();
for (int i = 1; i <= nums.get(0); i++) {
X.add(nums.get(i));
Y.add(nums.get(i + nums.get(0)));
}
// 计算中位数
double result = getMid(X, Y);
// 输出结果
try {
output(result);
} catch (IOException e) {
e.printStackTrace();
}
}
}
格雷码问题
package Grey;
import java.io.*;
import java.util.ArrayList;
public class Grey {
public static int ReadInput() throws IOException {
BufferedReader in = null;
try {
in = new BufferedReader(new FileReader("src\\Grey\\in.txt"));
String s;
if (in.ready()) {
s = (new String(in.readLine()));
in.close();
return Integer.parseInt(s);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return 0;
}
public static ArrayList<StringBuffer> getGrey(int n){
ArrayList<StringBuffer> list = new ArrayList<StringBuffer>();
if (n==1){
list.add(new StringBuffer("0"));
list.add(new StringBuffer("1"));
return list;
}
ArrayList<StringBuffer> new_list = new ArrayList<StringBuffer>();
ArrayList<StringBuffer> next_list = getGrey(n-1);
for(StringBuffer s: next_list){
new_list.add(new StringBuffer("0").append(s));
}
for (int i = next_list.size() - 1; i > -1 ; i--) {
new_list.add(new StringBuffer("1").append(next_list.get(i)));
}
return new_list;
}
public static void output(StringBuffer sb) throws IOException {
BufferedWriter out = new BufferedWriter(new FileWriter("src\\Grey\\out.txt"));
out.write(String.valueOf(sb));
out.close();
}
public static void main(String[] args) {
int n = 0;
//读取输入
try {
n = ReadInput();
} catch (IOException e) {
e.printStackTrace();
}
if (n<1){
System.out.println("Invalid Input!");
return;
}
StringBuffer sb = new StringBuffer();
for(StringBuffer s: getGrey(n)){
sb.append(s);
sb.append("\n");
}
//输出
try {
output(sb);
} catch (IOException e) {
e.printStackTrace();
}
}
}
目录结构
关于
原创文章，转载请声明！原文为本人在CSDN发布 CSDN链接
