当前位置:  编程技术>c/c++/嵌入式

算法详解之分治法具体实现

    来源: 互联网  发布时间:2014-10-23

    本文导语:  分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。 分治法解题的一般步骤: (1)分解,将要解决的问题划分成若干...

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。

分治法解题的一般步骤:

(1)分解,将要解决的问题划分成若干规模较小的同类问题;

(2)求解,当子问题划分得足够小时,用较简单的方法解决;

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

一言以蔽之:分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

在认识分治之前很有必要先了解一下递归,当然,递归也是最基本的编程问题,一般接触过编程的人都会对递归有一些认识.为什么要先了解递归呢?你看,根据上面所说的,我们就要将一个问题分成若干个小问题,然后一一求解并且最后合并,这就是一个递归的问题,递归的去分解自身,递归的去解决每一个小问题,然后合并…

关于递归,这里举一个最简单的例子,求N!;

我们只需要定义函数

代码如下:

int calculate(int n)

{

if(n==1)

return 1;

else

  return n*calculate(n-1);   //调用自身…

}

好了,有了递归的铺垫,我们下来来看一看一个分治算法的问题,归并排序问题…

基本思想:

将待排序元素分成大小大致相同的2个子集合(递归直到最小的排序单元),分别对2个子集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合。

下面我们用一张图来展示整个流程,最下面的(姑且叫他第一层)是原始数组分成了8个最小排序问题,各自只有一个元素,故不需要排序,大家可以看到,我们通过分而治之的思想把对最初数组的排序分为了若干个只有一个元素的小数组的排序,然后第二层,我们进行了合并,将每两个最小排序结果合并为有两个元素的数组,然后逐层往上进行合并,就有了最后的结果…

下面我们来看一下这个算法的具体实现,下面的MERGE-SORT (A, p, r)表示对数组A[p->r]的排序过程.其中p->r代表从p到r.

MERGE-SORT (A, p, r)

1.     IF p < r                                                    // 进行A[p->r]的排序过程自然需要pq]的排序

4.                 MERGE-SORT (A, q + 1, r)          // 继续递归看能不能将问题继续一分为二处理A[q+1->r]的排序

5.                 MERGE (A, p, q, r)                       // 合并当前结果

到这里,分治算法的精髓已经出来了,我们通过递归将问题进行分解到足够小…继而进行结果计算…然后再将结果合并.

下面来处理一下边角料的工作,呵呵,让大家看到一个完整的归并排序的例子,整个算法总结系列我都没有很好的使用伪代码,而是使用我认为广泛使用的C语言代码来进行代码诠释.实际上,描述算法最好还是使用伪代码比较好,这里我对我前面的四篇文章没有使用伪代码而小小的鄙视一下自己,太不专业了..呵呵

以下算法MERGE (A, p, q, r )表示合并A[p->q]和A[q+1->r]这两个已经排序好的数组

MERGE (A, p, q, r )

1.      n1 ← q − p + 1                                                          //计算A[p->q]的长度
2.      n2 ← r − q                                                                //计算A[q+1->r]的长度
3.      Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]       //创建两个数组
4.      FOR i ← 1 TO n1
5.            DO L[i] ← A[p + i − 1]
6.      FOR j ← 1 TO n2
7.            DO R[j] ← A[q + j ]        //4-7行是将原数组中A[p->r]的元素取出到新创建的数组,我们的操作是基于临时数组的操作
8.      L[n1 + 1] ← ∞
9.      R[n2 + 1] ← ∞                   //8-9行设置界限..
10.    i ← 1
11.    j ← 1
12.    FOR k ← p TO r
13.         DO IF L[i ] ≤ R[ j]
14.                THEN A[k] ← L[i]
15.                        i ← i + 1
16.                ELSE A[k] ← R[j]
17.                        j ← j + 1                //12-17行进行排序合

这里我还是提供一个具体的实现,请见下面的代码

C语言代码

关于代码注释,请见博客上面的伪代码注释..

代码如下:

#include
int L[100],R[100];
void merge(int numbers[],int left, int mid, int right)
        {
            int n1=mid-left+1;
            int n2=right-mid;
            int i,j,k;
            for(i=1;i

    
 
 

您可能感兴趣的文章:

  • 一种求正整数幂的高效算法详解
  • 深入串的模式匹配算法(普通算法和KMP算法)的详解
  • 解析C#彩色图像灰度化算法的实现代码详解
  • 使用Deflate算法对文件进行压缩与解压缩的方法详解
  • 深入第K大数问题以及算法概要的详解
  • 字符串的模式匹配详解--BF算法与KMP算法
  • 算法之排列算法与组合算法详解
  • 采用C++实现区间图着色问题(贪心算法)实例详解
  • C语言位图算法详解
  • 算法详解之回溯法具体实现
  • 基于一致性hash算法(consistent hashing)的使用详解
  • 算法详解之分支限界法的具体实现
  • C语言实现排序算法之归并排序详解
  • 基于稀疏图上的Johnson算法的详解
  • 基于一致性hash算法 C++语言的实现详解
  • 深入N皇后问题的两个最高效算法的详解
  • 使用C++实现全排列算法的方法详解
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • <<大话数据结构>>中冒泡排序算法改进
  • 那位高人有任务分配问题的禁忌搜索算法、模拟退火算法的算法实现程序啊
  • 二叉树常用算法(求总节点个数和叶子节点个数)
  • 求对称加密DES算法与非对称加密RSA算法!(可用)
  • boost unordered_map和std::list相结合的实现LRU算法
  • java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
  • 中文网页快速去重算法研究
  • 谁能给出一个最快最高效的求素数的算法?(高分求算法)
  • 使用java jdk中的LinkedHashMap实现简单的LRU算法
  • 谁有这样的算法:给定两个区域,用直线或折线来连接,以及移动其中线段的算法。
  • 广告系统中weak-and算法原理及编码验证
  • 算法之排序算法的算法思想和使用场景总结
  • c++实现MD5算法代码示例
  • 【算法】扑克发牌算法实现
  • c语言实现MD5算法完整代码示例
  • php加密算法之实现可逆加密算法和解密分享
  • MD5算法的C语言实现
  • C++实现查找中位数的O(N)算法和Kmin算法
  • PHP中对各种加密算法、Hash算法的速度测试对比代码
  • 关于加密算法的效率问题
  • 哈希算法计算 Generic Hash and HMAC Program




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3