怕沉所以就另外開了這篇
if p then q
else r
化成真值表低卻是一模一樣
回答錯誤orz 真是抱歉
不過我有新的問題
因為其實我當初也是寫法是和 yan一樣的
因為找到了p=1 q=1 r=1 結果result是1
才想說自己答案是錯的
結果畫出truth table才發現原來答案也是有這性質
我想這不能當作程式語言單純來看(一開始就是犯這錯誤><
因為如果用程式語言的邏輯
p成立r是不會執行的
所以我應該把p=1<=>bar(p)=0
bar(p)=>r <=> 0=>1=1
這樣看才是正確的囉?
順便問一些組合的證明
92交大
離散第4版的p3-12範例二
他說明看得懂 但是沒辦法把A=nB+a0 和A!/(n!)^B兜起來
覺得這類組合證明常常都不是很好想到
有沒有什麼觀察的訣竅嗎?
常常都是看完解答才發現
! 阿~原來可以這樣想
以上問題勞請大家指教囉 謝謝~
ps.如果是跟演算法相關數學可以問嗎?~"~
像是prune and search中找第K小的數的方法
分成3set
任意取P
s1
k k在s1中
s2=p |s1|+|s2|>k K在s2中
S3>p
為什麼將n拆成celing(n/5) 後 自這5 set中取中位數
然後再把5個中位數在取中位數後得到的P
丟進去此演算法
可以保證每回合減少1/4 |S|?
想不通原因 可是這跟離散又沒有太大關聯 不太好意思問
但是這應該是卡在數學
如果有這類問題可以請教助教嗎?
4 則留言:
1. 如果用程式語言的角度來看, 可以想成是如果 p=1 成立的話, 則 q=1, 但是 r 有沒有成立都無所謂, 一樣會符合程式邏輯, 因為也有可能初值本來就是1, 所以p=1, q=1, r=1的結果會是 1
2. 看到證明是整數的, 也許就可以往組合證法的方向想看看, 至於要怎麼組合, 可以看看階乘數是怎麼分配的, 會比較好分堆
3. prune and search找第k小的數, 嚴格來說其實可以篩掉 3n/10 這麼多個數, 因為假設是將 |S|=n 個元素分成 m 堆 (m=n/5), 並且 c1,c2,...,cm 是這每一堆當中的中位數, p 是c1,c2,...,cm的中位數, 那麼假設 k>p, 則代表在那 m 堆當中約有 m/2 堆的中位數小於 p, 假設這 m/2 堆叫 S_1,...,S_m/2, 因為在每個S_i裡必定有 3 個數會小於等於S_i的中位數, 所以可以確定這些數全部都小於 p 所以小於 k, 也就是說這些點全部都可以被篩掉, 那麼被我們去掉的點總共會有 3(m/2) = 3n/10 這麼多, 若是p>k那也一樣, 只是大小反過來而已
很多人喜歡寫 1/4 * |S|, 原因可以看下方這示意圖:
* * * * | * * *
* * * * | * * *
* * *＊| * * *
----------------
* * * * | * * *
* * * * | * * *
圖中的每一行就是一堆, 由小排到大(就5個數做sorting), 其中中間那一列代表的就是每一行的中位數, 比較大的那個點"＊"就是中位數的中位數 p, 其中左上角那一塊的所有數皆會小於 p, 那些就是可以被篩掉的點, 共有約|S|/4這麼多個, 所以 T(n)=T(n/5)+T(7n/10)+cn
p.s. 演算法相關可以問, 畢竟離散有時也會考一點, 但希望不要太多, 全部都拿來問的話我可能會懶得看
謝謝助教 你3n/10的寫法我比較看得懂呢
圖反而不太了解他其意
不過關於程式語言還是感覺有些奇怪
if(P){q};
else r;
不是P不成立才會去執行r嗎?
就像若 p 則 q, 如果 p 不發生, 那 q 不管發不發生都會對, 寫程式也一樣, 如果 p=0 則 r=1, 但如果 p=1, r 不管是甚麼都會符合這段程式的邏輯, 因為 r 沒被執行不代表他原本一定不成立
也就是前面我搞不好先執行r了
只是沒寫出來也可以符合這邏輯
謝謝助教
我瞭解了:)
張貼留言