【分治法】解决中位数问题、格雷码问题以及分治法直接折半存在的问题讨论————武汉理工大学算法分析实验1AlgorithmExperiment

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

3
5 15 18
3 14 21

输出文件示例1

output.txt

14.5

输入文件示例2

input.txt

4
5 15 18 24
3 10 21 30

输出文件示例2

output.txt

16.5

实现提示

比较两个序列的中位数大小，如果两个数相等，则该数为整个2n个数据的中位数，否则通过比较，分别减少两个序列的查找范围，确定查找的起止位置，继续查找。

直接折半存在的问题

第一次折半

5 15 18 24

3 10 21 30

第二次折半

5 15 18 24

3 10 21 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

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 MidNum;

import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;

public class MidNum {

    public static ArrayList<Integer> ReadInput() throws IOException {
        BufferedReader in = null;
        try {
            in = new BufferedReader(new FileReader("src\MidNum\in.txt"));
            String sb;
            ArrayList<Integer> nums = new ArrayList<Integer>();
            while (in.ready()) {
                sb = (new String(in.readLine()));
                String[] s;
                s = sb.split(" ");
                for(String i : s){
                    nums.add(Integer.parseInt(i));
                }
            }
            in.close();
            return nums;
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return null;
    }

    // 求单个数组的中位数
    public static double mid(ArrayList<Integer> arrayList){
        int len = arrayList.size();
        int mid = len/2;
        if(mid*2 == len){
            return (arrayList.get(mid) + arrayList.get(mid-1))/2.0;
        }else {
            return (double)arrayList.get(mid);
        }
    }

    // 取数组的一半，front为真则取前一半，反之取后一半
    public static ArrayList<Integer> half(ArrayList<Integer> arrayList, boolean front, boolean safe){
        int len = arrayList.size();
        int mid = len/2;
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(front) {
            if (mid * 2 == len) {
                for (int i = 0; i < mid; i++) {
                    list.add(arrayList.get(i));
                }
                if(!safe){
                    // 不能直接折半则保留中间的数
                    list.add(arrayList.get(mid));
                }
            } else {
                for (int i = 0; i <= mid; i++) {
                    list.add(arrayList.get(i));
                }
            }
            return list;
        } else {
            if (mid * 2 == len) {
                if (!safe){
                    // 不能直接折半则保留中间的数
                    list.add(arrayList.get(mid-1));
                }
                for (int i = mid; i < len; i++) {
                    list.add(arrayList.get(i));
                }
            } else {
                for (int i = mid; i < len; i++) {
                    list.add(arrayList.get(i));
                }
            }
            return list;
        }
    }

    // 判断能否直接折半
    public static boolean safe_to_cut(ArrayList<Integer> X, ArrayList<Integer> Y){
        int len = X.size();
        int mid = len/2;
        if (mid*2 == len){
            int x1 = X.get(mid-1);
            int x2 = X.get(mid);
            int y1 = Y.get(mid-1);
            int y2 = Y.get(mid);
            if (mid(X) > mid(Y)) {
                if (x2 < y2) {
                    return false;
                }
                if (x1 < y1){
                    return false;
                }
            }
            else if (mid(X) < mid(Y)){
                if (y2 < x2){
                    return false;
                }
                if (y1 < x1){
                    return false;
                }
            }
        }
        return true;
    }

    // 计算合并后的中位数
    public static double getMid(ArrayList<Integer> X, ArrayList<Integer> Y){
        double mid_x = mid(X);
        double mid_y = mid(Y);
        ArrayList<Integer> array = null;
        // 如果X Y只有一个数，则返回他们平均数
        if (X.size() == 1 && Y.size() == 1){
            return (mid_x + mid_y)/2.0;
        }
        // 如果X Y 各自剩余2个 考虑到折半安全问题，剩余2个时可能已经不能再次折半
        if (X.size() == 2 && Y.size() == 2){
            array = new ArrayList<Integer>();
            array.addAll(X);
            array.addAll(Y);
            array.sort(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1.compareTo(o2);
                }
            });
            return (array.get(1) + array.get(2))/2.0;
        }
        if (mid_x > mid_y){
            // 如果X的中位数大于Y的，取X的前半部分，Y的后半部分
            if (safe_to_cut(X, Y)) {
                // 如果可以直接折半
                X = half(X, true, true);
                Y = half(Y, false, true);
            } else {
                X = half(X, true, false);
                Y = half(Y, false, false);
            }
            return getMid(X, Y);
        } else if ( mid_x == mid_y){
            // 如果X Y中位数相等，返回这个值
            return (double) mid_x;
        } else {
            // 如果X的中位数小于Y的，取X的后半部分，Y的前半部分
            if (safe_to_cut(X, Y)) {
                // 如果可以直接折半
                X = half(X, false, true);
                Y = half(Y, true, true);
            } else {
                X = half(X, false, false);
                Y = half(Y, true, false);
            }
            return getMid(X, Y);
        }
    }

    public static void output(double x) throws IOException {
        BufferedWriter out = new BufferedWriter(new FileWriter("src\MidNum\out.txt"));
        out.write(String.format("%f", x));
        out.close();
    }

    public static void main(String[] args) {
        // 读取输入
        ArrayList<Integer> nums = null;
        try {
            nums = ReadInput();
        } catch (IOException e) {
            e.printStackTrace();
        }
        // 将输入写入X Y
        ArrayList<Integer> X = new ArrayList<Integer>();
        ArrayList<Integer> Y = new ArrayList<Integer>();
        for (int i = 1; i <= nums.get(0); i++) {
            X.add(nums.get(i));
            Y.add(nums.get(i + nums.get(0)));
        }
        // 计算中位数
        double result = getMid(X, Y);
        // 输出结果
        try {
            output(result);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

格雷码问题

package Grey;

import java.io.*;
import java.util.ArrayList;

public class Grey {

    public static int ReadInput() throws IOException {
        BufferedReader in = null;
        try {
            in = new BufferedReader(new FileReader("src\Grey\in.txt"));
            String s;
            if (in.ready()) {
                s = (new String(in.readLine()));
                in.close();
                return Integer.parseInt(s);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        return 0;
    }

    public static ArrayList<StringBuffer> getGrey(int n){
        ArrayList<StringBuffer> list = new ArrayList<StringBuffer>();
        if (n==1){
            list.add(new StringBuffer("0"));
            list.add(new StringBuffer("1"));
            return list;
        }
        ArrayList<StringBuffer> new_list = new ArrayList<StringBuffer>();
        ArrayList<StringBuffer> next_list = getGrey(n-1);
        for(StringBuffer s: next_list){
            new_list.add(new StringBuffer("0").append(s));
        }
        for (int i = next_list.size() - 1; i > -1 ; i--) {
            new_list.add(new StringBuffer("1").append(next_list.get(i)));
        }
        return new_list;
    }

    public static void output(StringBuffer sb) throws IOException {
        BufferedWriter out = new BufferedWriter(new FileWriter("src\Grey\out.txt"));
        out.write(String.valueOf(sb));
        out.close();
    }

    public static void main(String[] args) {
        int n = 0;
        //读取输入
        try {
            n = ReadInput();
        } catch (IOException e) {
            e.printStackTrace();
        }
        if (n<1){
            System.out.println("Invalid Input!");
            return;
        }
        StringBuffer sb = new StringBuffer();
        for(StringBuffer s: getGrey(n)){
            sb.append(s);
            sb.append("n");
        }
        //输出
        try {
            output(sb);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

目录结构

代码github链接

个人博客

最后

以上就是老迟到小蝴蝶为你收集整理的【分治法】解决中位数问题、格雷码问题以及分治法直接折半存在的问题讨论————武汉理工大学算法分析实验1AlgorithmExperiment的全部内容，希望文章能够帮你解决【分治法】解决中位数问题、格雷码问题以及分治法直接折半存在的问题讨论————武汉理工大学算法分析实验1AlgorithmExperiment所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。