分治法应用——解决中位数&格雷码问题

时间:2020-9-12 作者:admin

中位数问题

问题描述

设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个数据的中位数,否则通过比较,分别减少两个序列的查找范围,确定查找的起止位置,继续查找。

实现代码

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中。

输入文件示例

输出文件示例

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。

实现代码

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(" ");
                }
            }
        }
    }
}

结果展示

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。