分治算法目录
目录
分治算法目录一、分治算法是什么？二、实现步骤1.二分法2.递归3.合并排序，归并排序等...
三、使用要求四、练习1.指数练习：2.查找任意一个峰值：3.查找所有峰值：4.数组集合：5.计算逆序对：
总结
一、分治算法是什么？
分治算法，就两个字：分和治。 分：通过一些规律把一个大问题分成若干小问题 治：把这些小问题以此解决，然后返回结果
举个例子：计算1-100的和，在没有求和公式的情况下都会从1+2+3+…+99+100。通过发现得到1+100=2+99=3+98…=49+ 50，而这些我们就相当于把这个大问题换成了若干小问题。
二、实现步骤
1.二分法
上一篇提到的二分搜索其实就是实现分治算法的一种，可以说二分搜索是分治算法的一个子集；二分法的使用
2.递归
使用分治法最多的还是使用递归来解决问题。附上一篇关于递归的文章：递归讲解
3.合并排序，归并排序等…
三、使用要求
该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
利用该问题分解出的子问题的解可以合并为该问题的解；
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
四、练习
1.指数练习：
利用递归解决指数问题
def pow(x
, n
):
if n
<= 0:
return 1
elif n
== 1:
return x
elif n
% 2:
return pow(x
* x
, n
// 2) * x
else:
return pow(x
* x
, n
// 2)
print(pow(5, 25))
2.查找任意一个峰值：
在一个数组中可能有多个峰值，请任意找一个并返回下标
def search(listt
):
return num
(listt
, 0, len(listt
) - 1)
def num(listt
, start
, end
):
if start
== end
:
return start
elif start
+ 1 == end
:
if listt
[start
] > listt
[end
]:
return start
else:
return end
mid
= (start
+ end
) // 2
if listt
[mid
- 1] < listt
[mid
] < listt
[mid
+ 1]:
return num
(listt
, mid
+ 1, end
)
elif listt
[mid
+ 1] < listt
[mid
] < listt
[mid
- 1]:
return num
(listt
, start
, mid
- 1)
elif listt
[mid
] > listt
[mid
- 1] and listt
[mid
] > listt
[mid
+ 1]:
return mid
n
= [0, 1, 9, 2, 3, 4, 8, 7, 5, 11, 6, 20, 23, 21]
print(search
(n
))
3.查找所有峰值：
def search(nums
):
i
= 1
index
= []
while i
< len(nums
):
if nums
[i
- 1] < nums
[i
]and nums
[i
] > nums
[i
+ 1]:
index
.append
(i
)
i
+= 1
return index
n
= [0, 1, 9, 2, 3, 4, 8, 7, 5, 11, 6, 20, 23, 21]
print(search
(n
))
4.数组集合：
两个长短不一的数组找集合，可能会有重复的数字，将他们全部输出
def search(nums1
, nums2
):
index
= []
i
, j
= 0, 0
while True:
if nums2
[j
] == nums1
[i
]:
index
.append
(nums2
[j
])
i
+= 1
j
+= 1
else:
i
+= 1
if i
== len(nums1
) - 1 or j
== len(nums2
) - 1:
break
return index
nums1
= [1, 2, 2, 2, 1]
nums2
= [2, 2, 3]
nums1
.sort
()
nums2
.sort
()
print(search
(nums1
, nums2
))
5.计算逆序对：
在一个无序数组中 a[i]>a[j] 且 i<j 这两个数就是一个逆序对
def merge(left
, right
):
result
= list()
i
, j
= 0, 0
inv_count
= 0
while i
< len(left
) and j
< len(right
):
if left
[i
] < right
[j
]:
result
.append
(left
[i
])
i
+= 1
elif right
[j
] < left
[i
]:
result
.append
(right
[j
])
j
+= 1
inv_count
+= (len(left
)-i
)
result
+= left
[i
:]
result
+= right
[j
:]
return result
, inv_count
def conut(nums
):
if len(nums
) < 2:
return nums
, 0
mid
= len(nums
) // 2
left
, inv_left
= conut
(nums
[:mid
])
right
, inv_right
= conut
(nums
[mid
:])
merged
, counts
= merge
(left
, right
)
counts
+= (inv_left
+ inv_right
)
return merged
, counts
nums
= [1, 20, 3, 5, 4]
print(conut
(nums
))
总结
提示：这里对文章进行总结：分治法作为三大算法之一，必有它的难点和独特之处。拿到题时多加思考和分析，理解+勤练习。
