Re: [問題] 從二進位判斷數字是否被5整除 atoi PTT批踢踢實業坊

作者: atoi (atoi) 2017-03-02 05:00:05

如果input同樣都是二進位值，從右邊的bit開始往左看，這些bit換成10進值再除以5的餘數會分別是1, 2, 4, 3一直循環下去，那其實只要把bit為1的那些餘數做加總，最後一次除以5看餘數是否為0應該就行了。
不知這樣如何呢？

作者: ddavid (謊言接線生) 2017-03-02 07:32:00

這個問題在於，運算次數全等於把原值換成十進位再除以5求餘數，除了被除數值能小很多以外沒任何優點也不符合原題要的automata形式

作者: atoi (atoi) 2017-03-02 07:43:00

不用阿，不用換成10進制，1、2、4、3這樣循環不用換的是會整個所有bit掃一次沒錯啦哦對，我沒注意到要建立automata，在第一句話有提到，呵呵

作者: firejox (Tangent) 2017-03-02 12:36:00

如果input是以4n bit的型式，應該是可以建automata由右到左一次掃4bit這樣

作者: FRAXIS (喔喔) 2017-03-02 23:10:00

如果 4bit 可以那 1bit 也可以吧.. 只是要多一些 states

作者: outofyou 2017-03-03 16:24:00

00 01 10 11, 4個state就好了吧。 00補0 或10補1我錯了0_0

繼續閱讀