引言

今日头条看视频，求=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整除。

证毕。

C代码

#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;
}

结束

关注头条号“独角兽电波” #教育##百粉#