精华内容
下载资源
问答
  • 第七章 分治算法 所谓分治就是指的分而治之即将较大规模的问题分解成几个较小规模 的问题通过对较小规模问题的求解达到对整个问题的求解当我们将问题分 解成两个较小问题求解时的分治方法称之为二分法 分治的基本...
  • 分治算法 芯片测试.py

    2020-04-14 17:55:22
    芯片测试:蛮力测试和分治策略都有写到,算法按设计与分析课的笔记,博主自己写的,仅仅参考了讲义的伪代码,若有错误请指出,谢谢。 重要的假设:好芯片至少比坏芯片多一片。 测试结果:奇数个芯片√ 偶数个芯片...
  • 二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
  • 递归与分治算法练习

    2020-12-22 08:10:15
    一道关于递归与分治算法的练习题如下: 刚拿到题目觉得这题目似乎和递归分治没有什么关系,但是O(1)的空间复杂度,以及O(n)的时间复杂度度就限制了解决方法,也就是分治和递归。(使用python语言只需几行,用切片...
  • 分治算法

    2019-04-09 01:16:42
    NULL 博文链接:https://128kj.iteye.com/blog/1628818
  • 主要介绍了Java基于分治算法实现的线性时间选择操作,涉及java排序、比较、计算等相关操作技巧,需要的朋友可以参考下
  • 分治算法的典型例题

    2018-01-28 13:31:01
    第K小数,快速幂,下载之后负责答疑哦 int cmp(int x,int y) { return x; } void Swap() { swap(a[i],a[j]); swap(i,j); } void Operation(int START,int END) { i=START; j=END; while(i!...}
  • 实验 1 递归与分治算法 一实验目的和要求 1进一步掌握递归算法的设计思想以及递归程序的调试技术 2理解这样一个观点分治与递归经常同时应用在算法设计之中 3分别用蛮力法和分治法求解最近对问题 4分析算法的时间性能...
  • 自己写的分治算法,也包括了暴力求解的部分,并比较两者的运行时间,输出最大子数组的起始位置
  • 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。
  • 分治算法详解

    2018-11-21 15:12:23
    该课件讲述了分治算法的基本思想,并利用分治思想完成了对数组的排序,快速排序,数组选top k问题,讲解相邻点对的解决方案。
  • 18级学姐自主完成的算法作业,呕心沥血,基于四舍五入等于0基础的python实现,如果在语言规范上存在不足,那就。就憋着!哈哈哈哈哈,代码仅供参考,自己亲自码代码更酸爽!
  • %mergesort 分治算法——归并排序 %divide——将数组一分为二 %conquer——对两部分数组分别排序 %combine——将各自排好序的数组融合 %以此类推递归调用
  • C语言分治算法求解30枚银币中的某枚假币,简单而言,30枚银币中有1枚假币,该假币的重量比其他29枚银币的重量小1,先将30枚银币平分成两部分,各15枚,分别称重,重量小的那一半银币中必然包含假币,然后再分成两...
  • 算法设计与分析 分治法——归并排序 归并排序操作过程: def mergesort(seq): #归并排序 if len(seq) <= 1: return seq mid = int(len(seq) / 2) # 将列表分成更小的两个列表 # 分别对左右两个列表进行处理...
  • %divide——将数组分成两段 %conquer——每段分别求最大字段和 %combine——最大子段和无非三种情况:左端、右端、横跨中间 %每段分别求最大子段和的时候采用递归调用
  • 分治算法在循环赛赛程分配中的应用算法设计与分析 分治算法 循环赛事
  • 分治算法C程序

    2015-07-27 19:18:28
    对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,...这种算法设计策略叫做分治法。
  • 利用字符串和分治法来实现大整数乘法,内含c++源代码和实验报告说明
  • 分治算法PPt

    2018-09-17 14:39:33
    分治算法简介,专门对信息学C++语言算法课件让参加NOIP
  • 实验_邮局选址问题-分治算法
  • 分治算法 在树的路径问题中的应用 长沙市雅礼中学漆子超 树的路径问题 以路径为询问对象的题目 POJ1741,树中点对统计 SPOJ QTREE. FTOUR2,QTREE4 Astar2008复赛黑白树 论文内容 树的分治算法 树的分治的两种常见形式...
  • 维诺图的运算生成。又叫泰森多边形或Dirichlet图,它是由一组由连接两邻点直线的垂直平分线组成的连续多边形组成。
  • c语言分治算法

    2012-12-29 20:35:29
    c语言分治算法, 希望对大家有好的帮助。
  • 快速排序,使用分治算法,绝对AC,使用C++算法,没有使用sort,时间复杂度O(n logn)
  • 五大常用经典算法—分治算法

    千次阅读 多人点赞 2021-03-12 10:23:43
    分治算法(divide and conquer)是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一,很多人在平时学习中可能只是知道分治算法,但是可能并没有系统的学习分治算法,本篇就带你较为全面的去...

    原文作者:bigsai

    原文地址:五大常用算法:一文搞懂分治算法

    目录

    前言

    分治算法介绍

    分治算法经典问题

    二分搜索

    快速排序

    归并排序(逆序数)

    最大子序列和

    最近点对

    结语


    前言

    分治算法(divide and conquer)是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一,很多人在平时学习中可能只是知道分治算法,但是可能并没有系统的学习分治算法,本篇就带你较为全面的去认识和了解分治算法。在学习分治算法之前,问你一个问题,相信大家小时候都有存钱罐的经历,父母亲人如果给钱都会往自己的宝藏中存钱,我们每隔一段时间都会清点清点钱。但是一堆钱让你处理起来你可能觉得很复杂,因为数据相对于大脑有点庞大了,并且很容易算错,你可能会将它先分成几个小份算,然后再叠加起来计算总和就获得这堆钱的总数了

    image-20201130124009617

    当然如果你觉得各个部分钱数量还是太大,你依然可以进行划分然后合并,我们之所以这么多是因为:

    • 计算每个小堆钱的方式和计算最大堆钱的方式是相同的(区别在于体量上)
    • 然后大堆钱总和其实就是小堆钱结果之和。这样其实就有一种分治的思想。

    当然这些钱都是想出来的……

    BACDB95DF648E67CF0576A009697EBD2

    分治算法介绍

    分治算法是用了分治思想的一种算法,什么是分治?分治,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。在计算机科学中,分治法就是运用分治思想的一种很重要的算法。分治法是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)等等。将父问题分解为子问题同等方式求解,这和递归的概念很吻合,所以在分治算法通常以递归的方式实现(当然也有非递归的实现方式)。分治算法的描述从字面上也很容易理解,分、治其实还有个合并的过程:

    • 分(Divide):递归解决较小的问题(到终止层或者可以解决的时候停下)
    • 治(Conquer):递归求解,如果问题够小直接求解。
    • 合并(Combine):将子问题的解构建父类问题

    一般分治算法在正文中分解为两个即以上的递归调用,并且子类问题一般是不想交的(互不影响)。当求解一个问题规模很大很难直接求解,但是规模较小的时候问题很容易求解并且这个问题并且问题满足分治算法的适用条件,那么就可以使用分治算法。

    image-20201130165303362

    那么采用分治算法解决的问题需要 满足那些条件(特征) 呢?

    • 1 . 原问题规模通常比较大,不易直接解决,但问题缩小到一定程度就能较容易的解决。
    • 2 . 问题可以分解为若干规模较小、求解方式相同(似)的子问题。且子问题之间求解是独立的互不影响。
    • 3 . 合并问题分解的子问题可以得到问题的解。

    你可能会疑惑分治算法和递归有什么关系?其实分治重要的是一种思想,注重的是问题分、治、合并的过程。而递归是一种方式(工具),这种方式通过方法自己调用自己形成一个来回的过程,而分治可能就是利用了多次这样的来回过程

    分治算法经典问题

    对于分治算法的经典问题,重要的是其思想,因为我们大部分借助递归去实现,所以在代码实现上大部分都是很简单,而本篇也重在讲述思想。分治算法的经典问题,个人将它分成两大类:子问题完全独立和子问题不完全独立。

    • 1 . 子问题完全独立就是原问题的答案可完全由子问题的结果推出。
    • 2 . 子问题不完全独立,有些区间类的问题或者跨区间问题使用分治可能结果跨区间,在考虑问题的时候需要仔细借鉴下。

    二分搜索

    二分搜索是分治的一个实例,只不过二分搜索有着自己的特殊性

    • 序列有序
    • 结果为一个值

    正常二分将一个完整的区间分成两个区间,两个区间本应单独找值然后确认结果,但是通过有序的区间可以直接确定结果在那个区间,所以分的两个区间只需要计算其中一个区间,然后继续进行一直到结束。实现方式有递归和非递归,但是非递归用的更多一些:

    public int searchInsert(int[] nums, int target) {
      if(nums[0]>=target)return 0;//剪枝
      if(nums[nums.length-1]==target)return nums.length-1;//剪枝
      if(nums[nums.length-1]<target)return nums.length;
      int left=0,right=nums.length-1;
      while (left<right) {
        int mid=(left+right)/2;
        if(nums[mid]==target)
          return mid;
        else if (nums[mid]>target) {
          right=mid;
        }
        else {
          left=mid+1;
        }
      }
      return left;
    }
    

    时间复杂度:比如总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。 由于n/2^k取整后>=1,即令n/2^k=1, 可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O()=O(logn)

    快速排序

    快排也是分治的一个实例,快排每一趟会选定一个数,将比这个数小的放左面,比这个数大的放右面,然后递归分治求解两个子区间,当然快排因为在分的时候就做了很多工作,当全部分到最底层的时候这个序列的值就是排序完的值。这是一种分而治之的体现。

    image-20201120133851275

    public void quicksort(int [] a,int left,int right)
    {
      int low=left;
      int high=right;
      //下面两句的顺序一定不能混,否则会产生数组越界!!!very important!!!
      if(low>high)//作为判断是否截止条件
        return;
      int k=a[low];//额外空间k,取最左侧的一个作为衡量,最后要求左侧都比它小,右侧都比它大。
      while(low<high)//这一轮要求把左侧小于a[low],右侧大于a[low]。
      {
        while(low<high&&a[high]>=k)//右侧找到第一个小于k的停止
        {
          high--;
        }
        //这样就找到第一个比它小的了
        a[low]=a[high];//放到low位置
        while(low<high&&a[low]<=k)//在low往右找到第一个大于k的,放到右侧a[high]位置
        {
          low++;
        }
        a[high]=a[low];			
      }
      a[low]=k;//赋值然后左右递归分治求之
      quicksort(a, left, low-1);
      quicksort(a, low+1, right);		
    }
    
    

    归并排序(逆序数)

    快排在分的时候做了很多工作,而归并就是相反,归并在分的时候按照数量均匀分,而合并时候已经是两两有序的进行合并的,因为两个有序序列O(n)级别的复杂度即可得到需要的结果。而逆序数在归并排序基础上变形同样也是分治思想求解。

    image-20201120173153449

    private static void mergesort(int[] array, int left, int right) {
      int mid=(left+right)/2;
      if(left<right)
      {
        mergesort(array, left, mid);
        mergesort(array, mid+1, right);
        merge(array, left,mid, right);
      }
    }
    
    private static void merge(int[] array, int l, int mid, int r) {
      int lindex=l;int rindex=mid+1;
      int team[]=new int[r-l+1];
      int teamindex=0;
      while (lindex<=mid&&rindex<=r) {//先左右比较合并
        if(array[lindex]<=array[rindex])
        {
          team[teamindex++]=array[lindex++];
        }
        else {				
          team[teamindex++]=array[rindex++];
        }
      }
      while(lindex<=mid)//当一个越界后剩余按序列添加即可
      {
        team[teamindex++]=array[lindex++];
    
      }
      while(rindex<=r)
      {
        team[teamindex++]=array[rindex++];
      }	
      for(int i=0;i<teamindex;i++)
      {
        array[l+i]=team[i];
      }
    }
    

    最近点对

    最近点对是一个分治非常成功的运用之一。在二维坐标轴上有若干个点坐标,让你求出最近的两个点的距离,如果让你直接求那么枚举暴力是个非常非常大的计算量,我们通常采用分治的方法来优化这种问题。

    image-20201130204401673

    如果直接分成两部分分治计算你肯定会发现如果最短的如果一个在左一个在右会出现问题。我们可以优化一下。在具体的优化方案上,按照x或者y的维度进行考虑,将数据分成两个区域,先分别计算(按照同方法)左右区域内最短的点对。然后根据这个两个中较短的距离向左和向右覆盖,计算被覆盖的左右点之间的距离,找到最小那个距离与当前最短距离比较即可。

    image-20201130205950625

    这样你就可以发现就这个一次的操作(不考虑子情况),左侧红点就避免和右侧大部分红点进行距离计算(O(n2)的时间复杂度)。事实上,在进行左右区间内部计算的时候,它其实也这样递归的进行很多次分治计算。如图所示:

    image-20201130210925059

    这样下去就可以节省很多次的计算量。但是这种分治会存在一种问题就是二维坐标可能点都聚集某个方法某条轴那么可能效果并不明显(点都在x=2附近对x分割作用就不大),需要注意一下。杭电1007推荐给大家,ac的代码为:

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.OutputStreamWriter;
    import java.io.PrintWriter;
    import java.io.StreamTokenizer;
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.List;
    public class Main {
        static int n;
        public static void main(String[] args) throws IOException {
            StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
            //List<node>list=new ArrayList();
             while(in.nextToken()!=StreamTokenizer.TT_EOF)
             {
                 n=(int)in.nval;if(n==0) {break;}
                node no[]=new node[n];
                
                 for(int i=0;i<n;i++)
                 {
                     in.nextToken();double x=in.nval;
                     in.nextToken();double y=in.nval;
                    // list.add(new node(x,y));
                     no[i]=new node(x,y);
                 }
                 Arrays.sort(no, com);
                double min= search(no,0,n-1);
                out.println(String.format("%.2f", Math.sqrt(min)/2));out.flush();
             }         
        }
        private static double search(node[] no, int left,int right) {
            int mid=(right+left)/2;
            double minleng=0;
            if(left==right) {return Double.MAX_VALUE;}
            else if(left+1==right) {minleng= (no[left].x-no[right].x)*(no[left].x-no[right].x)+(no[left].y-no[right].y)*(no[left].y-no[right].y);}
            else minleng= min(search(no,left,mid),search(no,mid,right));
            int ll=mid;int rr=mid+1;
            while(no[mid].y-no[ll].y<=Math.sqrt(minleng)/2&&ll-1>=left) {ll--;}
            while(no[rr].y-no[mid].y<=Math.sqrt(minleng)/2&&rr+1<=right) {rr++;}
            for(int i=ll;i<rr;i++)
            {
                for(int j=i+1;j<rr+1;j++)
                {
                    double team=0;
                    if(Math.abs((no[i].x-no[j].x)*(no[i].x-no[j].x))>minleng) {continue;}
                    else
                    { 
                        team=(no[i].x-no[j].x)*(no[i].x-no[j].x)+(no[i].y-no[j].y)*(no[i].y-no[j].y);
                        if(team<minleng)minleng=team;
                    }
                }
            }
            return minleng;
        
        }
        private static double min(double a, double b) {
            // TODO 自动生成的方法存根
            return a<b?a:b;
        }
        static Comparator<node>com=new Comparator<node>() {
    
            @Override
            public int compare(node a1, node a2) {
                // TODO 自动生成的方法存根
                return a1.y-a2.y>0?1:-1;
            }};
        static class node
        {
            double x;
            double y;
            public node(double x,double y)
            {
                this.x=x;
                this.y=y;
            }
        }
    }
    
    

    结语

    到这里,分治算法就讲这么多了,因为分治算法重要在于理解其思想,还有一些典型的分治算法解决的问题,例如大整数乘法、Strassen矩阵乘法、棋盘覆盖、线性时间选择、循环赛日程表、汉诺塔等问题你可以自己研究其分治的思想和原理。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 86,011
精华内容 34,404
关键字:

分治算法