回覆列表
  • 1 # 使用者3764646602807

    設這五個數從小到大為

    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

    ==================

    改了半天終於把錯誤都改過來了,果然遞迴這種東西還是交給計算機吧。

  • 中秋節和大豐收的關聯?
  • 袁詠儀做了什麼,為何採訪時說曾後悔傷害張智霖?