整除7碾转算法的数学证明和代码实现

今日头条看视频，求=4391。用了一种有趣的整除7碾转算法，分享给各位小伙伴，同时给出证明和C代码实现。

设十进制整数为n，

（1）判定n是否被7整除；

（2）如果能判定，则得出结论，否则到步骤3；

（3）将n的末尾数(设为m)与其他数（设为r)分离，得到m和r。

（4）用m和r求得新数x, 公式为x = r - 2m。

（5）回到步骤1，判定x。

举例说明。试试1414。假设我们不能一眼看得出结论，那么尝试用上述算法。
（1）将末尾数分离，得到141和4。然后前者减去后者的两倍，即141 - 8，为133。
（2）如果能判断出是否被7整除，则得出结论。这里133还不明显的话，则重复上述步骤。
（3）将133截取末尾数，得到13和3。 13 - 3 X 2 = 7。 显然7能被7整除，

于是得出结论，1414能被7整除。

再来一个例子，1234。

123 - 4 X 2 = 115。 11 - 2X5 = 1。1不能被7整除，因此1234不能被7整除。

设十进制整数n表示为r和m，使得 n = 10r m。

有10r m = 7r 7m 3r - 6m = 7(r m) 3(r - 2m)

由此，n是否被7整除，转换为检查7(r m) 3(r-2m)是否被7整除。显然，7(r m)被7整除，那么，r-2m决定了是否能被7整除，假如r-2m能被7整除，则n被7整除，反之，r-2m不被7整除，则n不被7整除。

证毕。

#include <assert.h> bool is_divided_by_7(int n) { if (n < 0) n = -n; while (n > 10) { int r = n / 10; int m = n - 10 * r; m = m << 1; n = r - m; } return n == 0 || n == 7; } int main() { assert(is_divided_by_7(1414)); assert(!is_divided_by_7(1234)); assert(is_divided_by_7(7)); assert(!is_divided_by_7(1)); assert(is_divided_by_7(0)); assert(is_divided_by_7(21)); assert(!is_divided_by_7(23)); return 0; }

结束

关注头条号“独角兽电波”