千草 發問時間: 科學數學 · 1 0 年前

離散數學-遞迴 習題求解

賣場中有一元的物品2種、二元的物品3種、三元的物品1種,假設C(n)為花掉n元購買物品的方法,試寫出C(n)的遞迴方程式和它的起始值(boundary condition)。

(提示C(1)=2,C(2)=7,C(3)=21)

那Cn= ???+ ??? +???

2 個解答

評分
  • 天助
    Lv 7
    1 0 年前
    最佳解答

    C(1)=2 (1元可買2種物品)

    C(2)=3+2*2=7(2元3種or 1元又1元2*2種)

    C(3)=1+7*2+2*3(3元1種+ 2元又1元7*2種+ 1元又2元2*3種)

    考慮最後一件物品的價格,共有3種case

    case1: 最後一件為3元(1種),then前面有n-3元C(n-3)種,共有C(n-3)*1種

    case2: 最後一件為2元(3種),then前面有n-2元C(n-2)種,共有C(n-2)*3種

    case3: 最後一件為1元(2種),then前面有n-1元C(n-1)種,共有C(n-1)*2種

    故C(n)=C(n-3)+3C(n-2)+2C(n-1)

    2010-04-24 17:52:08 補充:

    題意中買東西的順序是有差別的,否則C(2)不會是7

    因此1+3與3+1不同!

  • 1 0 年前

    TO天助心清

    這樣算會重複喔

    例如

    我C(n-3)中已經買了A(1元的) 在花3元買B

    和我C(n-1)中已經買了B(3元的) 在花1元買A

    結論是一樣的 但是你至少算了兩次

還有問題?馬上發問,尋求解答。