ACM程序设计,分治法的课件,相关练习,以及各种题型,由简单到复杂,由容易到困难的各个阶段。是学习这一基本算法的很好的辅助资料。
分治法求解排序问题 合并为其中一种 效率不错 时间复杂度为O nlogn 代码有本人大量解释 便于理解
%mergesort 分治算法——归并排序 %divide——将数组一分为二 %conquer——对两部分数组分别排序 %combine——将各自排好序的数组融合 %以此类推递归调用
%divide——将数组分成两段 %conquer——每段分别求最大字段和 %combine——最大子段和无非三种情况:左端、右端、横跨中间 %每段分别求最大子段和的时候采用递归调用
设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表, (1)每个选手必须与其他n-1个选手各赛一次; (2) 每个选手一天只能赛一次; (3) 当n是偶数时,循环赛进行n-1天,当n是奇
对于分治法,一个简单的例子,数字旋转方阵,用二位数组data[N][N]表示N*N的方阵,观察方阵中数字的规律,可以从外层向里层填数……
Constructing a divide and conquer algorithm for Gray code (C++)
Fast sorting using recursive divide and conquer algorithm
分治法的另外一种排序算法,快速排序。有注释,便于阅读,因为交换时使用的引用,暂时归为C++,C语言版稍后奉上。
采用递归分治方法进行合并排序的算法下载这是为上机做准备时写的