Re: [問題] 從二進位判斷數字是否被5整除
看板Prob_Solve (計算數學 Problem Solving)作者march20時間16年前 (2008/10/04 18:02)推噓1(1推 0噓 2→)留言3則, 3人參與討論串4/6 (看更多)
※ 引述《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整除。
: 請問有人能解決這個問題嗎？
一個 5-state finite automaton 應該可以解決:
States : {s_i | 0 <= i < 5}: 目前輸入 mod 5 餘數為 i
Alphabet : {0, 1}
Start State : s_0
Accept States: {s_0 }
transition function :
| 0 | 1
---+---+----
s_0|s_0|s_1
s_1|s_2|s_3
s_2|s_4|s_0
s_3|s_1|s_2
s_4|s_3|s_4
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.136.255.51
※ 編輯: march20 來自: 71.136.255.51 (10/04 18:10)
→
10/04 18:13, , 1F
10/04 18:13, 1F
推
10/04 20:20, , 2F
10/04 20:20, 2F
→
10/06 14:48, , 3F
10/06 14:48, 3F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
