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];
            }
        }
    }

}