Re: [理工] [ds] 96 清大資工

看板Grad-ProbAsk作者aoqq12 (阿任)時間15年前 (2011/01/28 13:38)推噓1(1推 0噓 10→)

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

請問一下關於第七題的証明他題目是說either or 那如果我舉一個 1 5 3 4 2 2^2+1個數可是他存在 1 3 4 與 5 4 2 長度為n+1的遞增與遞減書上的証明只證兩者皆非為錯? 並不代表他會只有其中一個成立啊兩者皆是呢? = ="如果我想錯請指正感謝 ※ 引述《boy5548 (小YO)》之銘言： : ※ 引述《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: 163.18.75.139

推

boy5548

01/28 13:49, , 1^F

01/28 13:49, 1^F

→

boy5548

01/28 13:50, , 2^F

01/28 13:50, 2^F

→

aoqq12

01/28 13:51, , 3^F

01/28 13:51, 3^F