检查号码的逻辑可以被3整除吗？

Question

不使用%,/或*,我必须找到否.可以被3整除吗？

这可能是一个面试问题.

谢谢.

Answer 1

有各种方式.最简单的是非常明显的:

int isdivby3(int n) {
    if (n < 0) n = -n;

    while (n > 0) n -= 3;

    return n == 0;
}

但我们可以改善这一点.任何数字都可以这样表示:(","表示包括范围):

Base2 (AKA binary)
(0,1) + 2*(0,1) + 4*(0,1)

Base4
(0,3) + 4*(0,3) + 16*(0,3)

BaseN
(0,N-1) + N*(0,N-1) + N*N*(0,N-1)

现在的诀窍是,当且仅当基数的digitum x可被整除时,数字n-1才能被整除.这个技巧以9为人所熟知:xnn-1

1926 = 6 + 2*10 + 9*100 + 1*1000
6+2+9+1 = 8 + 1*10
8+1 = 9 thus 1926 is divisible by 9

现在我们也可以在base4中应用3.幸运的是,因为4是2的幂,我们可以进行二进制按位运算.我用的是符号number(base).

27(10) = 123(4)
Digitsum
12(4)
Digitsum again
3(4) = Divisible!

现在让我们把它翻译成C:

int div3(int n) {
    if (n < 0) n = -n;
    else if (n == 0) return 1;

    while (n > 3) {
        int d = 0;

        while (n > 0) {
            d += n & 3;
            n >>= 2;
        }

        n = d;
    }

    return n == 3;
}

快速燃烧.

Answer 2

减去3直到你

命中0 - 数字可以被3(或)整除

得到一个小于0的数字 - 数字不可分割

 if (number > 0)
 {
        while (number > 0)
        {
            number -= 3;
    }
}
else if( number < 0)
{
    while number < 0:
        number += 3
}
return number == 0

Answer 3

这是一个相当有效的大数字算法.(不是很有效,但考虑到约束,这是合理的.)

使用sprintf将其转换为字符串,每个数字转换回数字.加上数字.如果你想出3,6或9,它可以被3整除.除了10以外的任何其他东西,它不是.任何超过9的,递减.

例如,为了测试数字813478902你要字符串化,然后添加数字得到42,添加这些数字得到6,所以它可以被3整除.