Re: [問題] 有關演算法的問題
假設所有傳回值大部分都是壞的呢？
起始解傳回兩個 F ，你要踢哪個？兩個 F 表示至少一個壞的。
你原文抽出一個跟一對混淆在一起，搞不清楚你是寫哪種。
(註: TF FT 僅為反序，只論 TF)
1)傳回 T T 可能是全好或全壞。
2)傳回 T F 可以保證 F 一定是壞的，可以踢掉，但 T 則不一定是好壞。
3)傳回 F F 可以保證必有一個壞的。
你之前的說法看不出 2 要怎樣處理，因為你寫
: 只要有其中一個報告 bad, 則這對拿起來放在一邊.
: 然後在晶片堆拿下一個, 繼續做.
拿起一對，則下一步應該是在晶片堆拿下一對。
可以確認：
1 是一堆，3 是一堆
2 不知道要全部塞到 3 還是一半到 3 。
那怎麼看最後剩下來的堆 1 跟堆 3 都是混雜著好壞。
假設只把標記為 F 得丟到 堆 3 ，每次只丟一個，相同丟 B，則
F F
T T
兩種情況都會把不確定到底誰是 F 誰是 T 的狀況亂分堆。
由於只有 2 可以有效減少晶片數，所以第一次分組完會得到：
1) T T (i 組)
2) T (j 個)
3) F F (k 組)
後面該怎樣組合能最快不一定，但是
2 跟 3 組合踢掉 F ，把剩下來的分配回 1, 2, 3 各組。
若 2 有剩，則 2 兩兩互組分回 1, 2, 3 。
若 3 有剩，則用 1 的 T T 依序去配，踢掉 F 。
循環最後可能得到除了 1 外，剩下單獨的 T , F 或 F F ，最後再處理。
1 由於兩兩為一組，必為 TT 或 FF ，所以開始抽選序號為 2 的次方倍來比對。
12 34 56 78 ...
抽 24 68 ... 比對，
1)傳回 TT 表示 12 34 必為 TT TT 或 FF FF
2)傳回 TF 表示 12 可能為 TT 或 FF ，但 34 必為 FF ，踢掉 34
3)傳回 FF 表示 12 34 可能為 TT FF 或 FF TT 或 FF FF
(注意，邏輯又回到上面的單個的情形)
最後 1 是綁定的，變成 4 個一組：
1234 5678 ....
抽 48 ... 比對，
1)傳回 TT 表示 1234 5678 必為 TTTT TTTT 或 FFFF FFFF
2)傳回 TF 表示 1234 可能為 TTTT 或 FFFF ，但 5678 必為 FFFF ，踢掉 5678
3)傳回 FF 表示 1234 5678 可能為 TTTT FFFF 或 FFFF TTTT 或 FFFF FFFF
可以看出邏輯一直在循環，只是每次循環的邏輯下，1 每組的個數會成 2 的次方倍增加。
1, 2, 4, 8, 16, 32, 64, ...
由於有一個條件為好的比壞的多，組 1 綁定的個數接近 1/2 的總個數時，才可以停止。
而剩下零散的組數因為已經確認了有好的了，要踢掉也很容易。
原先題目中最難決定是必為好的的那個或那組是哪個。
==> 本文由 "Alien <adrianshum.bbs@ptt.cc>"
> 於 news:4ZThVX%248ne%40ptt.cc 發表
> ※ 引述《璉璉 <devil@tainan.com.tw.x>, 看板: Programming》之銘言：
> : 這個能用的前提是你第一個拿出來的要是好的。
> : 結果不可信表示可能回傳是好的或壞的，並非是壞的就會傳回好的。
> 並不是
> 你細心想一下, 就算我第一個拿出來的是壞的, 我逐一的去
> 比對, 總會遇到好的(基於好晶片會比壞晶片多的事實). 這
> 樣的組合之下, 好的晶片會回報我手上的晶是壞的.
> : 所以會造成你分的兩堆根本就不可信，因為每一堆都是混雜了好的或壞的。
> 你也錯了.
> 到最後, 剩下的一堆一定是好晶片.
> 之前逐一比對之後放在一邊的那堆才是好壞混雜
> 你再細心想一想吧.
> : 此外，實務上不會這樣做，要這樣做只要開始之前準備一個好的就行了。
> : 會有這種命題就是為了解決實務上降低測試成本用的，所以才需要工程師思考。
> 我不知他的命題的本意是什麼, 我只是根據他給的
> 資料來找出可行的答案. 我才不管他實務上怎樣做.
> btw, 實務上真的有那麼多這種用一種東西來檢查與
> 自己同類的東西的情況嗎?
> : ==> 本文由 "Alien <adrianshum.bbs@ptt.cc>"
> : > 於 news:4ZTPeM%246nc%40ptt.cc 發表
> : > 隨便從晶片裡抽一個出來, 和剩下的逐一比對.
> : > 只要有其中一個報告 bad, 則這對拿起來放在一邊.
> : > 然後在晶片堆拿下一個, 繼續做.
> : > 直到有一顆晶片, 和其他剩下的所有晶片檢查結果都是
> : > good. 這時, 剩下的所有晶片都是都是好的.
> : > 再用這些好的晶片來檢查之前放在一邊的那堆就好了.
> : > 這方法一定要肯定好的比壞的多才能成立
> : > alien
>
--
風禹科技驗證有限公司 ASP.NET Web News Reader 0.2.7 UTF-8 Beta
網站地圖 http://tlcheng.twbbs.org/wwwmap.htm
流域防洪/區域水資源/徐昇網/玫瑰圖/語音通訊 文章與程式
Basic/Fortran/Windows API/.Net/輔助說明檔 原始碼、文章與討論
微軟程式設計、系統管理使用新技術論壇討論區，網友回覆後即時簡訊、電子郵件通知：
MSDN: http://forums.microsoft.com/msdn-cht/default.aspx?siteid=14
TechNet: http://forums.microsoft.com/technet-cht/default.aspx?siteid=23
--
ASPNET News Reader http://tlcheng.twbbs.org/News/Reader.aspx
RSS 2.0 http://tlcheng.twbbs.org/News/rss2.aspx?Action=List&Newsgroup=tw.bbs.comp.language
討論串 (同標題文章)