第1关：分治法找最大最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def min_max(a):
    ## 参数a为列表，编写分治法函数，返回a的最大值和最小值
    ## 注意，有两个返回值
    if len(a) == 1:
        return (a[0], a[0])
    elif len(a) == 2:
        return (min(a), max(a))
    m = len(a) // 2
    lmin, lmax = min_max(a[:m])
    rmin, rmax = min_max(a[m:])
    return (min(lmin, rmin), max(lmax, rmax))


if __name__ == "__main__":
    ##编写代码，输入列表A，A列表中都是数字
    A = [float(x) for x in input().split(",")]

    ##输出A的最小值和最大值
    ##下面这行代码不需要修改哦～
    print("Minimum and Maximum: %g, %g" % (min_max(A)))

第2关：找假币问题

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
def find_coin(a, arr):
    x = len(arr)
    if x == 1:
        return a
    if x % 2 == 1:
        x = x - 1
        y = 1
    else:
        y = 0

    if (sum(arr[: x // 2])) < sum(arr[x // 2 : x]):
        return find_coin(a, arr[: x // 2])
    elif (sum(arr[: x // 2])) > sum(arr[x // 2 : x]):
        return find_coin(a + x // 2, arr[x // 2 : x])
    else:
        if y == 0:
            return -1
        else:
            if arr[x] < arr[0]:
                return a + x
            else:
                return -1


if __name__ == "__main__":
    coins = [int(x) for x in input().split(",")]

    position = find_coin(0, coins)
    print(
        f"position is: {position}, weight is: {-1 if position == -1 else coins[position]}."
    )