递归与分治java策略实验报告_递归与分治策略–计算机算法设计与分析

递归概念：直接或者间接调用自身的算法，称为递归运算。

分治思想：把一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相等，递归解决子问题后再将结果合并

下方为一些应用函数。因为最近再学Python，下面示例方式均用Python代码体现。(逻辑不变，理解就好)

应用之二分法搜索：用分治法的典型例子，对已经排好序的n个元素中，找出某一个值。

思路为：将有序的n个元素大致的分为两半，取中间元素与 x比较，若大于则在右侧同样取剩下元素的中间值进行比较，以此类推

import math

def binary_search(x,list,n):

left =0

right =n-1

while left

middle = math.ceil((left+right)/2) ## 取大于或等于平均数的最小整数

if x== list[middle]:

print("第",middle,"数字为所查找值")

return

elif x>list[middle]:

left = middle

else:

right = middle-1

print("未找到该数值")

list =[1,2,3,4,5,6,7,8,9,10]

num = 8

n= 10

binary_search(num,list,n)

运行结果为：第 7 数字为所查找值

实际上，在Python中，是内置了函数课直接使用

list.index(num) ## 从列表中找出某个值第一个匹配项的索引位置

应用之合并排序：用分治策略对n个元素进行排序的算法

思路为：将待排序元素分成大小相近的两个子集，然后分别对子集进行排序，之后再将结果合并。

import math

def merge(listb,i,m,n):

lista=listb.copy()

j =m+1

k=i

while i<=m and j<= n:

if lista[i]<= lista[j]:

listb[k] = lista[i]

i +=1

k +=1

else:

listb[k] = lista[j]

j +=1

k +=1

if i>m:

for q in range(j,n+1) :

listb[j] = lista[q]

j+=1

else:

for q in range(i,m+1):

listb[k] =lista[q]

k +=1

def merge_sort(lista,left,right):

if left

middle =math.floor((left+right)/2)

merge_sort(lista,left,middle)

merge_sort(lista,middle+1,right)

merge(listb,left,middle,right)

lista = [2,4,3,1,6,7,5,9,8,10]

listb = lista.copy()

merge_sort(lista,0,9)

print(listb)

实际上在Python中，已经内置了相关函数，如下

result=lista.sort()

print(lista)

输出结果均为：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

应用之快速排序：用分治策略，对无序列表进行排序的算法

思路为：对输入的数列，从中选一个数字，把对应数字分别放置到左右两侧。然后对左右两侧的子数列再进行递归调用。

应用之线性时间选择：给定有序序列，找到该序列的第K小元素。也是使用分治策略。

思路为：若是找最大或者最小，是比较方便 ，若是找中位数就比较麻烦。举例如下，

(1)将n个输入元素划分成n/5(向上取整)个组，每组5个元素，最多只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5(向上取整)个。

(2)递归调用select来找出这n/5(向上取整)个元素的中位数。如果n/5(向上取整)是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。