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

Patrick 等级 515 0 0
标签: Java

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

目录结构

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

关于

代码github仓库

个人博客

原创文章,转载请声明!原文为本人在CSDN发布 CSDN链接

收藏
评论区

相关推荐

Java实现排序算法
//冒泡排序 public static void bubbleSort(int data) { int n data.length; for (int i 0; i < n; i) { for (int j 0; j < n; j) { if (
JS排序算法
引子 有句话怎么说来着: 雷锋推倒雷峰塔,Java implements JavaScript. 当年,想凭借抱Java大腿火一把而不惜把自己名字给改了的JavaScript(原名LiveScript),如今早已光芒万丈。node JS的出现更是让JavaScript可以前后端通吃。虽然Java依然制霸企业级软件开发领域(C/C 的大神们不要打
python实现——最优化算法(二分法、格点法、黄金分割法、牛顿法等)
二分法 函数详见rres,此代码使该算法运行了两次 python def asdf(x): rres8x32x27x3 return rres i2 left0 right1 while i0 : i i1 ans 0.1 mid1 (left right ans) / 2
Java多态实现原理
Java多态概述 多态是面向对象编程语言的重要特性,它允许基类的指针或引用指向派生类的对象,而在具体访问时实现方法的动态绑定。Java 对于方法调用动态绑定的实现主要依赖于方法表,但通过类引用调用(invokevirtual)和接口引用调用(invokeinterface)的实现则有所不同。 类引用调用的大致过程为:Java编译器将Java源代码编译成c
Jvm的内存布局和垃圾回收机制
内存布局 运行时数据区 1. 程序计数器:用来控制代码运行行数。 2. Java 虚拟机栈:每个线程运行方法(A调用B)时,先把A方法放入到栈底,然后加载B方法,B
如何正确停止Java线程,终止Java线程的三种方法
如何正确停止Java线程,终止Java线程的三种方法 在 Java 中有以下 3 种方法可以终止正在运行的线程: 1. 使用退出标志,使线程正常退出,也就是当 run() 方法完成后线程终止。 2. 使用 stop() 方法强行终止线程,但不推荐,该方法已被弃用,原因见后文。 3. 使用 interrupt 方法中断线程。 以下内容翻译自 J
初步了解01背包问题(分治篇)
目录 问题描述(问题描述) 输入格式(输入格式) 输出格式(输出格式) 基于0/1背包的迭代算法(基于01背包的动态规划算法) 0/1背包问题的分析(01背包问题的分析) 分治法(分治法) 总结(总结) 问题描述 Coda非常喜欢玩“NewWorld Online”,受到某部动画的影响,他
【分治法】解决中位数问题、格雷码问题以及分治法直接折半存在的问题讨论————武汉理工大学算法分析实验1
AlgorithmExperiment算法分析课实验分治法的核心思想是将问题分为若干子问题去,使规模一步步缩小,最终分到一步就能得出结果。要注意每个子问题需要性质相同而且相互不重复。采用分治法完成如下任务: i. 中位数问题 问题描述设X 0 : n 1和Y 0 : n – 1 为两个数组,每个数组中含有n个已排好序的数。找出X和Y
简析限流算法
简析限流算法1.简介限流顾名思义是限制流量,限制流量的目的是为了保障服务稳定运行,避免服务被流量冲垮。当流量超出服务处理能力时,部分请求将会被限流组件拦截。被拦截的请求可能会被丢弃,如果是 C 端请求,那么这个请求可能会被导向指定的错误页上,而不是生硬的拒绝。这里我们丢
从未有人把JVM原理讲的这么详细
JVM原理1.简述JVM是Java Virtual Machine(Java虚拟机)的缩写,是通过在实际的计算机上仿真模拟各种计算机功能来实现的。由一套字节码指令集、一组寄存器、一个栈、一个垃圾回收堆和一个存储方法域等组成。JVM屏蔽了与操作系统平台相关的信息,使得Java程序只需要生成在Java虚拟机上运行的目标代码(字节码),就可在多种平台上不加修改的运
读取csv文件编码的方法
with open(fpath, 'rb') as f: result chardet.detect(f.read()) e result['encoding'] print(e)
代码审查机制
代码审查机制[TOC] 什么是代码审查Code Review已经是很多公司的常规实践,初看上去好像是浪费时间,降低工作效率,其实反之,好处大家有目共睹。它能检查代码的正确性,合理性,安全性,发现隐秘的bugs,让系统更可靠的运行。它能保证代码能有两个或以上的人熟悉,促进知识共享。它能让团队成员互为备份,互相支持,不会有SPOF。它能威慑埋雷的任何想法,杜绝邪
C进阶 - 内存四驱模型
一.内存四驱模型不知我们是否有读过 《深入理解 java 虚拟机》这本书,强烈推荐读一下。在 java 中我们将运行时数据,分为五个区域分别是:程序计数器,java 虚拟机栈,本地方法栈,java 堆,方法区。在 c/c++ 中我们将运行时数据,分为四个区域分别是:栈区,堆区,数据区,代码区。我们详细来介绍下:1. 栈区:由编译器自动分配释放 ,存放函数的
总结了pandas提取数据的15种方法,统统只需1行代码,真香!
pandas是python数据分析必备工具,它有强大的数据清洗能力,往往能用非常少的代码实现较复杂的数据处理今天,鸟哥总结了pandas筛选数据的15个常用技巧,主要包括5个知识点:1.比较运算:、<、、、<、!2.范围运算:between(left,right)3.字符筛选:str.contains(pattern或字符串,naFalse)4.逻辑运算:&
javascript实践教程-02-javascript入门
本节目标1. 掌握如何编写javascript代码。2. 掌握javascript的3个弹框。3. 掌握javascript的注释。4. 掌握浏览器的调试工具控制台。 内容摘要本篇介绍了如何在网页上编写js代码,如何引入外部js代码文件,js的3个弹框、注释语法,还有浏览器调试工具的控制台使用。阅读时间1520分钟。 script标签如果我们需要在网页中编写

热门文章

最新文章