多元線性方程整數(shù)解的計(jì)數(shù)
[TOC]
問(wèn)題描述
統(tǒng)計(jì)
的非負(fù)整數(shù)解的個(gè)數(shù)打月。列出這些解。
枚舉
靜態(tài)地看蚕捉，的范圍容易確定奏篙，
。各個(gè)范圍的笛卡爾積
是答案的范圍迫淹，其中的元素記為
秘通。將每個(gè)
帶入方程驗(yàn)證，即可篩選出解敛熬。
from itertools import product
def cc(s, a):
def p(x):
return sum([x * a for x, a in zip(x, a)])
return [x for x in product(*[range(s // ai + 1) for ai in a]) if p(x) == s]
遞歸
如果將決定中每個(gè)
看作一個(gè)動(dòng)態(tài)的過(guò)程肺稀，則已決定的
對(duì)未決定的
的范圍有影響。我們可以沿著兩個(gè)方向減小問(wèn)題的規(guī)模应民，分別是
- 減小變量的個(gè)數(shù)
- 減小
def cr(s, a):
def r(s, a, x):
if s == 0:
xs.append(tuple(x))
elif s > 0 and len(a) != 0:
x = list(x)
r(s, a[:-1], x) # 減小變量個(gè)數(shù)
x = list(x)
x[len(a) - 1] += 1
r(s - a[-1], a, x) # 減小S
xs = []
r(s, a, [0] * len(a))
return xs
代碼中x就是中的某個(gè)
.
對(duì)比
將遞歸樹葉子節(jié)點(diǎn)的個(gè)數(shù)作為遞歸的復(fù)雜度话原，與枚舉法的中元素個(gè)數(shù)做對(duì)比，發(fā)現(xiàn)枚舉空間的大小大約是遞歸空間大小的40倍诲锹。運(yùn)行時(shí)間的比值也接近40繁仁。
附錄
jupyter notebook 完整實(shí)驗(yàn)代碼：
from itertools import *
l = 0
def cc(s, a):
global l
def p(x):
return sum([x * a for x, a in zip(x, a)])
l = len([x for x in product(*[range(s // ai + 1) for ai in a])])
return [x for x in product(*[range(s // ai + 1) for ai in a]) if p(x) == s]
x1 = cc(100, [1, 5, 10, 25, 50])
cnt = 0
def cr(s, a):
def r(s, a, x):
global cnt
if s == 0:
xs.append(tuple(x))
cnt += 1
elif s > 0 and len(a) != 0:
x = list(x)
r(s, a[:-1], x)
x = list(x)
x[len(a) - 1] += 1
r(s - a[-1], a, x)
else:
cnt += 1
xs = []
r(s, a, [0] * len(a))
return xs
x2 = cr(100, [1, 5, 10, 25, 50])
set(x1) == set(x2)
x1 == x2
l / cnt
%timeit cc(100, [1, 5, 10, 25, 50])
%timeit cr(100, [1, 5, 10, 25, 50])
