Re: [資工] 離散 103北大資工鴿籠

看板Grad-ProbAsk作者Honor1984 (奈何上天造化弄人？)時間8年前 (2017/10/24 16:29)推噓2(2推 0噓 10→)

留言12則, 2人參與討論串2/2 (看更多)

※ 引述《q1qip123 (wtlee)》之銘言： : 想請問在箭頭那一行 : 若是我假設一數列為 2,1,6,7,8,9,10,5,4,3 : 則 I(1)=length('2,6,7,8,9,10') : D(1)=length('10,5,4,3') : I(2)=length('1,6,7,8,9,10') : D(2)=length('10,5,4,3') : 那我a1跟a2定義出來的數對(I,D)都是（6,4） : 不就不會產生n^2+1個數對了？ : 謝謝！http://i.imgur.com/R6lj4uh.jpg

: ----- : Sent from JPTT on my OPPO R7sf. 你的理解有誤 D_1 = length('2, 1') = 2 I_2 = length('1,6,7,8,9,10') = 6 D_2 = length('1') = 1 所以只要數列總數 = n^2 + 1，就找得到長度為n + 1的遞增或遞減數列你沒有看懂證明尤其是倒數第二、三段如果a_i < a_j，則I_i的數列可能包含a_j或不包含a_j 如果包含a_j，顯然I_i >= I_j + 1 => I_i > I_j 如果不包含a_j，那表示存在不包含a_j的遞增數列長度 > I_j => I_i > I_j 如果a_i > a_j，則D_i的數列可能包含a_j或不包含a_j 如果包含a_j，顯然D_i >= D_j + 1 => D_i > D_j 如果不包含a_j，那表示存在不包含a_j的遞減數列長度 > D_j => D_i > D_j 由於(I_i, D_i) = (I_j, D_j)必須要求I_i = I_j且D_i = D_j 所以只要I_i = I_j或D_i = D_j其中一個條件不滿足，就表示(I_i, D_i) = (I_j, D_j)不成立了因此證明了這個命題。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.56.10.112 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1508833748.A.3ED.html

推

q1qip123

10/24 17:34, 8年前 , 1^F

10/24 17:34, 1^F

→

q1qip123

10/24 17:37, 8年前 , 2^F

10/24 17:37, 2^F

→

q1qip123

10/24 17:37, 8年前 , 3^F

10/24 17:37, 3^F