- 设计一个算法，把整数集合{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))
运行结果:
第十题
感谢观看。若有错误或遗漏，或者有更有解法，欢迎给我留言~
网友评论