数据结构与算法-分治法
分治法：
把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
设计思想：
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
策略：
对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
精髓：
分--将问题分解为规模更小的子问题；
治--将这些规模更小的子问题逐个击破；
合--将已解决的子问题合并，最终得出“母”问题的解；
特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
分治法在每一层递归上都有三个步骤：
分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
合并：将各个子问题的解合并为原问题的解。
分治法（递归技术）
直接或间接调用自身的算法。
注意：因为递归可以替代循环，故必须有终止。否则慎用。
-
for (int i = 0; i <= 10; i++) {
-
Log.e("SCCDemo", "Pos" + i + "返回:" + d(i));
-
}
-
//2021/5/26 功能描述：分治法（递归技术）
-
private int d(int pos) {
-
if (pos == 0 || pos == 1) {
-
return 1;
-
} else {
-
return d(pos - 1) + d(pos - 2);
-
}
-
}
输出：
E/SCCDemo: Pos0返回:1===========E/SCCDemo: Pos1返回:1、
E/SCCDemo: Pos2返回:2===========E/SCCDemo: Pos3返回:3
E/SCCDemo: Pos4返回:5===========E/SCCDemo: Pos5返回:8
E/SCCDemo: Pos6返回:13==========E/SCCDemo: Pos7返回:21
E/SCCDemo: Pos8返回:34==========E/SCCDemo: Pos9返回:55
分治法（二分查找法）
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
要求：
1) 必须采用顺序存储结构。
2) 必须按关键字大小有序排列。
-
ArrayList<Integer> numbers = new ArrayList<>();
-
for (int i = 0; i < 29; i++) {
-
numbers.add(i);
-
}
-
/**
-
* 功能描述：分治法（二分查找）
-
* @param numbers 数组
-
* @param a 起点
-
* @param b 终点
-
* @param lookUpNum 查找的数
-
*/
-
private void e(ArrayList<Integer> numbers, int a, int b, int lookUpNum) {
-
if (a > b) {//查找完且未找到结果,查找失败
-
Log.e("SCCDemo", "lookUpNum:" + lookUpNum + "返回:-1");
-
} else {
-
int mid = (a+b)/2;//找到中间点,可能导致溢出，应该使用mid=(b-a)/2+a;
-
Log.e("SCCDemo", "mid:" + numbers.get(mid));
-
if (numbers.get(mid) == lookUpNum) {
-
Log.e("SCCDemo", "lookUpNum:" + lookUpNum + "返回:" + mid);
-
} else {
-
if (numbers.get(mid) > lookUpNum) {
-
Log.e("SCCDemo", "查找范围:（" + a + "，" + (mid - 1) + ")");
-
//中间值大于lookUpNum，查找范围锁定是(a,(mid-1));
-
e(numbers, a, mid - 1, lookUpNum);
-
} else {
-
Log.e("SCCDemo", "查找范围:（" + (mid + 1) + "，" + b + ")");
-
//中间值小于lookUpNum，查找范围锁定是((mid+1),b);
-
e(numbers, mid + 1, b, lookUpNum);
-
}
-
}
-
}
-
}
e(numbers, 0, numbers.get(numbers.size()-1), 1);
E/SCCDemo: mid:14——比较后——E/SCCDemo: 查找范围:（0，13)
E/SCCDemo: mid:6——比较后——E/SCCDemo: 查找范围:（0，5)
E/SCCDemo: mid:2——比较后——E/SCCDemo: 查找范围:（0，1)
E/SCCDemo: mid:0——比较后——E/SCCDemo: 查找范围:（1，1)
E/SCCDemo: mid:1——比较后——E/SCCDemo: lookUpNum:1返回:1
e(numbers, 0, numbers.get(numbers.size()-1), 15);
E/SCCDemo: mid:14——比较后——E/SCCDemo: 查找范围:（15，28)
E/SCCDemo: mid:21——比较后——E/SCCDemo: 查找范围:（15，20)
E/SCCDemo: mid:17——比较后——E/SCCDemo: 查找范围:（15，16)
E/SCCDemo: mid:15——比较后——E/SCCDemo: lookUpNum:15返回:15
e(numbers, 0, numbers.get(numbers.size()-1), 28);
E/SCCDemo: mid:14——比较后——E/SCCDemo: 查找范围:（15，28)
E/SCCDemo: mid:21——比较后——E/SCCDemo: 查找范围:（22，28)
E/SCCDemo: mid:25——比较后——E/SCCDemo: 查找范围:（26，28)
E/SCCDemo: mid:27——比较后——E/SCCDemo: 查找范围:（28，28)
E/SCCDemo: mid:28——比较后——E/SCCDemo: lookUpNum:28返回:28
文章来源: shuaici.blog.csdn.net，作者：帅次，版权归原作者所有，如需转载，请联系作者。
原文链接：shuaici.blog.csdn.net/article/details/117290466
- 点赞
- 收藏
- 关注作者
评论（0）