算法面试题之判断整数是否可以被3整除

一个整数，知道位数，如何判断它是否能被3整除，不可以使用除法和模运算。

小学奥数里面学过，如果一个数字各个位上的和是3的倍数，那么它也能被3整除。拿999做例子来看：

999各个位上的和是27，27可以被3整除，但是不能用mod运算，如何判断27可以被3整除呢？我们继续递归的去求27个个位上的和：2+7=9，此时，它变成了一个一位数，一位数能被3整除的只有3，6，9三个数字，用if语句就可以表达，因此，我们可以这么做：

bool judge(int i)
{
	if (i<10)
	{
		if (i==3 || i==6 || i==9) return true;
		return false;
	}
	int sum=get_sum(i); //求i各个位上的和
	return judge(sum);
}