分治算法,多么简单的思想!可是它无处不在。btree,b+树中都有它的身影!
1、分治算法:分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。
2、二分法:利用分治策略求解时,所需时间取决于分解后子问题的个数、子问题的规模大小等因素,而二分法,由于其划分的简单和均匀的特点,是经常采用的一种有效的方法,例如二分法检索。
3、解题步骤:分治法解题的一般步骤:
(1)分解,将要解决的问题划分成若干规模较小的同类问题;
(2)求解,当子问题划分得足够小时,用较简单的方法解决;
(3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。
4、实例说明:
a)、利用分治算法求最大最小数:
package sunfa.idea;
import java.util.Arrays;
/**
* 当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,
* 我们往往先把它分解成几个子问题
* ,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题
* ,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。
*
*/
public class BranchDemo1 {
public static void main(String[] args) {
BranchDemo1 demo1 = new BranchDemo1();
int[] a = { 1, 3, 2, 4, 5, 6, 3, 2, 10, 12, 9 };
Arrays.sort(a);
System.out.println(Arrays.toString(a));
demo1.simpleMinMax(a);
System.out.println("branchMinMax:");
MinMaxBean bean = branchMinMax(a, 0, a.length-1);
System.out.println("max:" + bean.max + ",min:" + bean.min);
}
// 普通算法
public static void simpleMinMax(int[] a) {
MinMaxBean bean = new MinMaxBean();
bean.max = a[0];
bean.min = a[0];
for (int i = 1; i < a.length; i++) {
if (bean.max < a[i])
bean.max = a[i];
if (bean.max < a[i])
bean.min = a[i];
}
System.out.println("max:" + bean.max + ",min:" + bean.min);
}
//分治算法求最大最小数
public static MinMaxBean branchMinMax(int[] a, int low, int hihg) {
MinMaxBean bean = new MinMaxBean();
//2 求解
if (low > hihg - 2) {//如果问题规模较小,此处小于等于2个则直接求解
if (a[low] < a[hihg]) {
bean.max = a[hihg];
bean.min = a[low];
} else {
bean.max = a[low];
bean.min = a[hihg];
}
System.out.println("区间["+low+","+hihg+"] [max:"+bean.max+",min:"+bean.min+"]");
} else {//否则对问题进行分解
int mid = (low + hihg) >>> 1; //1 分解
//3 合并
MinMaxBean b1 = branchMinMax(a, low, mid);
MinMaxBean b2 = branchMinMax(a, mid + 1, hihg);
bean.max = b1.max > b2.max ? b1.max : b2.max;
bean.min = b1.min < b2.min ? b1.min : b2.min;
}
return bean;
}
}
class MinMaxBean {
int max;
int min;
}
b)利用二分法查找数组中某个数或对象的索引
java.util.Arrays源码:
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
在对象数组中的二分法查找:
private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
Object key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable midVal = (Comparable)a[mid];
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found.
}
分享到:
相关推荐
学 习a c m 分 治算法 的入门 教程简单易学acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法acm分治算法vacm分治算法acm...
在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解...
分值算法实验报告,简单易懂,适合初学者而且不愿意去花大心思的人
主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考下
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。
我叫什么名字,我来自哪里,我喜欢搞什么技术
本程序包括递归与分治算法章节课后习题中的内容的集合,方便简单易懂,对刚学算法的人帮助很大,这是我们这学期的三道作业题合在一起的程序。
棋盘覆盖问题,是用分治法实现的。基本上全是数字实现的。虽然简单,但是这是为了说明一个算法的设计问题
C语言分治算法求解30枚银币中的某枚假币,简单而言,30枚银币中有1枚假币,该假币的重量比其他29枚银币的重量小1,先将30枚银币平分成两部分,各15枚,分别称重,重量小的那一半银币中必然包含假币,然后再分成两...
二分查找 归并排序 快速排序 穷举N位二进制 穷举所有排列
对于分治法,一个简单的例子,数字旋转方阵,用二位数组data[N][N]表示N*N的方阵,观察方阵中数字的规律,可以从外层向里层填数……
棒糖的价格总是在波动的。 假设你已经通过未来机器知道未来连续n天中棒糖的单价...设计一个O(n log n)的算法。(为简单起见,假设n是2的幂,且n) 例如: Input 4 9 1 5 2 Output 4 例如: Input 4 9 1 5 2 Output 4
ACM程序设计,分治法的课件,相关练习,以及各种题型,由简单到复杂,由容易到困难的各个阶段。是学习这一基本算法的很好的辅助资料。
关于最接近点对问题 给定平面上n个点,找出其中一对点,使得在n个点所构成的所有点对中,该点对的距离最小。 这个问题很容易理解,似乎也...对这种一维的简单情形,我们尝试用分治法来求解,并希望能推广到二维的情形。
算法的分析,分治思想,能使同学能理解算法的思想,对学习语言能简单。
十大算法\分治算法\中国数学建模-编程交流-分治算法_1.txt 十大算法\分治算法\中国数学建模-编程交流-分治算法_2.txt 十大算法\动态规划 十大算法\动态规划\中国数学建模-编程交流-动态规划算法_1.txt 十大算法\...
五大常用算法之一:分治算法 分治算法 一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子...
简单的分治法排序代码 最近在看算法书 就写写程序练手
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。 分治法解题的一般步骤: (1)分解,将要解决的问题划分成若干...
在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解...