- 設(shè)計(jì)一個(gè)算法曼库，把整數(shù)集合{1,2，…, N}中總和為 N 的元素的所有子集報(bào)告出來(lái)臀防。并寫一段程序眠菇，運(yùn)行 N=100，N=1000 時(shí)的實(shí)例袱衷。
"""
該題使用回溯法
"""
def test9(n):
# 用向量表示該數(shù)是否被用到,0的位置浪費(fèi)掉捎废，為了1,..,n更直觀
use = [0] * (n + 1)
# 存放該狀態(tài)下已經(jīng)的和
total = 0
def solve(i=1):
# 將 use, total的作用域設(shè)置為test9函數(shù)
nonlocal use, total
# i > n 則已經(jīng)超過(guò)數(shù)組最右邊,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)
# 回溯的時(shí)候要剪掉上次加進(jìn)去的數(shù)登疗，再往前找
use[i] = 0
total -= i
solve(i + 1)
# 從1開始算
solve(1)
# 特殊情況處理
print([n])
if __name__ == '__main__':
# 100,1000太多了，拿個(gè)10測(cè)試一下
test9(10)
運(yùn)行結(jié)果:
第九題
10.設(shè)計(jì)一個(gè)算法，并程序?qū)崿F(xiàn)辐益，計(jì)算下述問題断傲。有編號(hào)為 1~n 的 n 個(gè)數(shù)字，2<=n<=8000, 無(wú)序排列智政。好在艳悔，對(duì)每個(gè)位置的數(shù)字，知道排在它前面比它小的數(shù)兒有多少女仰，記在 Pre[]里。求這個(gè)數(shù)列抡锈。比如：
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++風(fēng)格床三，想用c++寫的讀者可以參考這個(gè)樣式
def solve_pre(pre: list, n):
"""
:param pre: pre數(shù)組
:param n: n個(gè)元素
:return:
"""
# ans代表解向量
ans = [0] * n
# 從用來(lái)表示用到的數(shù)一罩，后面用到就把該數(shù)置為-1,相當(dāng)于打上標(biāo)記
c = [i for i in range(1, n + 1)]
# 從后面開始考慮
i = n - 1
while i >= 0:
j = pre[i]
k = 0
# 從左往右找到第一個(gè)合適(滿足pre)的數(shù)
while (j > 0 or c[k] == -1):
if (c[k] != -1):
j = j - 1
k = k + 1
# 找到合適的數(shù)將該數(shù)放到ans,并在c數(shù)組將該數(shù)置為-1,防止被重復(fù)使用
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)))
運(yùn)行結(jié)果:
第10題
第二個(gè)寫的比較像python風(fēng)格:
def solve_pre(pre: list):
"""
這個(gè)函數(shù)寫的比較 pythonic
:param pre: pre數(shù)組
:return:返回解
"""
# 放置可選的數(shù)字,這里由于range右邊是開區(qū)間，所以是len(pre)+1
# 因?yàn)槲覀僷ool是要1,2,...,n
pool = list(range(1, len(pre) + 1))
# 放置解的數(shù)組
ans = []
# 從右邊來(lái),pre最右邊的下標(biāo)是len(pre) - 1, 由于range右邊界是開區(qū)間撇簿，
# 故要第二個(gè)參數(shù)是-1, 第三個(gè)-1代表逆序
for i in range(len(pre) - 1, -1, -1):
# 每次都把把這個(gè)數(shù)插入到ans最前面聂渊，并且把這個(gè)數(shù)從可選的數(shù)中除去
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))
運(yùn)行結(jié)果:
第十題
感謝觀看。若有錯(cuò)誤或遺漏四瘫，或者有更有解法汉嗽，歡迎給我留言~
