分区算法的 python 实现示例

分治算法的思想：将问题规模为n的原问题归纳为规模n/2的两个子问题，或规模n/m的m'个子问题；若规模缩小的子问题仍不能简单求解，则继续归约为规模更小的问题；分别求解小规模的子问题，并逐步综合得到原问题的解。

分治算法改进途径：1.通过代数变换减少子问题数。

                                 2.通过预处理减少递归内部计算量。

分治算法的经典例子：1.查找峰顶的算法。

重要代码：

2.关于两个鸡蛋判断楼层问题：

问题：经典的问题，给你两个鸡蛋，从100层楼上往下扔，从某个楼层开始，鸡蛋开始碎，请问最少扔多少次可以判断出楼层。

# -*- coding: utf-8 -*-

"""

Created on Wed Mar  3 20:24:20 2021

@author: iron

"""

#分治算法问题

import numpy as np #NumPy 是一个非常优秀的提供矩阵操作的包

def dynamic_program(eggs,floors):

    table=np.zeros((eggs+1,floors+1)) #返回来一个给定形状和类型的用0填充的数组

    #如果只有0楼或者一楼时

    for i in range(eggs+1):

        table[i][0]=0

        table[i][1]=1

    #如果只有一个鸡蛋

    for j in range(floors+1):

        table[1][j]=j

    #其他情况，table( eggs, floors) = 1+ Max(table( eggs-1 , floors-1), table( eggs, floors-x))

    for i in range(2,eggs+1):

        for j in range(2,floors+1):

            table[i][j]=2**63-1 #取值范围为-2**63～2**63-1

            for x in range(1,j):

                #table[i-1][x-1]表示鸡蛋在X楼碎了减小一个。table[eggs][j-x]

                #表示鸡蛋还是最开始的楼层变为j-x

                maxtable=1+max(table[i-1][x-1],table[i][j-x]) #子问题

                if maxtable<table[i][j]:

                    table[i][j]=maxtable

    print(table[eggs][floors])

if __name__ == '__main__':

    dynamic_program(2,100)

    dynamic_program(6, 100)

    dynamic_program(10, 100)

    print("\033[32;1m由此可知，当楼层固定时，鸡蛋足够时，次数也只会固定在一个值，不会继续减少，也就是说前期鸡蛋越多次数越少，后期次数不随鸡蛋的增多而变化，二分法结果就是极限\033[0m")

其实还有很多经典的运用分治算法的例子，简书家人们可以在评论区发表。