算法第二次测试第9和第10题代码

9. 设计一个算法，把整数集合{1,2，…, N}中总和为 N 的元素的所有子集报告出来。并写一段程序，运行 N=100，N=1000 时的实例。

"""
该题使用回溯法
"""


def test9(n):
    # 用向量表示该数是否被用到,0的位置浪费掉，为了1,..,n更直观
    use = [0] * (n + 1)
    # 存放该状态下已经的和
    total = 0

    def solve(i=1):
        # 将 use, total的作用域设置为test9函数
        nonlocal use, total
        # i > n 则已经超过数组最右边,total大于n,该回溯了
        if i > n or total > n:
            return
        # 找到解了，输出
        elif total == n:
            # use元素为1证明该元素有用到
            one_solution = [i for i in range(len(use)) if use[i] == 1]
            # 输出解
            print(one_solution)
            # 回去找其他解
            return

        # 讲i加到解
        use[i] = 1
        total += i

        # 向前走，找其他元素
        solve(i + 1)
        # 回溯的时候要剪掉上次加进去的数，再往前找
        use[i] = 0
        total -= i
        solve(i + 1)

    # 从1开始算
    solve(1)
    # 特殊情况处理
    print([n])


if __name__ == '__main__':
    # 100,1000太多了，拿个10测试一下
    test9(10)

运行结果:

第九题

10.设计一个算法，并程序实现，计算下述问题。有编号为 1~n 的 n 个数字，2<=n<=8000, 无序排列。好在，对每个位置的数字，知道排在它前面比它小的数儿有多少，记在 Pre[]里。求这个数列。比如：
Pre[]={0 1 2 1 0}；有 ans= {2 4 5 3 1}. Pre[]={0 1 0 3 2 5 3 7 4}；有ans= {2 6 1 7 3 8 4 9 5 }.

第一种写的很像c++风格，想用c++写的读者可以参考这个样式

def solve_pre(pre: list, n):
    """
    :param pre: pre数组
    :param n: n个元素
    :return:
    """
    # ans代表解向量
    ans = [0] * n
    # 从用来表示用到的数，后面用到就把该数置为-1,相当于打上标记
    c = [i for i in range(1, n + 1)]
    # 从后面开始考虑
    i = n - 1
    while i >= 0:
        j = pre[i]
        k = 0
        # 从左往右找到第一个合适(满足pre)的数
        while (j > 0 or c[k] == -1):
            if (c[k] != -1):
                j = j - 1
            k = k + 1
        # 找到合适的数将该数放到ans,并在c数组将该数置为-1,防止被重复使用
        ans[i] = c[k]
        c[k] = -1
        # 回溯
        i = i - 1
    return ans


if __name__ == '__main__':
    pre1 = [0, 1, 2, 1, 0]
    pre2 = [0, 1, 0, 3, 2, 5, 3, 7, 4]
    print(solve_pre(pre1, len(pre1)))
    print(solve_pre(pre2, len(pre2)))

运行结果:

第10题

第二个写的比较像python风格:

def solve_pre(pre: list):
    """
    这个函数写的比较 pythonic
    :param pre: pre数组
    :return:返回解
    """
    # 放置可选的数字,这里由于range右边是开区间，所以是len(pre)+1
    # 因为我们pool是要1,2,...,n
    pool = list(range(1, len(pre) + 1))
    # 放置解的数组
    ans = []
    # 从右边来,pre最右边的下标是len(pre) - 1, 由于range右边界是开区间，
    # 故要第二个参数是-1, 第三个-1代表逆序
    for i in range(len(pre) - 1, -1, -1):
        # 每次都把把这个数插入到ans最前面，并且把这个数从可选的数中除去
        ans.insert(0, pool.pop(pre[i]))
    return ans


if __name__ == '__main__':
    pre1 = [0, 1, 2, 1, 0]
    pre2 = [0, 1, 0, 3, 2, 5, 3, 7, 4]
    print(solve_pre(pre1))
    print(solve_pre(pre2))

运行结果:

第十题

---

感谢观看。若有错误或遗漏，或者有更有解法，欢迎给我留言~