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
13 25 15 18 33 14 21
输出文件示例1
output.txt
14.5
输入文件示例2
input.txt
14 25 15 18 24 33 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
10 0 0 20 0 1 30 1 1 40 1 0 51 1 0 61 1 1 71 0 1 81 0 0
实现提示
把原问题分解为两个子问题，分别对两个子问题的每个数组后一位加0和1。
代码实现
中位数问题
1package MidNum; 2 3import java.io.*; 4import java.util.ArrayList; 5import java.util.Comparator; 6 7public class MidNum { 8 9 public static ArrayList<Integer> ReadInput() throws IOException { 10 BufferedReader in = null; 11 try { 12 in = new BufferedReader(new FileReader("src\\MidNum\\in.txt")); 13 String sb; 14 ArrayList<Integer> nums = new ArrayList<Integer>(); 15 while (in.ready()) { 16 sb = (new String(in.readLine())); 17 String[] s; 18 s = sb.split(" "); 19 for(String i : s){ 20 nums.add(Integer.parseInt(i)); 21 } 22 } 23 in.close(); 24 return nums; 25 } catch (FileNotFoundException e) { 26 e.printStackTrace(); 27 } 28 return null; 29 } 30 31 // 求单个数组的中位数 32 public static double mid(ArrayList<Integer> arrayList){ 33 int len = arrayList.size(); 34 int mid = len/2; 35 if(mid*2 == len){ 36 return (arrayList.get(mid) + arrayList.get(mid-1))/2.0; 37 }else { 38 return (double)arrayList.get(mid); 39 } 40 } 41 42 // 取数组的一半，front为真则取前一半，反之取后一半 43 public static ArrayList<Integer> half(ArrayList<Integer> arrayList, boolean front, boolean safe){ 44 int len = arrayList.size(); 45 int mid = len/2; 46 ArrayList<Integer> list = new ArrayList<Integer>(); 47 if(front) { 48 if (mid * 2 == len) { 49 for (int i = 0; i < mid; i++) { 50 list.add(arrayList.get(i)); 51 } 52 if(!safe){ 53 // 不能直接折半则保留中间的数 54 list.add(arrayList.get(mid)); 55 } 56 } else { 57 for (int i = 0; i <= mid; i++) { 58 list.add(arrayList.get(i)); 59 } 60 } 61 return list; 62 } else { 63 if (mid * 2 == len) { 64 if (!safe){ 65 // 不能直接折半则保留中间的数 66 list.add(arrayList.get(mid-1)); 67 } 68 for (int i = mid; i < len; i++) { 69 list.add(arrayList.get(i)); 70 } 71 } else { 72 for (int i = mid; i < len; i++) { 73 list.add(arrayList.get(i)); 74 } 75 } 76 return list; 77 } 78 } 79 80 // 判断能否直接折半 81 public static boolean safe_to_cut(ArrayList<Integer> X, ArrayList<Integer> Y){ 82 int len = X.size(); 83 int mid = len/2; 84 if (mid*2 == len){ 85 int x1 = X.get(mid-1); 86 int x2 = X.get(mid); 87 int y1 = Y.get(mid-1); 88 int y2 = Y.get(mid); 89 if (mid(X) > mid(Y)) { 90 if (x2 < y2) { 91 return false; 92 } 93 if (x1 < y1){ 94 return false; 95 } 96 } 97 else if (mid(X) < mid(Y)){ 98 if (y2 < x2){ 99 return false; 100 } 101 if (y1 < x1){ 102 return false; 103 } 104 } 105 } 106 return true; 107 } 108 109 // 计算合并后的中位数 110 public static double getMid(ArrayList<Integer> X, ArrayList<Integer> Y){ 111 double mid_x = mid(X); 112 double mid_y = mid(Y); 113 ArrayList<Integer> array = null; 114 // 如果X Y只有一个数，则返回他们平均数 115 if (X.size() == 1 && Y.size() == 1){ 116 return (mid_x + mid_y)/2.0; 117 } 118 // 如果X Y 各自剩余2个 考虑到折半安全问题，剩余2个时可能已经不能再次折半 119 if (X.size() == 2 && Y.size() == 2){ 120 array = new ArrayList<Integer>(); 121 array.addAll(X); 122 array.addAll(Y); 123 array.sort(new Comparator<Integer>() { 124 @Override 125 public int compare(Integer o1, Integer o2) { 126 return o1.compareTo(o2); 127 } 128 }); 129 return (array.get(1) + array.get(2))/2.0; 130 } 131 if (mid_x > mid_y){ 132 // 如果X的中位数大于Y的，取X的前半部分，Y的后半部分 133 if (safe_to_cut(X, Y)) { 134 // 如果可以直接折半 135 X = half(X, true, true); 136 Y = half(Y, false, true); 137 } else { 138 X = half(X, true, false); 139 Y = half(Y, false, false); 140 } 141 return getMid(X, Y); 142 } else if ( mid_x == mid_y){ 143 // 如果X Y中位数相等，返回这个值 144 return (double) mid_x; 145 } else { 146 // 如果X的中位数小于Y的，取X的后半部分，Y的前半部分 147 if (safe_to_cut(X, Y)) { 148 // 如果可以直接折半 149 X = half(X, false, true); 150 Y = half(Y, true, true); 151 } else { 152 X = half(X, false, false); 153 Y = half(Y, true, false); 154 } 155 return getMid(X, Y); 156 } 157 } 158 159 public static void output(double x) throws IOException { 160 BufferedWriter out = new BufferedWriter(new FileWriter("src\\MidNum\\out.txt")); 161 out.write(String.format("%f", x)); 162 out.close(); 163 } 164 165 public static void main(String[] args) { 166 // 读取输入 167 ArrayList<Integer> nums = null; 168 try { 169 nums = ReadInput(); 170 } catch (IOException e) { 171 e.printStackTrace(); 172 } 173 // 将输入写入X Y 174 ArrayList<Integer> X = new ArrayList<Integer>(); 175 ArrayList<Integer> Y = new ArrayList<Integer>(); 176 for (int i = 1; i <= nums.get(0); i++) { 177 X.add(nums.get(i)); 178 Y.add(nums.get(i + nums.get(0))); 179 } 180 // 计算中位数 181 double result = getMid(X, Y); 182 // 输出结果 183 try { 184 output(result); 185 } catch (IOException e) { 186 e.printStackTrace(); 187 } 188 } 189} 190
格雷码问题
1package Grey; 2 3import java.io.*; 4import java.util.ArrayList; 5 6public class Grey { 7 8 public static int ReadInput() throws IOException { 9 BufferedReader in = null; 10 try { 11 in = new BufferedReader(new FileReader("src\\Grey\\in.txt")); 12 String s; 13 if (in.ready()) { 14 s = (new String(in.readLine())); 15 in.close(); 16 return Integer.parseInt(s); 17 } 18 } catch (FileNotFoundException e) { 19 e.printStackTrace(); 20 } 21 return 0; 22 } 23 24 public static ArrayList<StringBuffer> getGrey(int n){ 25 ArrayList<StringBuffer> list = new ArrayList<StringBuffer>(); 26 if (n==1){ 27 list.add(new StringBuffer("0")); 28 list.add(new StringBuffer("1")); 29 return list; 30 } 31 ArrayList<StringBuffer> new_list = new ArrayList<StringBuffer>(); 32 ArrayList<StringBuffer> next_list = getGrey(n-1); 33 for(StringBuffer s: next_list){ 34 new_list.add(new StringBuffer("0").append(s)); 35 } 36 for (int i = next_list.size() - 1; i > -1 ; i--) { 37 new_list.add(new StringBuffer("1").append(next_list.get(i))); 38 } 39 return new_list; 40 } 41 42 public static void output(StringBuffer sb) throws IOException { 43 BufferedWriter out = new BufferedWriter(new FileWriter("src\\Grey\\out.txt")); 44 out.write(String.valueOf(sb)); 45 out.close(); 46 } 47 48 public static void main(String[] args) { 49 int n = 0; 50 //读取输入 51 try { 52 n = ReadInput(); 53 } catch (IOException e) { 54 e.printStackTrace(); 55 } 56 if (n<1){ 57 System.out.println("Invalid Input!"); 58 return; 59 } 60 StringBuffer sb = new StringBuffer(); 61 for(StringBuffer s: getGrey(n)){ 62 sb.append(s); 63 sb.append("\n"); 64 } 65 //输出 66 try { 67 output(sb); 68 } catch (IOException e) { 69 e.printStackTrace(); 70 } 71 } 72} 73
目录结构
关于
原创文章，转载请声明！原文为本人在CSDN发布 CSDN链接