Re: 台大離散

看板Grad-ProbAsk作者wodahs (還我明日香!!)時間11年前 (2015/02/11 01:00)推噓6(6推 0噓 8→)

留言14則, 7人參與討論串3/3 (看更多)

※ 引述《h04mp6286 (H28)》之銘言： : ※ 引述《you00360842 (handsome chien)》之銘言： : : X1+X2+...+Xn=r : : 1<=X1<X2<....<Xn<=r : : ㄧ開始以為trivial : : 結果沒等號 : : 算出c(r,n) : : 可是列幾個例子暴力法卻沒任何規律 : : 求解 : 這題目超難 : 敝人的超強同學提供一個想法 : 若今天題目是x+y+z=15 : x,y,z三者皆異(x<y<z) : 令y=x+u : z=y+w=x+u+w : 問題就變成3x+2u+w=15 (x,u,w>0) : 此題應該可以比照辦理吧 : 變成n*x1+(n-1)*y2+(n-2)*y3+...+1*yn=r (x1,y2~yn>0) : 然後就不會解了q_q : 有強者可以解下去嘛？明天要考成大睡前靈光一閃想到一種解法因為題目已知 1 <= X1 < X2 < X3 < ... <= r 推得 X1 >= 1, X2 >=2, X3 >=3, ...., Xn >=n, 其中 n<=r 令 Y1=X1-1, Y2=X2-2, Y3=X3-3, ..., Yn=Xn-n, Y1,...,Yn>=0 所以 Y1+Y2+ ... +Yn = (X1+X2+ ..+Xn) - (1+2+ ...+n) 因為題目已知 X1+X2+ ... + Xn = r 推得 Y1+Y2+ ... +Yn = r -(1+2+ ... +n) = r - n(1+n)*(1/2) = r-n-0.5 這題將X平移成Y 來求非負整數個數解因此答案為 n+r-n-0.5-1 r-1.5 ( ) = ( ) r-n-0.5 r-n-0.5 這是我想到的解法....這題出的好漂亮換一種寫法考試一緊張就完全寫不出來惹..... -- ╔══════════════════╗ ║即使前路茫茫無盡我的雙手仍抱著光明╚══════╗ ║告別的時候靜下來的心歸於無有的身體叫耳朵細聽 ║ ║生存的奇妙死亡的不可思議花與風與城市都同一樣 ║ ╚═════════════════════════╝ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.169.206.171 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1423587633.A.F3E.html

推

you00360842

02/11 05:59, , 1^F

02/11 05:59, 1^F

推

a95641126

02/11 06:52, , 2^F

02/11 06:52, 2^F

→

mkchiun1028

02/11 07:36, , 3^F

02/11 07:36, 3^F