递归与分治策略--计算机算法设计与分析

递归概念:直接或者间接调用自身的算法,称为递归运算。
分治思想:把一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相等,递归解决子问题后再将结果合并
下方为一些应用函数。因为最近再学Python,下面示例方式均用Python代码体现。(逻辑不变,理解就好)


应用之二分法搜索:用分治法的典型例子,对已经排好序的n个元素中,找出某一个值。
思路为:将有序的n个元素大致的分为两半,取中间元素与 x比较,若大于则在右侧同样取剩下元素的中间值进行比较,以此类推

import math
def binary_search(x,list,n):
    left =0
    right =n-1
    while left<right:
        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<right:
        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]

应用之快速排序:用分治策略,对无序列表进行排序的算法
思路为:对输入的数列,从中选一个数字,把对应数字分别放置到左右两侧。然后对左右两侧的子数列再进行递归调用。

应用之线性时间选择

未经允许不得转载:书生吴小帅 » 递归与分治策略--计算机算法设计与分析

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址