Re: [問題]比大小求最小值

看板Python作者darkgerm (黑駿)時間12年前 (2013/11/05 19:55)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/4 (看更多)

※ 引述《Anisno (Anisno)》之銘言： : 我遇到一個問題，題目如下:給一個正整數，你必須找出遮罩M，滿足L<M<U且N or M : 運算後數字最大。 : 假如 : N=30951344 : L=201310 : U=3567891 : 求M=___ 要解的話最簡單就是 NM, M = max((i|N, i) for i in range(L+1,U)) 出來 NM 就是 N or M 值，M 即所求不過這樣複雜度是 O(U-L) 我想到一個 O(log(U)) 的解法以範例來說 U-L = 3366581 log(U) = 21.8 效率差距差不多就差這麼多我想到的解法是找出所有 "介於 U L 間，盡量多 1 或是盡量越大的數字" 稱為 candidates 再從這些 candidates 中取出跟 N 做 or 最大者實作出的 code 有點長，我直接加註解傳到貼 code 網站 http://ideone.com/p0YzSV 建意看以下的演算法可以搭配 code 會比較清楚 :) class Entry 欄位解釋： (等等演算法中 queue 裡的元素都是 Entry) M: 現在的 M 值，是 binary string 型式，是從高位元填下來的 uf: upperbound flag: 有 set 表示現在的 M 值已保證小於 U lf: lowerbound flag: 有 set 表示現在的 M 值已保證大於 L idx: 現在跑到第幾 bit (最高位元是 idx=0) 在開始前，先把 U L 轉成 binary string 而且長度對齊，L 短的部份就前面補 0 以下的 length = len(U) = len(L) # code 中 ub lb 是指 binary string 版的 U L 演算法 ====== 主要的概念就是從最高位元(idx=0)開始填 0/1，然後再往下走 idx=1 填 0/1 如此一來會展開一顆二元樹，葉子會有 2**length 個然後我們用 BFS 去走訪他，搭配剪枝可以砍掉大部份的狀況 # DFS 應該也可以，不過我 code 是用 BFS 實做的，效能應該差不多剛剛提到的 class Entry 可以想成是在每個節點的狀態在每次 main while 跑時會從 queue 中取一個狀態來走，然後把新的狀態加到 queue 中若取出的狀態，發現 lf uf 都已 set 了，表示已符合 L<M<U 那麼後面亂填也不會影響到 L<M<U，跟據題意當然全填 1 這樣 or 起來會最大 class Entry 的 get() 就是在後面補 1 用的，然後結果就會是一個 candidate 若取出的狀態，發現 idx >= length，表示 M 的長度已經填滿了表示尋找 L<M<U 失敗，那這條路就不理他 (continue) 再來就是演算法的重點，要怎麼作狀態轉移跟據 U[idx] L[idx] 的值會有 4 種狀況：00 01 10 11 我跟據等等解釋需要做一點順序的調整 U L 1. 1 0 2. 0 1 3. 0 0 4. 1 1 U L 1. 1 0 在這個狀況下 M 若填 1 就 "一定保證比 L 大" -> set lf M 若填 0 就 "一定保證比 U 小" -> set uf 因此會產生兩個新狀態："填 1 並 set lf" "填 0 並 set uf" 這裡，我們不能知道填1比較好還是填0比較好因為 set 的 flag 不同(set flag 可以想成是得到的保證) 後面可能會有不同結果 U L 2. 0 1 這個狀況比較神奇，因為 U > L 若在前面的 bit 全部都 U==L，那到這位發現 U[idx]==0 L[idx]==1 就不合前題 (因為我們是從高位走下來的) 因此會遇到這個狀態只有可能是前面出現過 1 0 (狀況1) 既然出現過狀況1，那 lf 或 uf 一定有其中一個被 set 所以分狀況 if lf is set: (已經保證比L大了) 為了滿足 M<U，這裡一定要填 0 if uf is set: (已經保證比U小了) 為了滿足 M>L，這裡一定要填 1 if lf ul are not set: 不可能出現在這個狀況下，由於要滿足 L<M<U，只會產生一個新狀態，而不會動到 flag U L 3. 0 0 這個狀態必需要考慮到 uf，因為 M<U，隨便填 1 的話可能會因此 M>U if uf is not set: 為了不能讓 M 超過 U，只能填 0 if uf is set: M 已經保證小於 U 了，這位可以高興的直接填 1 順便 set lf -> uf lf 皆 set，結束這條路 (後面也可以高興的全填 1) U L 4. 1 1 這個狀態與上個類似，因為 M>L，所以必需看 lf 行事 if lf is not set: 為了不能讓 M 小於 L，只能填 1 if lf is set: M 已經保證大於 L 了，這位...填 0 填 1 都可以填 0 --> set ul 結束這條路填 1 --> 什麼 flag 都不會動，繼續做為什麼不能像狀況3 直接結束這條路呢？因為 N[idx] 有可能在這位是 0，那麼這位填 1 可能會得到 N or M 比較大當然可以判斷 N 值多砍一點，不過現在效能已經改善很多，先不弄這麼複雜如此去走訪這顆樹，走完後會一堆 candidates 再一個個去測誰和 N or 起來最大就結束了 # 當然可以在一產生 candidate 時就做 N or M 然後記錄最大 # 這樣可以再省掉存 candidates 花的時間和空間，不過這跟演算法沒什麼關系 # 為了方便我就先沒這樣寫了XD ----------------------------------------------------------------- 效能的部份這個方法最壞就是整顆樹走完 O(U)，不過這是不可能的事由於剪枝的關系，每往下一層大約只有 2 條路能走到 (沒剪枝是 2**層數條) 雖然沒精算，不過我覺得效能差不多是 O(2*log(U)) = O(log(U)) 而實測也差不多是如此範例的 U=3567891 L=201310 爆搜要 3567891 - 201310 跑 3366581 次但用這個演算法 main while 只跑了 37 次，產生的 candidates 只有 12 個 2*log(3567891) = 43.5 差不多再少一點這樣程式是用 python2 寫的，從 stdin 依序讀入 U L N 要改 python3 只有 print 和 raw_input 需要動這個實作是把數字轉成 0/1 組成的 string 做的真的要加速的話可以直接用 bitwise，但這部分與演算法無關就不提了有問題或 bug 歡迎提出 :) -- 光明的背後是黑暗黑暗的背後還是黑暗由此可知黑暗 > 光明 Q.E.D. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.235.135 ※ 編輯: darkgerm 來自: 140.113.235.135 (11/05 22:47) ※ 編輯: darkgerm 來自: 140.113.235.135 (11/05 22:52)