如何判断一个10进制数值是否是3的倍数？

看完也不会有收获系列

如何判断一个给定的数值是否是3的倍数，可能大家对这个问题都会嗤之以鼻【不要用这种问题来侮辱我的智商惹.jpg ，取余就好啦】

if ( num % 3 == 0 )

{

// ……

}

但是如果这个数字的位数很多呢，有上万位什么的，这个时候直接用c++的 long long 或者 java 的long 就不行了。当然也可以用 java 的BigInteger 类，python的话当然更简单粗暴了，再不济还可以直接利用3的倍数的性质，直接用字符串读入然后每位加起来对三取余【大数取余】。

不过今天就介绍一种更加优雅的方法，当然从性能的角度上来说可能比不上上面说的，不过确实很漂亮。

接下来口胡开始

以下我将用num表示读入的数字，

1、什么是正则表达式？

这个方法是用正则表达式来进行匹配，上过java课大家也知道这是一个十分强大的字符串模式匹配工具。简单地说就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，然后用这个“规则字符串”用来表达对字符串的一种过滤逻辑，也就是匹配。下面开始进行详细的胡扯。

什么是正则表达式呢，正则表达式是由 regular expression 【简称 regex】翻译过来的，也就是“规则” “表达式”的意思，表达式也就是说它是一个字符串，而规则呢，由于我们是想用一段简要的表达式来描述一段复杂的字符串（或者说所有的字符串)，而这些字符串间存在共性，这个共性便是规则。因此我们直接称这个表达式/字符串为规则，那么这个规则需要有什么性质呢。

首先，这个规则里的每个字符都是一个特定的记号。对于表达式里的每一个特定的记号，都可以把一个特定的字符或者是空字符串认为是这一类型的记号的全部。比如表达式中的1表示的仅仅是字符“1”，而没有其他的字符与之对应。【估计这一句没描述清楚，不过没关系，不打紧】

其次，规则可以串联。串联是什么意思呢，假设我们有规则 regex1 和 regex2 ，对于一个字符串str，regex1 能够匹配 str 的一个前缀，而 regex2 能匹配 str 剩余部分的一个前缀，那么

我们把需要验证的数值当成字符串，作为输入，从左向右读进来，我们记 M 为当前已读入的字符串（即完整字符串从最左端开始到以某个下标 i 对应的字符串）对应的数值 mod 3 的结果，因此 M 只取0，1，2。那么我们就可以根据 M 的状态转移构建一个确定有穷状态自动机，长下面这个样子，其中 A 状态表示 M = 0的字符串集合【同时是开始和结束的状态】，B 表示 M = 1 的字符串集合， C 表示 M = 2 的字符串集合。

接下来我们只要把这个DFA转化为正则表达式就可以啦

如下所示：

其中由于A是3起始状态，因此空字符串也可以匹配A，然后我们基于以下的事实

其中*表示Y可以被多次匹配，所以对第一个方程我们有：

同理也可以化简另外的方程，然后我们进行一波展开代入化简，最终可以得到

A=[0369]* ( ( [147][0369]* | [258][0369]*[258][0369]* ) ([147][0369]*[258][0369]*)* ( [258][0369]* | [147][0369]*[147][0369]* ) | [258][0369]*[147][0369]* )*

这便是最终的正则表达式。至此，我们用正则表达式解决了如何判断一个数是否是3的倍数这一问题。

同样的，对于一个大整数，我们想判断这个数是否是一个整数p的倍数，我们也可以这样通过构造DFA从而找到正则表达式来解决，实际上和大数取模的想法是一致的。不过，随着p的增大，正则表达式的复杂度也会越来越高。另外，上述的正则表达式其实是不完善的，比如他会把一个空字符串判为3的倍数。

感谢你的收看，由于这个推文是暑假之前制作的，部分内容我自己现在好像都看不太懂了【，所以最后匆匆结尾，有兴趣的同学可以自行看一下正则，蛮好玩的一个东西。

• end •

文| 编辑 嗷嗷嗷

17计创☛☛☛

放肆而不做作的

班级分享大本营