分治法應用——解決中位數&格雷碼問題

中位數問題

問題描述

設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中，

實作提示

比較兩個序列的中位數大小，如果兩個數相等，則該數為整個2n個資料的中位數，否則通過比較，分別減少兩個序列的查找范圍，確定查找的起止位置，繼續查找，

實作代碼

package com.company;

public class Median {

    static int x[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    static int y[] = {2, 4, 6, 7, 8, 10, 11, 12, 13, 18};
    static int a[] = {5, 15, 18};
    static int b[] = {3, 14, 21};

    //low和high分別為減少查找范圍后陣列的查找起點和終點
    public int findMedian(int x[], int y[], int length, int xLow, int xHigh, int yLow, int yHigh) {
        if (length == 1) {//當前陣列長度為1，取較小值為中位數
            return x[xLow] <= y[yLow] ? x[xLow] : y[yLow];
        }
        if (length % 2 == 0) {//長度為偶數，中位數下標=起點下標+長度/2-1
            if (x[xLow + length / 2 - 1] == y[yLow + length / 2 - 1]) {//兩陣列中位數相等
                return x[xLow + length / 2 - 1];
            } else if (x[xLow + length / 2 - 1] < y[yLow + length / 2 - 1]) {//x中位數小于y，查找x后半部分以及y前半部分
                return findMedian(x, y, length / 2, xLow + length / 2, xHigh, yLow, yHigh - length / 2);
            } else {//y中位數小于x，查找y后半部分以及x前半部分
                return findMedian(x, y, length / 2, xLow, xHigh - length / 2, yLow + length / 2, yHigh);
            }
        } else {//長度為奇數，中位數下標=起點下標+長度/2
            if (x[xLow + length / 2] == y[yLow + length / 2]) {//兩陣列中位數相等
                return x[xLow + length / 2];
            } else if (x[xLow + length / 2] < y[yLow + length / 2]) {//x中位數小于y，查找x后半部分以及y前半部分
                return findMedian(x, y, length / 2 + 1, xLow + length / 2, xHigh, yLow, yHigh - length / 2);
            } else {//y中位數小于x，查找y后半部分以及x前半部分
                return findMedian(x, y, length / 2 + 1, xLow, xHigh - length / 2, yLow + length / 2, yHigh);
            }
        }
    }

    public static void main(String[] args) {
        Median median = new Median();
        //int Median = median.findMedian(a, b, a.length, 0, a.length - 1, 0, b.length - 1);
        int Median = median.findMedian(x, y, x.length, 0, x.length - 1, 0, y.length - 1);
        System.out.println(Median);
    }
}

Gray碼問題

問題描述

Gray碼是一個長度為2n的序列，序列中無相同的元素，每個元素都是長度為n位的串，相鄰元素恰好只有一位不同，用分治策略設計一個演算法對任意的n構造相應的Gray碼，

編程任務

利用分治策略試設計一個演算法對任意的n構造相應的Gray碼，

資料輸入

由檔案input.txt提供輸入資料n，

結果輸出

程式運行結束時，將得到的所有編碼輸出到檔案output.txt中，

實作提示

把原問題分解為兩個子問題，分別對兩個子問題的每個陣列后一位加0和1，

實作代碼

package com.company;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Math.pow;

public class Gray {

    public void createGray(int n, int grayNum[][]) {
        if (n == 1) {
            grayNum[0][0] = 0;
            grayNum[1][0] = 1;
        } else {
            int low = (int) pow(2, n - 1);//復制的起點下標
            int high = (int) (pow(2, n));//復制的終點下標+1

            //當n=2時，對第n-1列（即第1列）的前2^1行（第0,1行）填0，后2^1行（第2,3行）填1
            for (int i = 0; i < low; i++) {
                grayNum[i][n - 1] = 0;
            }
            for (int i = low; i < high; i++) {
                grayNum[i][n - 1] = 1;
            }

            createGray(n - 1, grayNum);

            for (int i = 0; i < n - 1; i++) {
                for (int j = low; j < high; j++) {
                    //當n=2時，將第0列的0,1行元素復制到3,2行（鏡像對稱）
                    //此時下標分別為0,1；high=4，high-j-1分別等于3,2，即為第3行、第2行
                    grayNum[j][i] = grayNum[high - j - 1][i];
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {

        String str;
        int n;
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("請輸入n的值：");
        str = bufferedReader.readLine();
        n = Integer.parseInt(str);

        int row = (int) pow(2, n);
        int grayNum[][] = new int[row][n];//創建二維陣列保存格雷碼

        Gray gray = new Gray();
        gray.createGray(n, grayNum);

        //將陣列元素按行逆序輸出
        for (int i = 0; i < row; i++) {
            for (int j = n - 1; j >= 0; j--) {
                System.out.print(grayNum[i][j]);
                if (j == 0) {
                    System.out.println("");
                } else {
                    System.out.print(" ");
                }
            }
        }
    }
}

結果展示