1. 中位数问题
« 问题描述
设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中。
| 输入文件示例 |
输出文件示例 |
| input.txt |
output.txt |
| 3 5 15 18 3 14 21 |
14 |
« 实现提示
比较两个序列的中位数大小，如果两个数相等，则该数为整个2n个数据的中位数，否则通过比较，分别减少两个序列的查找范围，确定查找的起止位置，继续查找。
2. Gray码问题
« 问题描述
Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的串，相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。
« 编程任务
利用分治策略试设计一个算法对任意的n构造相应的Gray码。
« 数据输入
由文件input.txt提供输入数据n。
« 结果输出
程序运行结束时，将得到的所有编码输出到文件output.txt中。
| 输入文件示例 |
输出文件示例 |
| input.txt |
output.txt |
| 3 |
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。
实现代码：
import java.io.*;
public class Main {
public static void main(String[] args){
Middle();
Gray();
}
public static void Middle(){
//读取文件，完成数组a，b的初始化
int[] a=null;
int[] b=null;
int len=0;
try{
BufferedReader fr=new BufferedReader(new FileReader("src/file/input_1.txt"));
String line=fr.readLine();
len=Integer.parseInt(line);
String str=fr.readLine();
String[] sa=str.split(" ");
str=fr.readLine();
String[] sb=str.split(" ");
fr.close();
a = new int[len];
b = new int[len];
for(int i=0;i<len;i++){
a[i]=Integer.parseInt(sa[i]);
b[i]=Integer.parseInt(sb[i]);
}
}catch(Exception e){
System.out.println(e);
}
boolean ji=len%2==0?false:true;
findMiddle(a,0,len-1,b,0,len-1,ji);
}
public static void findMiddle(int[] a,int start_a,int end_a,int[] b,int start_b,int end_b,boolean j){
/*
* 比较两个数组的中位数mid1和mid2，若相等则就是总的中位数mid
* 若a、b都只剩两个元素，则取四个元素中第二小的为mid
* 若mid1<mid2，取此时a的右部分，b的左部分，进行递归
* 若mid1>mid2，取此时a的左部分，b的右部分，进行递归
* */
int mid1=(start_a+end_a)/2, mid2=(start_b+end_b)/2;
System.out.println(a[mid1]+","+b[mid2]);
if(a[mid1]==b[mid2]){
writeNum(a[mid1]);
}
else if(end_a-start_a<=1&&end_b-start_b<=1){//<=4时直接解决
int result=0;
if(end_a-start_a==1&&end_b-start_b==1)//4
result=getMid(a[start_a],a[end_a],b[start_b],b[end_b]);
else if(end_a==start_a&&end_b==start_b)//2
result=a[end_a]>b[end_b]?b[end_b]:a[end_a];
else if(end_a==start_a)//a1b2，选三者中位数
result=a[end_a]<b[start_b] ? b[start_b]:(a[end_a]<b[end_b]?a[end_a]:b[end_b]);
else//a2b1，选三者中位数
result=b[end_b]<a[start_a]?a[start_a]:(b[end_b]<a[end_a]?b[end_b]:a[end_a]);
writeNum(result);
return;
}
else if(a[mid1]<b[mid2]){
if(j)
findMiddle(a,mid1,end_a,b,start_b,mid2,true);
else
findMiddle(a,mid1+1,end_a,b,start_b,mid2,true);
}
else{
if(j)
findMiddle(a,start_a,mid1,b,mid2,end_b,true);
else
findMiddle(a,start_a,mid1,b,mid2+1,end_b,true);
}
}
public static int getMid(int a,int b,int c,int d){//选四个数中的中位数
System.out.println(a+","+b+","+c+","+d);
int[] num={a,b,c,d};
int result,min=0;
for(int i=1;i<4;i++){
if(num[i]<num[min])
min=i;
}
result=min==0?num[1]:num[0];
for(int i=0;i<4;i++){
if(i!=min&&num[i]<result)
result=num[i];
}
System.out.println("result: "+result);
return result;
}
public static void writeNum(int n){
try{
FileWriter fw=new FileWriter(new File("src/file/output_1.txt"));
fw.write(String.valueOf(n));
fw.close();
}catch(IOException e){
System.out.println(e);
}
}
public static void Gray(){
int len=0;
try{
BufferedReader bf=new BufferedReader(new FileReader("src/file/input_2.txt"));
len=Integer.parseInt(bf.readLine());
bf.close();
}catch(IOException e){
System.out.println(e);
}
int row=(int)Math.pow(2,len);
int [][] gray=new int[row][len];
getGray(gray,len,row);
try{
File f= new File("src/file/output_2.txt");
FileWriter fw=new FileWriter(f);
for(int i=0;i<row;i++){
String line="";
for(int j=len-1;j>=0;j--){
line=line+String.valueOf(gray[i][j])+" ";
}
line+="\n";
fw.write(line);
}
fw.close();
}catch(IOException e){
System.out.println(e);
}
}
public static void getGray(int[][] gray,int n,int row){
/*
* n表示gray码的长度，row表示生成的gray码个数
* 前一半的头一位是0，后一半的头一位是1，n-1，row除2递归
* 当n=1时“递”结束，利用对称性为其它单元赋值
* 在gray数组中，每一个gray编码是反向存储的
* */
for(int i=0;i<row/2;i++){
gray[i][n-1]=0;
gray[row-i-1][n-1]=1;
}
if(n==1){//递归结束
gray[0][n-1]=0;
gray[1][n-1]=1;
return;
}
getGray(gray,n-1,row/2);
//利用对称性赋值
for(int i=row/2;i<row;i++){
for(int j=0;j<n-1;j++){
gray[i][j]=gray[row-1-i][j];
}
}
}
}
