設這五個數從小到大為
a+1,b+2,c+3,d+4,e+5
則
0≤a≤b≤c≤d≤e≤6
10≤a+b+c+d+e≤20
設k>=1個非負整數,最大不超過m>=0,和不超過n>=0,這樣的無序組有f(m,n,k)個。本題結果為
f(6, 20, 5) -f(6, 9, 5)
則考慮最小的數是否為0(非0就整體-1,從而和n減少k),得到遞推式
約定 f(m,負數,k)=0, f(負數, n, k)=0
所以n<k時,
f 的初值由定義決定:
m>=0, n>=0時 f(m,n,1)=min{m,n}+1
且當m>=n時,f(m,n,k)=f(n,n,k),另記為g(n,k), 遞推式改寫為
k>=1時, g(0,k)=1, g(1,k)=g(1,1)=2,
當n>=0時, g(n,1)=n+1
然後交給電腦遞迴一下。這個演算法其實等價於幾個幾個數。
另外, km<=n時, (這條性質只是為了簡化運算)
對於f(6 20 5),也可以這麼遞迴,不過需要耐心和細心。這裡換個演算法,計算其反面。
5個不超過6的非負整數和不大於20,等價於5個不超過6的非負整數(即6-每個數)和不小於10
f(6 20 5)=(5個不超過6的非負整數構成的無序五元組個數)-f(6 9 5)
=(5個不超過11的正整數構成的五元組個數)-f(6 9 5)
=11*10*9*8*7/5!-g(4 5)=462-f(6 9 5)
g(3 2)=g(1 2)+g(3 1)=2+4=6
g(3 3)=g(0 3)+g(1 2)+g(3 1)=1+2+4=7
g(4 2)=g(2 2)+g(4 1)=g(0 2)+g(2 1)+5=1+3+5=9 (中間結果g(2 2)=4)
g(4 5)=g(4 4)=g(0 4)+g(1 3)+g(2 2)+g(4 1)=1+2+4+5=12
g(5 4)=g(1 4)+g(2 3)+g(3 2)+g(5 1)=2+g(2 2)+6+6=14+4=18
f(6 9 5)=6+7+9+12+18+24=76
f(6 20 5)-f(6 9 5)=462-76*2=310
==================
改了半天終於把錯誤都改過來了,果然遞迴這種東西還是交給計算機吧。
設這五個數從小到大為
a+1,b+2,c+3,d+4,e+5
則
0≤a≤b≤c≤d≤e≤6
10≤a+b+c+d+e≤20
設k>=1個非負整數,最大不超過m>=0,和不超過n>=0,這樣的無序組有f(m,n,k)個。本題結果為
f(6, 20, 5) -f(6, 9, 5)
則考慮最小的數是否為0(非0就整體-1,從而和n減少k),得到遞推式
約定 f(m,負數,k)=0, f(負數, n, k)=0
所以n<k時,
f 的初值由定義決定:
m>=0, n>=0時 f(m,n,1)=min{m,n}+1
且當m>=n時,f(m,n,k)=f(n,n,k),另記為g(n,k), 遞推式改寫為
k>=1時, g(0,k)=1, g(1,k)=g(1,1)=2,
當n>=0時, g(n,1)=n+1
然後交給電腦遞迴一下。這個演算法其實等價於幾個幾個數。
另外, km<=n時, (這條性質只是為了簡化運算)
對於f(6 20 5),也可以這麼遞迴,不過需要耐心和細心。這裡換個演算法,計算其反面。
5個不超過6的非負整數和不大於20,等價於5個不超過6的非負整數(即6-每個數)和不小於10
f(6 20 5)=(5個不超過6的非負整數構成的無序五元組個數)-f(6 9 5)
=(5個不超過11的正整數構成的五元組個數)-f(6 9 5)
=11*10*9*8*7/5!-g(4 5)=462-f(6 9 5)
g(3 2)=g(1 2)+g(3 1)=2+4=6
g(3 3)=g(0 3)+g(1 2)+g(3 1)=1+2+4=7
g(4 2)=g(2 2)+g(4 1)=g(0 2)+g(2 1)+5=1+3+5=9 (中間結果g(2 2)=4)
g(4 5)=g(4 4)=g(0 4)+g(1 3)+g(2 2)+g(4 1)=1+2+4+5=12
g(5 4)=g(1 4)+g(2 3)+g(3 2)+g(5 1)=2+g(2 2)+6+6=14+4=18
f(6 9 5)=6+7+9+12+18+24=76
f(6 20 5)-f(6 9 5)=462-76*2=310
==================
改了半天終於把錯誤都改過來了,果然遞迴這種東西還是交給計算機吧。