发表于 | 分类于 | 阅读次数:
字数统计: 407 | 阅读时长 ≈ 1

分治问题 适合于使用递归实现

帮助设计分布式系统和并行计算，细分后的问题交给不同的机器来处理

某些机器专门负责收集来自不同机器的处理结果 完成结果的合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


# coding=utf-8
import copy


def merge_sort(to_sort=None):
    """
    使用函数的递归（嵌套）调用，实现归并排序（从小到大）
    :param to_sort: 等待排序的数组
    :return: 排序后的数组
    """
    if to_sort is None:
        return []
    # 如果分解到只剩一个数，返回该数
    if len(to_sort) == 1:
        return to_sort
    # 将数组分解成左右两半
    mid = len(to_sort) // 2  # python3 // 表示整除，不带小数
    left = copy.copy(to_sort[0:mid])
    right = copy.copy(to_sort[mid:len(to_sort)])
    # 嵌套调用 对两半数组分别进行排序
    left = merge_sort(left)
    right = merge_sort(right)
    # 合并排序后的两半
    merged = merge(left, right)

    return merged


def merge(left=None, right=None):
    """
    合并两个已经排序完毕的数组（从小到大）
    :param left: 左半边数组
    :param right: 右半边数组
    :return: 合并后的数组
    """
    if left is None:
        left = []
    if right is None:
        right = []
    merged_one = list()
    ai = 0
    bi = 0
    # 轮流从两个数组中取出较小的值 放入合并后的数组中
    while ai < len(left) and bi < len(right):
        if left[ai] <= right[bi]:
            merged_one.append(left[ai])
            ai = ai + 1
        else:
            merged_one.append(right[bi])
            bi = bi + 1
    # 将某个数组内剩余的数字放入合并后的数组中
    if ai < len(left):
        for i in range(ai, len(left)):
            merged_one.append(left[i])
    else:
        for i in range(bi, len(right)):
            merged_one.append(right[i])
    return merged_one


if __name__ == '__main__':
    to_sort_ = [7,6,2,4,1,9,3,8,0,5]
    sorted_ = merge_sort(to_sort_)
    print(sorted_)

发表于 | 分类于 | 阅读次数:
字数统计: 295 | 阅读时长 ≈ 1

假设有四种面额的钱币，1 元、2 元、5 元和 10 元，而您一共给我 10 元，那您可以奖赏我 1 张 10 元，或者 10 张 1 元，或者 5 张 1 元外加 1 张 5 元等等。 如果考虑每次奖赏的金额和先后顺序，那么最终一共有多少种不同的奖赏方式呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
 # coding=utf-8
import copy

rewards = [1, 2, 5, 10]  # 四种面额的纸币


def get_all_components(total_rewards, result=None):
    """
    使用函数的递归（嵌套调用），找出所有可能的奖赏组合
    :param
        total_rewards 奖赏总金额
        result 保存当前的解
    :return: None
    """
    # 当 total_rewards=0 时，证明它是满足条件的解，结束嵌套调用，输出解
    if result is None:
        result = []
    if total_rewards == 0:
        print(result)
        return
    # 当 total_rewards<0 时，证明它不是满足条件的解，不输出
    elif total_rewards < 0:
        return
    else:
        for i, _ in enumerate(rewards):
            new_result = copy.copy(result)  # 由于有4种情况，需要 clone 当前的解并传入被调用的函数
            new_result.append(rewards[i])  # 记录但当前但选择，解决一点问题
            get_all_components(total_rewards-rewards[i], new_result)  # 剩下但问题，留给嵌套调用去解决


if __name__ == '__main__':
    total_reward = 10
    get_all_components(total_reward)