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

继续阅读