※ 引述《dyndns.bbs@bbs.wretch.cc ()》之銘言：
: 0000000
: 0000001 ==> 這樣就合併成000000*
: 0000010
: 0000011 ==> 這樣就合併成000001*
: 由上面兩個 ==> 這樣就合併成00000**
: 0000100
: 0000101 ==> 000010*
: 0000111 ==> 0000111
: 0001000
: 0001010
: 下面還有一堆這樣的2進位的值,我要檢查並簡化規則
: 這樣的簡化有沒有一個專有的名詞????
: 還有請問一下有什麼演算法讓我能快速簡化它???
我自己的一個點子... 8421法 (亂取名字 XD)
假設有一串數字:18,20,32,55,要化簡為pattern,
以2^n~(2^(n+1)-1)為分割區段,每個分割區段大致擁有同樣的pattern,
而預設的pattern為xxxxxxxxxxxxxxx.
在pattern中,
0,1是確定為單值bit,
*則是確定為二相值bit,
而x代表未知且可接受改變值的bit.
上述數列中,
18與20都在16~31分割區段裏,共有pattern大概是1xxxx,
32,55位於32~63分割區段裏,共有pattern大概是1xxxxx.
因為目前數列跨越二個區段,可以確定整體pattern大概是**xxxx.
第五,六順位的LSB是*.
後面4bit不能確定,把它們再做一次.
要把每個數字都減掉它所屬分割區段的基數: 18-16, 20-16, 32-32, 55-32,
變成子數列2,4,0,23,子數列與原數列一一對應.
子數列依分割區段判斷:
0,2,4各佔一個區段.
23在16~31區段,pattern是1xxxx,無濟於事.
再做一次: 23-16 = 7,介於4~7,pattern大概是1xx.
此例整體來講,依序產生的pattern為:
未檢查: xxxxxxxxxxxxxxx
原數列: **xxxx 覆寫結果: **xxxx
子數列: 0000 覆寫結果: **0000
0010 覆寫結果: **00*0
0100 覆寫結果: **0**0
0111 覆寫結果: **0***
結果: **0***
後產生的往前覆寫,覆寫的規則大概是:
1. 前者bit為1: 後者是0或*,就覆寫為*. 後者為1或x不影響.
2. 前者bit為0: 後者是1或*,就覆寫為*. 後者為0或x不影響.
3. 前者bit為*: 後者為任何符號,通殺,不影響.
4. 前者bit為x: 後者為1,0,或*,都覆寫為後者. 後者為x不影響.
5. 最後把pattern剩下的x都換成0.
這樣做不知道快不快.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.139.92.115
※ 編輯: razor 來自: 220.139.92.115 (02/03 19:20)
※ 編輯: razor 來自: 220.139.92.115 (02/03 19:23)
※ 編輯: razor 來自: 220.139.92.115 (02/03 19:32)