图形化计算大数对N取余
几个月前，在quora上看到一个问题，关于如何判定一个整数能否被7整除，有一个回答很有趣。回答中给出了下面这个图。具体的判定方法是：给出一个十进制的整数（如413），从第一位（4）开始，由下方的白色点出发，沿着黑色箭头走4步（此时到达圆圈内部左上方那个点）；然后沿白色箭头走一步（到达圆圈内部下方的点），转到下一位（1）；再沿着黑色箭头走1步（因为这一位的数字是1），然后沿着白色箭头走一步（此时到达圆圈内部左上方点），转到下一位；最后，沿着黑色箭头走三步（因为最后一位数字是3）。若最终回到白点，则这个数字可以被7整除。
总结方法：从第一位数字开始，从下方白点出发，沿黑色箭头走n步（n为当前位的数字），然后沿着白色箭头走一步，跳转到下一位；如此循环，直到最后一位数的黑色箭头走完，这时不必再走白色箭头的一步。若回到下方的白点，则说明能被7整除，若不能，则说明不能被整除。
以上方法来自：http://blog.tanyakhovanova.com/?p=159
很有趣，多尝试几个数字发现的确是成立的。但是，为什么会是这样呢？这个图的奥秘何在？
我们来观察一下这个图，发现刚好有7个点，那不妨按照黑色箭头的顺序标记为[0-6]好了。至于为什么要这么标记呢？通过代入[0-10]之间的数字，观察发现，这些点的顺序可能表示的就是数字除以7后的余数。
然后来观察白色箭头的方向：[0→0]，[1→3→2→6→4→5→1]。我们知道，对于一个一位数（0-9）来说，行进n步之后停留的点代表的是n除以7的余数。那么，结合刚才的一个重要步骤：沿白色箭头走一步，然后跳转到下一位。可以猜想，白色箭头表示的是当前的余数左移一位（十进制）后，除以7 的余数。来验证一下：[10 % 7 == 3]，[30 % 7 == 2]，[20 % 7 == 6]……的确是符合猜想的。
发现以上规律后，可以知道，按箭头进行的操作实际上是对所给的数按照每一位进行对7取余，乘以10，对7取余数，加上后一位，再对7取余数，如此循环。最终得到的结果（停留点的编号）是这个整数除以7的余数。这个操作的依据是：
明白原理之后，就可以构造任意N的类似图形了。以13为例，先画出并排的13个点，编号分别是[0-12]。然后依次画出13个黑色箭头，顺序是[0→1→2→3→4→5→6→7→8→9→10→11→12→0]。接下来计算白色箭头的方向，可能是几个分离的环，对于13来说，分别是：[0→0]，[1→10→9→12→3→4→1]，[2→7→5→11→6→8→2]。根据计算结果，将白色箭头补上。最后，将得到的图形进行拓扑变形，变形成较为规律和漂亮的形状即可。
Post Info
- Copyright Notice: Creative Commons BY-NC-ND 3.0
