首页 / 算法 / 2020年09月 HNUCM-OJ算法分析与设计作业7

2020年09月 HNUCM-OJ算法分析与设计作业7

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2020年09月 HNUCM-OJ算法分析与设计作业7，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8251字，纯文字阅读大概需要12分钟。

内容图文

@ZHANGQIANYI2020

HNUCM-OJ 归并排序，大整数乘法，第k小元素问题，第k大元素问题，前m大数，找中位数

问题 A: 归并排序
问题 B: 大整数乘法
问题 C: 第k小元素问题
问题 D: 第k大元素问题
问题 E: 前m大数
问题 F: 找中位数

问题 A: 归并排序

（时间限制: 1 Sec 内存限制: 256 MB）

题目描述：

编写一个程序，使用分治策略实现二路归并排序（升序）。

输入：

多组输入，每组第一个数字为数组长度，然后输入一个一维整型数组。

输出：

输出排序之后（升序）的一维整型数组，每组输出占一行。

样例输入：

6 1 8 6 5 3 4
5 12 42 2 5 8

样例输出：

1 3 4 5 6 8
2 5 8 12 42

参考答案：

import java.util.Scanner;
 
public class Main {
     public static void sort(int []arr){
         int []temp = new int[arr.length];
         sort(arr,0,arr.length-1,temp);
     }
     private static void sort(int[] arr,int left,int right,int []temp){
         if(left<right){
             int mid = (left+right)/2;
             sort(arr,left,mid,temp);
             sort(arr,mid+1,right,temp);
             merge(arr,left,mid,right,temp);
         }
     }
     private static void merge(int[] arr,int left,int mid,int right,int[] temp){
         int i = left;
         int j = mid+1;
         int t = 0;
         while (i<=mid && j<=right){
             if(arr[i]<=arr[j]){
                 temp[t++] = arr[i++];
             }else {
                 temp[t++] = arr[j++];
             }
         }
         if(i>mid){
            for(int q=j;q<=right;q++)
                temp[t++] = arr[q];
         }else{
            for(int q=i;q<=mid;q++)
                temp[t++] = arr[q];
         }
         t = 0;
         while(left <= right){
            arr[left++] = temp[t++];
         }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int n=sc.nextInt();
            int a[]=new int[n];
            for(int i=0;i<n;i++) {
                a[i]=sc.nextInt();
            }
            sort(a);
            for(int i=0;i<n;i++) {
                System.out.print(a[i]+" ");
            }
        }
    }
}

问题 B: 大整数乘法

（时间限制: 1 Sec 内存限制: 128 MB）
题目描述：

使用分治算法实现两个大整数相乘。

输入：

两个十进制大整数，满足每一个整数长度为2^n且两个大整数的长度相等。（多组数据）

输出：

两个大整数的乘积。

样例输入：

1234 5678

样例输出：

参考答案：

import java.util.Scanner;
 
public class Main {
    public static long zhengshucheng(long x,long y,int n) {
        int signx=(x<0?-1:1);
        int signy=(y<0?-1:1);
        int sign=signx*signy;
        x=Math.abs(x);
        y=Math.abs(y);
        if(x==0||y==0) {
            return 0;
        }else if(n==1) {
            return sign*x*y;
        }else {
            long A=(long) (x/Math.pow(10, n/2));
            long B=(long) (x%Math.pow(10, n/2));
            long C=(long) (y/Math.pow(10, n/2));
            long D=(long) (y%Math.pow(10, n/2));
            long AC=zhengshucheng(A,C,n/2);
            long BD=zhengshucheng(B,D,n/2);
            long ABCD=zhengshucheng((A-B),(D-C),n/2)+AC+BD;
             
            return (long) (sign*(AC*Math.pow(2,n)+ABCD*Math.pow(2, n/2)+BD));
        }
    }
        public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            long x=sc.nextInt();
            long y=sc.nextInt();
            long z=x*y;
            System.out.println(z);
        }
    }
}

问题 C: 第k小元素问题

（时间限制: 1 Sec 内存限制: 128 MB）

题目描述：

输入一个整数数组，请求出该数组的第k小元素。要求时间复杂度为O(n)。

输入：

每组输入包括两行，第一行为一个整数数组，两个数字之间用空格隔开；第二行为k值。数组中元素个数小于10^9。

输出：

输出第k小元素的值。

样例输入：

2 5 6 1 8 7 9
2

样例输出：

参考答案：

import java.util.Random;
import java.util.Scanner;
 
public class Main {
    public static int quickSelect(int[] arr, int start, int end, int k) {
        if (start > end)
            return -1;
        int p = partition(arr, start, end);
        if (k == p) {
            return p;
        } else if (k < p) {
            return quickSelect(arr,start, p-1,k);
        } else {
            return quickSelect(arr,p+1,end,k);
        }
    }
    public static int partition(int[] arr, int start, int end) {
        if (start == end)
            return start;
        int p = getRandom(start, end);
        swap(arr, p, start);
        p = start;
        int p1 = start;
        int p2;
        for (p2 = p + 1; p2 <= end; p2++) {
            if (arr[p2] < arr[p]) {
                p1++;
                swap(arr, p1, p2);
            }
        }
        swap(arr, p1, p);
        p = p1;
        return p;
    }
    public static int getRandom(int start, int end) {
        Random random = new Random();
        int temp = random.nextInt(end - start + 1) + start;
        return temp;
    }
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    public static void printArray(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if(i < arr.length -1) {
                System.out.print(" ");
            }
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s1 = sc.nextLine();
            String s2 = sc.nextLine();
            int num = Integer.parseInt(s2);
            String[] arrString = s1.split(" ");
            int[] arrNum = new int[arrString.length];
            for (int i = 0; i < arrString.length; i++) {
                arrNum[i] = Integer.parseInt(arrString[i]);
            }
            arrString = null;
            int result = quickSelect(arrNum, 0, arrNum.length - 1, num - 1);
            if (result != -1) {
                System.out.println(arrNum[result]);
            }
        }
        sc.close();
    }
}

问题 D: 第k大元素问题

（时间限制: 1 Sec 内存限制: 128MB）

题目描述：

输入n个整数和一个正整数k(1<=k<=n)，输出这些整数从大到小排序后的第k个。（要求时间复杂度为O(n)，需使用随机化分区）。

输入：

多组数据输入，每组第一个数字为数组的长度n, 然后接下输入n个整数，最后输入整数k(1<=k<=n)。

输出：

输出数组降序排序后的第k个整数。

样例输入：

5 1 5 2 4 3 3
6 1 2 3 4 5 6 1

样例输出：

3
6

参考答案：

import java.util.Random;
import java.util.Scanner;
 
public class Main {
    public static int Ran(int p,int r) {
        Random ran=new Random();
        int i=ran.nextInt(r-p)+p;
        return i;
    }
    private static int partition(int[] a, int p, int r) {
        int x=a[r];
        int i=p-1;
        int temp=0;
        for(int j=p;j<=r-1;j++) {
            if(a[j]>=x) {
                i=i+1;
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
                temp=0;
            }
        }
        temp=a[i+1];
        a[i+1]=a[r];
        a[r]=temp;
        return i+1;
    }
    private static int ranpartition(int[] a, int p, int r) {
        // TODO Auto-generated method stub
        int q=Ran(p,r);
        int temp=a[q];
        a[q]=a[r];
        a[r]=temp;
        return partition(a,p,r);
    }
    public static int ranselect(int[] a,int p,int r,int k) {
        if(p==r)
            return a[p];
        int i=ranpartition(a,p,r);
        int j=i-p+1;
        if(k<=j) {
            return ranselect(a,p,i,k);
        }else {
            return ranselect(a,i+1,r,k-j);
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int n=sc.nextInt();
            int a[]=new int[n];
            for(int i=0;i<n;i++) {
                a[i]=sc.nextInt();
            }
            int k=sc.nextInt();
            System.out.println(ranselect(a,0,n-1,k));
        }
    }
}

问题 E: 前m大数

（时间限制: 1 Sec 内存限制: 33MB）

题目描述：

给你n个整数，请按从大到小的顺序输出其中前m大的数。

输入：

每组测试数据有两行，第一行有两个数n,m(0<n,m<1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。

输出：

对每组测试数据按从大到小的顺序输出前m大的数。

样例输入：

5 3
3 -35 92 213 -644

样例输出：

213 92 3

参考答案：

import java.util.Random;
import java.util.Scanner;
 
public class Main {
    public static int Ran(int p,int r) {
        Random ran=new Random();
        int i=ran.nextInt(r-p)+p;
        return i;
    }
    private static int partition(int[] a, int p, int r) {
        int x=a[r];
        int i=p-1;
        int temp=0;
        for(int j=p;j<=r-1;j++) {
            if(a[j]>=x) {
                i=i+1;
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
                temp=0;
            }
        }
        temp=a[i+1];
        a[i+1]=a[r];
        a[r]=temp;
        return i+1;
    }
    private static int ranpartition(int[] a, int p, int r) {
        // TODO Auto-generated method stub
        int q=Ran(p,r);
        int temp=a[q];
        a[q]=a[r];
        a[r]=temp;
        return partition(a,p,r);
    }
    public static void ranqsort(int a[],int p,int r) {
        if(p<r) {
            int q=ranpartition(a,p,r);
            ranqsort(a,p,q-1);
            ranqsort(a,q+1,r);
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int n=sc.nextInt();
            int m=sc.nextInt();
            int a[]=new int[n];
            for(int i=0;i<n;i++) {
                a[i]=sc.nextInt();
            }
            ranqsort(a,0,n-1);
            for(int i=0;i<m;i++) {
                System.out.print(a[i]+" ");
            }
            System.out.println();
        }
    }
}

问题 F: 找中位数

（时间限制: 1 Sec 内存限制: 128MB）

题目描述：

请设计一个算法，不排序，快速计算出一个无序数列的中位数。时间复杂度要求为O(n)。
如果有奇数个元素，中位数则是数组排序后最中间的那个数字。
如果是偶数个元素，中位数则是数组排序后最中间两个元素的平均值。

输入：

有多组输入，每组输入的第一行为n(1<=n<=1e5)，表示该数列的元素个数。
第二行为n个整数组成的无序数列

输出：

每组样例输出一行，表示该无序数列的中位数。
若为偶数，请保留三位小数
若为奇数，直接输出

样例输入：

5
5 3 2 1 4

样例输出：

参考答案：

import java.text.DecimalFormat;
import java.util.Scanner;
 
public class Main {
    public static int partition(int a[],int p,int q) {
        int x=a[p];
        int i=p,j;
        for(j=p+1;j<=q;j++) {
            if(a[j]<x) {
                i++;
                swap(a,i,j);
            }
        }
        swap(a,p,i);
        return i;
    }
    public static void swap(int a[],int p,int q) {
        int v;
        v=a[p];
        a[p]=a[q];
        a[q]=v;
    }
    public static void getMid(int a[],int p,int q) {
        int mid=(p+q)/2;
        while(true) {
            int pos=partition(a,p,q);
            if(pos==mid)break;
            else if(pos>mid) {q=pos-1;}
            else {p=pos+1;}
        }
        if(a.length%2!=0) {
            System.out.println(a[mid]);
        }
        else {
            double MID=1.0*(a[mid]+a[mid+1])/2;
            System.out.println(String.format("%.3f", MID));
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n=sc.nextInt();
            int a[]=new int[n];
        for(int i=0;i<a.length;i++) {
            a[i]=sc.nextInt();
        }
        getMid(a,0,a.length-1);
        }
    }
}

内容总结

以上是互联网集市为您收集整理的2020年09月 HNUCM-OJ算法分析与设计作业7全部内容，希望文章能够帮你解决2020年09月 HNUCM-OJ算法分析与设计作业7所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/611205.html

来源：【匿名】

【上一篇】2020年09月 HNUCM-OJ算法分析与设计作业8 【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【2020年09月 HNUCM-OJ算法分析与设计作业7】教程文章相关的互联网学习教程文章

南邮算法分析与设计实验4 密码算法

南邮算法分析与设计实验4 密码算法实验目的了解现代密码学的基本原理和数论的基础知识，掌握非对称密码体制的著名代表RSA加密算法的工作原理和流程，并设计实现一个简单的密钥系统。实验内容了解加/解密的基本原理和工作过程，用公开密钥对明文进行加密，并用私人密钥对密文进行解密，构造一个简单的 RSA 公开密钥系统。实验原理 1、RSA算法是由麻省理工学院的 Ron Rivest,Adi Shamir 和Len Adleman 于 1977 年研制并于...

广度优先搜索（BFS）思路及算法分析【代码】【图】

1、算法用途：是一种图像搜索演算法。用于遍历图中的节点，有些类似于树的深度优先遍历。这里唯一的问题是，与树不同，图形可能包含循环，因此我们可能会再次来到同一节点。 2、主要思想：主要借助一个队列、一个布尔类型数组、邻接矩阵完成（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将各点以及各点的关系存入邻接矩阵。再从第一个点开始，将一个点存入队列，然后在邻接表中找到他的相邻点，存入队列，...

数据结构与算法分析

线性表数据元素的排列方式是线性的顺序表：顺序表是在计算机中以数组的形式保存的线性表结构除了头尾，其他的元素依次首尾相连在内存中是一块连续的存储空间，每个元素占用相同的空间，所以顺序表支持随机访问e[i]=e[1]+e[i-1]*length, 1<=i<=n,length是单个元素所占的空间Java数组 Java在定义数组的时候，在堆里面分配一个连续的固定大小的空间，用于存放基本数据类型或者对象的引用。顺序表支持随机存取，所以Java数组用任意下...

JVM之可达性分析算法和引用

1、可达性分析算法　通过一系列称为GC Roots的根对象作为起始节点集，根据引用关系向下搜索，搜索走过的路径叫做引用链，如果某个对象到GC Roots节点集没有任何的引用链也被称为不可达，则证明这个对象不可能再被使用。　可作为GC Roots根节点的：在虚拟机栈（栈帧中的本地变量表）中引用的对象，譬如各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等在方法区中类静态属性引用的对象，譬如Java类的引用类型静态变量...

Java中使用TreeMap权重随机算法，以及验证与分析【代码】

权重下随机，就是给定各个值不同的权重，再根据权重的比例随机选出一个值 1/** 2 * Created by Jungle on 2020/2/23.3 *4 * @author JungleZhang5 * @version 1.0.06 * @Description 权重下随机的算法7*/ 8publicclass WeightRandom<K, V extends Number> {9private TreeMap<Double, K> weightMap = new TreeMap<>(); 1011public WeightRandom(@NotNull List<Pair<K, V>> list) { 12// 先排除权重为0的项13 Iterator<Pair<...

《数据结构与算法分析：C语言描述》复习——第六章“排序”——选择排序【代码】

2014.06.17 01:17简介：　　选择排序是一种O(n^2)级别的交换排序算法，属于新手必学算法。描述：　　个人觉得选择排序的代码是所有排序中最直观，最符合人类大脑思维的了。当我第一次有排序的需求时（初中时自学了一点C语言，算是人生第一次写代码），我自己试着写下的代码就是选择排序，当然我上了大学才知道“选择排序”是什么。很显然，直观且容易实现的算法基本都是最鹾的，而不直观且容易实现的算法基本都是最神的。很显然，选...

算法设计与分析(李春保)练习题答案v2

----------------------------------------------------- Page 1 -----------------------------------------------------1.1 第 1 章 ─ 概论 1.1.1 练习题 1. 下列关于算法的说法中正确的有（）。 Ⅰ . 求解某一类问题的算法是唯一的 Ⅱ . 算法必须在有限步操作之后停止 Ⅲ . 算法的每一步操作必须是明确的，不能有歧义或含义模糊 Ⅳ . 算法执行后一...

『嗨威说』算法设计与分析 - 算法第二章上机实践报告（二分查找 / 改写二分搜索算法 / 两个有序序列的中位数）【代码】【图】

本文索引目录：一、PTA实验报告题1 ：二分查找　　1.1　　实践题目　　1.2　　问题描述　　1.3　　算法描述　　1.4　　算法时间及空间复杂度分析二、PTA实验报告题2 ：改写二分搜索算法　　2.1　　实践题目　　2.2　　问题描述　　2.3　　算法描述　　2.4　　算法时间及空间复杂度分析三、PTA实验报告题3 ：两个有序序列的中位数　　3.1　　实践题目　　3.2　　问题描述　　3.3　　算法描述　　3.4　　算法时间及空间复杂度分析...

Pixhawk之姿态控制篇（1）_源码算法分析（超级有料）【图】

数据结构与算法之美专栏学习笔记-复杂度分析【代码】

复杂度分析什么是复杂度分析数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。为什么要进行复杂度分析和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。掌握复杂...

算法效率分析【图】

希望大家还是在实践当中感受效率，理解效率，写出高质量的代码和算法，仅仅作为参考，不要误导大家。排版尽量舒服吧，尽力了。一般而言分析算法效率的方式有两种，即：时间效率和空间效率。时间效率也称为时间复杂度；空间效率也称为空间复杂度。在计算机技术发展的几十年中，空间资源变得不是非常重要了，因此在一般的算法分析中，讨论的主要是时间复杂度，当然空间复杂度的分析也是如此。在算法分析中，我们不使用时间的标准单位...

寒假 8 （算法分析和递归，一些例子）

数据结构书前两章。附：递归的四个法则base cases；making progress；design rule; compound interest rule 算法里面的大小o不是高阶无穷的意思，就是说当n很大时，a比b小，也就是说，a的增长率小只定义了小，大，相等，严格小，用到的一般只有小有些递归和for循环等价，有些递归不可以改写成for循环算法分析，时间——语句——从最深层处开始计算，函数调用要展开，递归要展开计算任何事情不要超过一次：不要重复。 max sub...

10种排序算法分析【代码】【图】

10种排序算法，分别是直接插入排序，折半插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，树形排序，堆排序，归并排序，基数排序。各有千秋，但依旧有优劣之分，熟悉每一个算法，对于我们的代码优化，也将事半功倍。 1，直接插入排序：基本思想：假设待排的n个记录存放在变量R中，首先将R[1]看做是有序区，将后n - 1个数组元素看作是无序区；然后将无序区的第一个元素R[2]插入到前面有序区的适当位置，从而得到新的有序区R...

3.4 网页分析算法

在搜索引擎中，爬虫爬取了对应的网页之后，会将网页存储到服务器的原始数据库中，之后搜索引擎会对这些网页进行分析并确定各网页的重要性，即会影响用户的检索的排名结果。对于这些重要性的确定及排名结果的确定需要算法来解决，所以先来了解一下算法。搜索引擎的网页分析算法主要分为3类：基于用户行为的网页分析算法、基于网络拓扑的网页分析算法、基于网页内容的网页分析算法。接下来我们分别对这些算法进行讲解。搜索引擎的网页...

Python 实现关联规则分析Apriori算法【代码】【图】

# -*- coding:utf-8 -*-import sysreload(sys) sys.setdefaultencoding("utf8")def load_data_set():data_set = [[‘beer‘, ‘baby diapers‘, ‘shorts‘], [‘baby diapers‘, ‘shorts‘], [‘baby diapers‘, ‘milk‘], [‘beer‘, ‘baby diapers‘, ‘shorts‘], [‘beer‘, ‘milk‘], [‘baby diapers‘, ‘milk‘], [‘beer‘, ‘milk‘], [‘beer‘, ‘baby diapers‘, ‘milk‘, ‘shorts‘], [‘beer‘, ‘baby diap...

算法分析 - 相关标签

算法分析算法分析与设计

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 2020年09月 HNUCM-OJ算法分析与设计作业7

2020年09月 HNUCM-OJ算法分析与设计作业7

内容导读

内容图文

HNUCM-OJ 归并排序，大整数乘法，第k小元素问题，第k大元素问题，前m大数，找中位数

问题 A: 归并排序

问题 B: 大整数乘法

问题 C: 第k小元素问题

问题 D: 第k大元素问题

问题 E: 前m大数

问题 F: 找中位数

内容总结

内容备注

内容手机端

【2020年09月 HNUCM-OJ算法分析与设计作业7】教程文章相关的互联网学习教程文章

算法分析 - 相关标签

算法 - 最新教程

算法 - 最热教程