Python递归实现分治算法

def divide_conquer(problem):
    # 判断问题是否可以直接解决
    if problem is None:
        return None

    # 判断是否已经到达问题的最小规模
    if check_base_case(problem):
        return solve_base_case(problem)

    # 将问题分解成若干个子问题
    subproblems = split_problem(problem)

    # 递归地解决子问题
    solutions = []
    for subproblem in subproblems:
        solution = divide_conquer(subproblem)
        solutions.append(solution)

    # 将子问题的解合并成原问题的解
    result = merge_solutions(solutions)
    return result

def check_base_case(problem):
    return isinstance(problem, str)

def solve_base_case(problem):
    return problem.count('a')

def split_problem(problem):
    mid = len(problem) // 2
    return [problem[:mid], problem[mid:]]

def merge_solutions(solutions):
    return sum(solutions)

problem = 'pidancode.com皮蛋编程'
result = divide_conquer(problem)
print('字符串中出现了 %d 个字母 a' % result)