作者aoqq12 (阿任)
看板Grad-ProbAsk
標題Re: [理工] [ds] 96 清大資工
時間Fri Jan 28 13:38:24 2011
請問一下關於第七題的証明
他題目是說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
→ boy5548:到兩個都成立，那就已經包含在題意裡了? 01/28 13:50
→ aoqq12:可是either or不是兩者取其一嗎? 01/28 13:51
→ aoqq12:兩者皆成立不就不符合命題? 01/28 13:52
→ ai305428d:either.. or.. 不是a就是b 01/28 14:30
→ ai305428d:有一成立就成立 01/28 14:30
→ privatewind:資工所題目裡的either or = or 01/28 18:02
→ privatewind:但是現實中多指...either or 只有a 或b成立 01/28 18:03
→ privatewind:我也不知道為什麼資工的英文跟大家不太一樣... 01/28 18:04
→ aoqq12:原來如此= = 難怪我一直覺得不太完全 01/28 23:08