精华内容
下载资源
问答
  • 分治算法经典例子
    2020-08-12 16:54:13

    分治算法

    思想

    当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。

    分治法解题步骤

    (1)分解,将要解决的问题划分成若干规模较小的同类问题;
    (2)求解,当子问题划分得足够小时,用较简单的方法解决;
    (3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。

    分治算法经典——汉诺塔

    汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

    汉诺塔Java实现
    package dac;
    
    public class HanoiTower {
        public static void main(String[] args) {
            //分治算法的汉诺塔问题
            hanoiTower(5,'A','B','C');
        }
    
        /**
         * @param num 一共有多少个盘
         * @param a   a塔
         * @param b   b塔
         * @param c   c塔
         */
        public static void hanoiTower(int num, char a, char b, char c) {
            //如果只有一个盘,从a移动到c
            if (num == 1) {
                System.out.println("第1个盘从 " + a + "——>" + c);
            } else {
                //如果有n>=2个盘,应该看成只有两个盘,将最下面的一个盘和上面的所有盘分开看待。
                //先把最上面的所有盘a——>b,移动过程会使用到c
                hanoiTower(num - 1, a, c, b);
                //把最下面的盘从a——>c
                System.out.println("第" + num + "个盘从 " + a + "——>" + c);
                //把B塔的所有盘从b——>c,移动过程会使用到a塔
                hanoiTower(num-1, b, a, c);
            }
        }
    }
    
    运行结果
    第1个盘从 A——>C
    第2个盘从 A——>B
    第1个盘从 C——>B
    第3个盘从 A——>C
    第1个盘从 B——>A
    第2个盘从 B——>C
    第1个盘从 A——>C
    第4个盘从 A——>B
    第1个盘从 C——>B
    第2个盘从 C——>A
    第1个盘从 B——>A
    第3个盘从 C——>B
    第1个盘从 A——>C
    第2个盘从 A——>B
    第1个盘从 C——>B
    第5个盘从 A——>C
    第1个盘从 B——>A
    第2个盘从 B——>C
    第1个盘从 A——>C
    第3个盘从 B——>A
    第1个盘从 C——>B
    第2个盘从 C——>A
    第1个盘从 B——>A
    第4个盘从 B——>C
    第1个盘从 A——>C
    第2个盘从 A——>B
    第1个盘从 C——>B
    第3个盘从 A——>C
    第1个盘从 B——>A
    第2个盘从 B——>C
    第1个盘从 A——>C
    
    Process finished with exit code 0
    
    
    更多相关内容
  • 分治算法与典型例题

    2022-05-05 13:40:12
    分治算法设计思路与一些典型应用,包括归并排序、快速排序

    目录

    前言

    一、分治算法要素(条件)

    二、分治算法设计步骤

    三、时间复杂度求解

    四、典型例题1——归并排序

    五、典型例题2——快速排序

    总结

     


    前言

              在算法设计中,引入分而治之的策略,称为分治算法。其本质是将大规模问题分解为若干个规模较小的相同子问题,分而治之。举出两个典型例子,这里只放伪代码,具体内容可以参看《趣学算法》。


    一、分治算法要素(条件)

            1.原问题可以分解为若干个规模较小的相同子问题。

            2.子问题相互独立。

            3.子问题的解可以合并为原问题的解。

    二、分治算法设计步骤

            一般步骤如下:

            1.分解,将要解决的问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。

            2.治理,求解各个子问题。由于子问题与原问题形式相同,只是规模较小,当规模足够小时,就可以用较简单的方法解决。

            3.合并,按原问题要求,将子问题的解逐层合并构成原问题的解。

            分治算法中,各个子问题形式相同,解决方法一样,因此可以用递归算法快速解决。

    三、时间复杂度求解

            主要有三种方法,递推式法、递归树法和通式法。这里主要讲通式法。

    通式法:

            用T(n)表示分治法解决规模为n的问题所需要的时间,

    T(n)=aT(n/b)+f(n)

    f(n)=O(n^d)

            可以用递推树法证明,

    T(n)=\left\{\begin{matrix} O(n^d) , a/b^d < 1 \\ O(n^{\log_b a}), a/b^d > 1 \\ O(n^d\log_b n), a/b^d = 1 \end{matrix}\right.

            例,求解下式的时间复杂度,(一般情况下快速排序时间复杂度)

    T(n)=2T(n/2)+O(n)

            a=2, b=2, d=1, a/b^d=1, 则T(n)=O(n^d\log_b n)=O(n\log n)

    四、典型例题1——归并排序

    伪代码

    void Merge(int A[], int low, int mid, int high)
    {
        //申请一个辅助数组,归并排序是异地稳定排序
        int *B = new int [high-low+1];
        int i = low, j = mid + 1, k = 0;
        while(i <= mid && j <= high)
        {
            //从小到大把数据存入B[]
            if(A[i] <= A[j])
                B[k++] = A[i++];
            else
                B[k++] = A[j++];
        }
        while(i <= mid) B[k++] = A[i++];//处理剩余A[low, mid]
        while(j <= high) B[k++] = A[j++];//处理剩余A[mid+1, high]
        for(i = low, k = 0; i <= high; i++)
        {
            A[i] = B[k++];
        }
    }
    
    void MergeSort(int A[], int low, int high)
    {
        if(low < high)
        {
            int mid = (low+high)/2;
            MergeSort(A, low, mid);
            MergeSort(A, mid+1, high);
            Merge(A, low, mid, high);
        }
    }
    

            时间复杂度O(n \log n)

    五、典型例题2——快速排序

    伪代码

    int Partition(int r[], int low, int high)
    {
        int i = low, j = high, pivot = r[low];//基准元素取第一个,也有首元素,尾元素,中间元素三者取中值
        while(i < j)
        {
            while(i < j && r[j] > pivot) j--;//向左扫描
            if(i < j) swap(r[i++], r[j]);//交换i,j,并且i右移一位
            
            //反向过程
            while(i < j && r[i] <= pivot) i++;//向右扫描
            if(i < j) swap(r[i], r[j--]);//交换i,j,并且j左移一位
        }
        //找到pivot的位置并返回
        return i;
    }
    
    void QuickSort(int R[], int low, int high)
    {
        if(low < high)
        {
            int mid = Partition(R, low, high);
            QuickSort(R, low, mid-1);
            QuickSort(R, mid+1, high);
        }
    }

            快速排序本地不稳定排序,性能不一定比归并排序好,一般情况下时间复杂度O(n\log n),最差情况下时间复杂度O(n^2)。STL中的sort()函数融合多种排序算法,快速排序不一定最佳,需看具体情况。


    总结

            分治算法最大优势可以使用递归程序实现,编程简单,但是分解、治理过程有很大技巧,不易掌握。这里例1主要难在合并过程,例2难在分解过程,这两类程序框架可以不止用于排序算法。

    展开全文
  • 一、【分治算法】简介 1.基本思想:”分而治之“,将一个复杂问题分解成两个或多个相同或相似的子问题,再把子问题分解成更小的子问题…直到最后子问题可以简单的直接求解,原问题的解即为所有子问题的解的合并。 2....

    学习网站推荐:前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站

    【分治算法】<上篇>


    一、算法思想简介

    1.基本思想:”分而治之“,将一个复杂问题分解成两个或多个相同或相似的子问题,再把子问题分解成更小的子问题…直到最后子问题可以简单的直接求解,原问题的解即为所有子问题的解的合并。

    2.经典例子:

    • 汉诺塔
    • 二分查找(递归版)
    • 归并排序(递归版)
    • 快速排序(递归版)

    二、经典例子的代码实现

    1.汉诺塔:

    • 目标:将所有盘子从A柱移动到C柱,同一根柱子在任何时候不允许出现上面的某个盘子大于下面的某个盘子的情况。
    • 基本思想(图解):将A柱的n个盘子全部移动到C柱,可先将A柱的前n-1个盘子移动到B柱子,再将第n个盘子移到C柱,再将B柱的n-1个盘子移到C柱。
      在这里插入图片描述
    • 代码实现
    public class Hanoitower {
    
        public static void main(String[] args) {
            hanoiTower(3, 'A', 'B', 'C');
        }
    
        private static void hanoiTower(int num, char a, char b, char c) {
            //如果只有一个盘子
            if (num == 1) {
                System.out.println("第1个盘子从" + a + "->" + c);
            } else { //如果有n>=2个,可抽象成两个盘,一个是最下面的一个盘,另一个是上面的所有盘
                //将上面的盘从A->B
                hanoiTower(num - 1, a, c, b);
                //移动最下面的盘从A->C
                System.out.println("第" + num + "个盘从" + a + "->" + c);
                //将上面的盘从B->C
                hanoiTower(num - 1, b, a, c);
            }
        }
    
    }
    

    2.二分查找(递归版):

    • 目标:在有序表查找某值是否存在。

    • 基本思想(图解)
      在这里插入图片描述

    • 代码实现

    public class BinarySearch {
    
        public static void main(String[] args) {
            int[] a = {1, 2, 3, 4, 5};
            System.out.println(search(a, 1));
            System.out.println(search(a, 3));
            System.out.println(search(a, 5));
            System.out.println(search(a, 9));
        }
    
        public static boolean search(int[] a, int key) {
            return inSearch(a, 0, a.length - 1, key);
        }
    
        private static boolean inSearch(int[] a, int low, int high, int key) {
            int mid;
            while (low <= high) {
                mid = (low + high) / 2;
                if (key == a[mid]) {
                    return true;
                } else if (key < a[mid]) {
                    return inSearch(a, 0, mid - 1, key);
                } else {
                    return inSearch(a, mid + 1, high, key);
                }
            }
            return false;
        }
    
    }
    

    3.归并排序(递归版):

    • 目标:使序列有序。

    • 基本思想(图解):初始序列含有n个元素,则可看成是n个有序子序列,每个子序列的长度为1,然后两两归并,得到Math.ceil(n/2)个长度为2或1的有序子序列;再两两归并,…,如此重复,直到得到一个长度为n的有序序列位置。
      在这里插入图片描述

    • 代码实现

    public class MergeSort {
    
        public static void sort(int[] a) {
            int n = a.length - 1;
            MSort(a, a, 1, n);
        }
    
        //将SR[s..n]归并为有序的TR1[s..n]
        private static void MSort(int[] SR, int[] TR1, int s, int n) {
            int m;
            int[] TR2 = new int[n + 1]; // SR, TR1, TR2等长
            if (s == n) {
                TR1[s] = SR[s];
            } else {
                m = (s + n) / 2; // 将SR[s..n]平均分为SR[s..m]和SR[m+1..n]
                MSort(SR, TR2, s, m); // 递归将SR[s..m]归并为有序的TR2[s..m]
                MSort(SR, TR2, m + 1, n); // 递归将SR[m+1..n]归并为有序的TR2[m+1..n]
                Merge(TR2, TR1, s, m, n); // 将TR2[s..m]和TR2[m+1..n]归并到TR1[s..n]
            }
        }
    
        // 将有序的SR[s..m]和SR[m+1..n]归并为有序的TR[i..n]
        private static void Merge(int[] SR, int[] TR, int s, int m, int n) {
            int j, k, l; // k为左块的起始下标,j为右块的起始下标
            for (k = s, j = m + 1; s <= m && j <= n; k++) { //SR中记录由小到大归并入TR
                if (SR[s] < SR[j]) {
                    TR[k] = SR[s++];
                } else {
                    TR[k] = SR[j++];
                }
            }
            if (s <= m) {
                for (l = 0; l <= m - s; l++) {
                    TR[k + l] = SR[s + l]; // 将剩余的SR[s..m]复制到TR
                }
            }
            if (j <= n) {
                for (l = 0; l <= n - j; l++) {
                    TR[k + l] = SR[j + l]; // 将剩余的SR[j..m]复制到TR
                }
            }
        }
    
    }
    

    4.快速排序(递归版):

    • 目标:使序列有序。

    • 基本思想:通过一趟排序将待排序记录分割成独立的两部分,其中每一部分记录的关键字均比另一部分记录的关键字小,则可以分别对着两部分记录继续进行排序,以达到整个序列有序的目的。

    • 代码实现

    public class QuickSort {
    
        public static void sort(int[] a) {
            int n = a.length - 1;
            QSort(a, 1, n);
        }
    
        private static void QSort(int[] a, int low, int high) {
            int pivot; // 枢轴的下标,将某个数放在此位置,使得它左边的值都比它小,右边的都比它大
            if (low < high) {
                pivot = Partition(a, low, high); // 将a[low..high]一分为二,算出枢轴下标pivot
                QSort(a, low, pivot - 1); // 对低子表递归排序
                QSort(a, pivot + 1, high); // 对高子表递归排序
            }
        }
    
        // 交换顺序表a中子表的记录,使枢轴记录到为,并返回其位置
        private static int Partition(int[] a, int low, int high) {
            int pivotkey = a[low]; // 用子表的第一个记录作枢轴记录
            while (low < high) { // 从表的两端交替向中间扫描
                while (low < high && a[high] >= pivotkey) {
                    high--;
                }
                swap(a, low, high); // 将比枢轴值小的记录交换到低端
                while (low < high && a[low] <= pivotkey) {
                    low++;
                }
                swap(a, low, high); // 将比枢轴值大的记录交换到高端
            }
            return low; // 最终low == high,所有返回枢轴所在位置
        }
    
        private static void swap(int[] a, int x, int y) {
            int temp;
            temp = a[x];
            a[x] = a[y];
            a[y] = temp;
        }
    
    }
    

    请添加图片描述

    展开全文
  • 二 算法设计 快速排序是基于分治策略的,其算法思想如下。 1 分解 先从数列中取出一个元素作为基准元素。以基准元素为标准,将问题分解为两个子序列,使小于或等于基准元素的子序列在左侧,使大于基准元素的子...

    一 点睛

    快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据小,然后按此方法对这两部分分别进行快速排序,整个排序过程可以递归进行,以达到整个数据变成有序序列。

    合并排序每次都是从中间位置把问题一分为二,一直分解到不能再分时再进行合并操作。合并排序的划分很简单,但合并操作需要在辅助数组中完成,是一种异地排序的方法。合并排序分解容易、合并难,属于“先易后难”。而快速排序是原地排序,不需要辅助数组,但分解困难、合并容易,属于“先苦后甜”。

    二 算法设计

    快速排序是基于分治策略的,其算法思想如下。

    1 分解

    先从数列中取出一个元素作为基准元素。以基准元素为标准,将问题分解为两个子序列,使小于或等于基准元素的子序列在左侧,使大于基准元素的子序列在右侧。

    2 治理

    对两个子序列进行快速排序。

    3 合并

    将排好序的两个子序列合并在一起,得到原问题的解。

    三 对基准元素的选取

    • 一般有以下几种方法。
    • 取第一个元素
    • 取最后一个元素
    • 取中间位置元素
    • 取第一个元素,最后一个元素、中间位置的元素三者位置的中位数
    • 取第一个元素和最后一个元素之间位置的随机数 k (low <= k <= high),选第 k 个位置作为基准元素

    四 图解

    这里选取第一个元素作为基准。以说明快速排序的执行过程。

    1 取当前待排序的第一个元素作为基准元素 pivot = r[low],i = low,j = high。

    2 从右向左扫描,找小于或等于 pivot 的数,如果找到,则 r[i] 和 r[j] 交换,i++。

    3 从左向右扫描,找大于 pivot 的数,如果找到,则 则 r[i] 和 r[j] 交换,j--。

    4 重复第 2~3 步,直到 i 和 j 重合,将原数据分为两个子序列,左侧子序列都比 pivot 小,右侧序列都比 pivot 大。然后分别对这两个子序列进行快速排序。

    这里以序列(30,24,5,58,18,36,12,42,39)为例,演示快速排序过程。

    a 初始化

    i = low ,j = high,pivot = r[low] = 30。

    b 向左走

    从数组的右边向左找,一直找小于或等于 pivot 的数,找到 r[j] = 12。

    r[i] 和 r[j] 交换,i++。

    c 向右走

    从数组的左边向右找,一直找大于 pivot 的数,找到 r[i] = 58。

    r[i] 和 r[j] 交换,j--。

    d 向左走

    从数组的右边向左找,一直找小于或等于 pivot 的数,找到 r[j] = 18。

    r[i] 和 r[j] 交换,i++。

    e 向右走

    从数组的左边位置向右找,一直找比 pivot 大的数,此时 i = j,第一趟排序结束,返回 i 的位置,mid = i

    此时以 mid 为界,将原序列分为两个子序列,左侧子序列都比 pivot 小,右侧子序列都比 pivot 大。然后分别对两个子序列(12,24,5,18)、(36、58、42、39)进行快速排序。

    五 算法实现

    快速排序实战_实践求真知-CSDN博客icon-default.png?t=M1L8https://blog.csdn.net/chengqiuming/article/details/114705971

    展开全文
  • 分治算法经典案例——合并排序

    千次阅读 2022-02-26 10:47:52
    合并排序是采用分治策略进行排序的算法,是分治算法的一个典型应用和完美体现。它是一种平衡、简单的二分分治策略。 算法步骤如下。 1分解 将待排序元素分成大小大致相同的两个子序列。 2治理 对两个子序列进行...
  • 五大常用经典算法—分治算法

    千次阅读 多人点赞 2021-03-12 10:23:43
    分治算法经典问题 二分搜索 快速排序 归并排序(逆序数) 最大子序列和 最近点对 结语 前言 分治算法(divide and conquer)是五大常用算法(分治算法、动态规划算法、贪心算法、回溯法、分治界限法)之一,很多...
  • 分治算法思想及经典案例

    千次阅读 2020-02-20 22:03:27
    分治算法介绍 1)分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题...2)分治算法可以求解的一些经典问题 二分搜索 大整数乘法 棋盘覆盖 合并...
  • 分治算法详细讲解(含经典例题分析)

    万次阅读 多人点赞 2020-11-22 11:58:48
    分治算法可以由递归过程来表示,因为分治法就是一种找大规模问题与小规模问题关系的方法,是递归设计的一种具体策略。 步骤 1.分解 将原问题分解为若干规模较小,相互独立,与原问题相同的子问题。 2.解决 若干子...
  • 分治算法例子集锦

    万次阅读 多人点赞 2015-03-07 13:25:38
    分治算法例子集锦
  • 主要介绍了Java使用分治算法实现排序数索引功能,结合具体实例形式分析了java分治算法进行排序索引的相关操作技巧,需要的朋友可以参考下
  • 分治算法详解

    2022-01-19 12:11:04
    分治算法 实际场景中,我们之所以觉得有些问题很难解决,主要原因是该问题涉及到大量的数据,如果只需要处理少量的数据,问题会变得非常容易解决。 举一个简单的例子,设计一个排序算法实现对 1000 个整数进行排序。...
  • 例题 其实算法的思想不用讲太多,能够化为几句话是最好的,下面就举几个例子来看看分治算法: 例题一:二分查找,给定一个按照升序排好的数组array,要在这个数组中找出一个特定的元素x; 当我们遇到一个问题,完全...
  • 分治算法使用实例

    千次阅读 2021-11-29 16:31:30
    介绍分治算法,具有天然的递归性,通过汉诺塔和一道困难题来体会分治算法
  • 代表例子有快速排序和归并排序。 例题-所有可能的满二叉树 题目描述 所有可能的满二叉树 满二叉树是一类二叉树,其中每个结点恰好有 0 或 2 个子结点。 返回包含 N 个结点的所有可能满二叉树的列表。 答案的每个元素...
  • 分治算法原理: 分——将问题分解为规模更小的子问题; 治——将这些规模更小的子问题逐个击破; 合——将已解决的子问题合并,最终得出“母”问题的解; 分治法在具体操作时主要是以下两步: 1、找出最原始的...
  • C语言分治算法案例

    2021-11-04 12:00:55
    //分治算法:将原问题分解成若干个子问题、通过解决子问题最终解决原问题 int fenzhi(int a[],int zuo,int you) { int mid; int zmin,ymin; mid=(zuo+you)/2; if(zuo==you) { return a[zuo];//只有一个数,...
  • 2017-08-2620:18:50 writer:pprp 问题大概描述: 有一个2k∗2k的方格棋盘,恰有一...用分治法来解决,分治的时候要确定状态,需要什么状态,结束条件 结束条件是size规模变成了1的时候,就要退出了; 需要的状...
  • 2.Python算法之分治算法思想

    千次阅读 2020-10-13 22:26:48
    1.什么是分治算法分治算法就是对一个问题采取各个击破的方法,将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。只要求出子问题的解,就可得到原问题的解。 2.为什么...
  • 分治算法及例题解析

    千次阅读 2021-11-18 22:20:58
    分治算法及例题解析什么是分治思想分治法适用的情况分治法的基本步骤快速排序基本思想快速排序用到了分而治之的思想。将一个数组分成两个数组的方法为第一遍的过程如下全部排序过程如下Javascript实现快排归并排序...
  • 二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
  • 学 习a c m 分 治算法 的入门 教程简单易学acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法vacm分治算法acm...
  • 分治算法

    2020-09-22 21:32:12
    本文为自己的总结记录,参考博文分治算法总结很多。 算法思想及步骤 如字面意思,是“分而治之”。通常会用到递归。 对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k...
  • 递归思想和案列(阶乘函数,Fibonacci数列,Ackerman函数,整数划分问题,Hanoi塔问题)分治法思想的介绍(大整数的乘法,Strassen矩阵乘法,棋盘覆盖问题,二分搜索,快速排序,合并排序,线性时间选择)。算法课使用的ppt,可结合...
  • 分治算法经典例题 寻找假币

    万次阅读 2017-06-11 13:34:23
    一个袋子里有若干硬币,其中一枚是假币...请问如何区别:利用分治 算法的思想:import java.util.Scanner;public class Main { static final int MAXNUM = 30; private static int FalseCoin(int[] coin, int low, int
  • 首先,我们来复习一下分治算法的思想:将一个大的问题,分解成 若干个性质相同或相似的小的问题(最好是独立的),每一个小的问题是可以求解的。再将小的问题,合并成原的大的问题。 而为了解决一个给定的问题,...
  • 五大算法思想 分治算法介绍 二分搜索、大整数乘法、Strassen矩阵乘法、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表、汉诺塔
  • 二分查找基于分治算法的实现

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,855
精华内容 7,142
关键字:

分治算法经典例子