[問題] 從二進位判斷數字是否被5整除

看板Prob_Solve作者 (neverfly)時間15年前 (2008/10/01 14:08), 編輯推噓2(2推 0噓 2→)
留言4則, 2人參與, 最新討論串1/6 (看更多)
我想要建一個automata，可以輸入二進位的值， 如果該值能被5整除就接受。 但是我想了很久，實在想不出來二進位下，能被5整除的數有什麼特性。 列了前幾個出來 101 1010 1111 10100 11001 11110 100011 101000 101101 110010 110111 111100 1000001 1000110 1001011 1010000 1010101 1011010 1011111 1100100 …… 只發現了有每八個，末三碼會重覆這個特性， 不過似乎還是不能直接檢查出來一串二進位的值是否被5整除。 請問有人能解決這個問題嗎？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.169.80.216
推
10/01 14:21, , 1F
被五除餘一, 後面多一個 0 就會變餘二, 多一個 1 則是餘三
10/01 14:21, 1F
→
10/01 14:22, , 2F
利用 2n 或 2n+1 mod 5 去設計你的 transition
10/01 14:22, 2F
推
10/01 19:43, , 3F
每 2 bits 分開，對 5 的餘數分別是 -1,+1,-1,+1
10/01 19:43, 3F
→
10/01 19:43, , 4F
把 +1 / -1 分別加總，看差值是不是 5 的倍數
10/01 19:43, 4F
‣ 更多 neverfly 的文章
文章代碼(AID): #18unFRY_ (Prob_Solve)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 1 之 6 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共6篇)
‣ 更多 neverfly 的文章
文章代碼(AID): #18unFRY_ (Prob_Solve)