Re: [理工] [ds] 96 清大資工
※ 引述《ai305428d (可愛小小羅)》之銘言：
: http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/96/2101.pdf
: 請問第6題
: 選項(a)為什麼是F
: 第7題
: (f) T ...怎麼證?
7.(f)
令Ak為由ak開始之最長遞增字串，Bk為由ak開始之最長遞減字串。
利用矛盾證法，假設沒有長度為n+1之遞增及長度為n+1之遞減
=>1<=Ak<=n , 1<=Bk<=n for all k=1,2,...,(n^2+1)
=>(A1,B1),(A2,B2),...,(A(n^2+1),B(n^2+1))共有n^2可能
=>必存在i!=j，使得(Ai,Bi)=(Aj,Bj) 產生矛盾 故得證
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.27.126.62
推
01/27 22:44, , 1F
01/27 22:44, 1F
→
01/28 00:32, , 2F
01/28 00:32, 2F
討論串 (同標題文章)