作者yauhh (舉杯邀鼠長 共飲長江奶)
看板Prob_Solve
標題Re: [問題] 從二進位判斷數字是否被5整除
時間Fri Oct 3 22:10:13 2008
※ 引述《neverfly (neverfly)》之銘言：
: 我想要建一個automata，可以輸入二進位的值，
: 如果該值能被5整除就接受。
: 但是我想了很久，實在想不出來二進位下，能被5整除的數有什麼特性。
: 列了前幾個出來
: 101 1010 1111 10100 11001 11110 100011 101000
: 101101 110010 110111 111100 1000001 1000110 1001011 1010000
: 1010101 1011010 1011111 1100100 ……
: 只發現了有每八個，末三碼會重覆這個特性，
: 不過似乎還是不能直接檢查出來一串二進位的值是否被5整除。
: 請問有人能解決這個問題嗎？
我的想法:
由高位往低位方向讀資料,例如 11001 = 25, 讀 1 -> 1 -> 0 -> 0 -> 1 順序.
狀態分為接受與不接受,
此外,狀態附帶一個 n 值代表根據已經讀入的部份二進位數值決定的十進位數值,
例如, 對 11001 已讀入 110 時, 狀態的 n 值是 6.
輸入的意義是,遇到 0, 代表 n*2; 遇到 1, 代表 n*2+1
Transition 有三個項目要關心: 1) 讀入的二進位數字, 2) 狀態 n 的求值,
3) 結果接受或不接受, 以下用 (t1, t2, t3) 表達三個項目.
Automata為:
(1, n, F)
[unacceptable] <------(1)-------- S:[accepted]
|^ |^ | | ^ ^ |^
|| || +-----------(0)-------------+ | ||
|| || | (0, n*2, (n*2)%5 = 0) | ||
Ｕ || +-------------(1)-----------+ ||
(0, n*2, (n*2)%5 /= 0) (1, n*2+1, (n*2+1)%5 = 0)
|| ||
Ｕ Ｕ
(1, n*2+1, (n*2+1)%5 /= 0) (0, n, T)
S是起動狀態, 起動時 n = 0.
這個automata有下列特性:
1. 0 整除 5.
2. 任一unacceptable狀態遇到下一個 0 一定是unacceptable. (不確定)
也就是,任一unacceptable狀態只有遇到下一個 1 才可能accepted.
3. 任一accepted狀態遇到下一個 0 一定是accepted.
4. 任一accepted狀態遇到下一個 1 一定是unacceptable.
(以上特性是畫出具體的 0,1,2,...,25 狀態機而觀察到的)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.111.154
※ 編輯: yauhh 來自: 218.160.111.154 (10/03 22:18)
1F：推 FRAXIS:用5個state 分別代表現在讀入的字串除5的餘數為 0~4 就好啦 10/04 07:00
2F：→ yauhh:不同的概念會畫出不同的automata 10/04 10:45
3F：→ yauhh:重點是你要說明一套automata能不能講得完整,而不必考慮是否 10/04 10:46
4F：→ yauhh:符合別人的概念 10/04 10:46
※ 編輯: yauhh 來自: 218.160.111.154 (10/04 10:55)
5F：→ yauhh:用5個狀態的麻煩是,你一個狀態可能連到其他四個狀態,傳遞線 10/04 11:15
6F：→ yauhh:要畫很多; 而我的只判斷留在原地或跳別的狀態,傳遞線很少. 10/04 11:17
※ 編輯: yauhh 來自: 218.160.111.154 (10/04 11:21)
7F：推 ledia:這不是 automata 了吧, 多了 n 10/04 21:51
8F：→ yauhh:就當作side-effect好了,本來沒多嚴謹去想這東西 10/04 22:34