c/c++语言开发共享检查数字的逻辑可以被3整除吗?

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

这可能是一个面试问题。

谢谢。

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

    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) 

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

     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中应用它。 并且很幸运,因为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; } 

    快速燃烧。

    减去3,直到你

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

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

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

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

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

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

    只需使用for循环一次又一次减去3,看看你是否得到0.如果你得到负数而没有得到0然后你知道它不能被3整除

    打印一个可被3整除的计数序列,不带除法或模数运算符。

    注意计数顺序:

     00: 00(00) 01: 0001 02: 0010 03: 00(11) 04: 0100 05: 0101 06: 01(10) 07: 0111 08: 1000 09: 10(01) 10: 1010 11: 1011 12: 11(00) 13: 1101 14: 1110 15: 11(11) 16: 10000 17: 10001 18: 100(10) 19: 10011 20: 10100 21: 101(01) 

    请注意,那些可被3整除的数字的最后两位(括号中所示)在{00, 11, 10, 01}中循环。 我们需要检查的是计数序列的最后两位是否在序列中具有这些位。

    首先,我们开始匹配mask = 00和loop,而第一个数字没有遇到低两位00 。 当找到匹配时,我们会做(mask + 03) & 0x03 ,这将获得集合中的下一个掩码。 我们继续将下一个计数的最后两位与11匹配。 这可以通过((count & 3) == mask)

    代码是

     #include  int main (void) { int i=0; unsigned int mask = 0x00; for (i=0; i<100;i++) { if ((i&0x03) == mask) { printf ("n%d", i); mask = (mask + 3) & 0x03; } } printf ("n"); return 0; } 

    这不是一般的。 最好是使用@nightcracker建议的解决方案

    此外,如果您真的想要在不使用除法运算的情况下实现除法运算i。 我会告诉你看看非恢复分区算法,这可以在程序中完成,对位操作符进行大量的位操作。 以下是一些链接和参考。

    维基百科链接

    这是麻省大学的一个演示

    另请参阅Carl Hamacher的计算机组织,Zvonko Vranesic,Safwat Zaky

     number = abs(number) while (number > 0) { number -= 3; } return number == 0 

    假设n是有问题的数字,它是非负数。

    如果n为0,则可以被3整除; 否则n =(2 ^ p)*(2 * n1 + 1)并且n可以被3整除iff 2 * n1 + 1,如果有ak> = 0且2 * n1 + 1 = 3 *(2 * k) +1)iff n1 = 3 * k + 1 iff n1 = 1或n1> 1且n1-1可被3整除。所以:

     int ism3( int n) { for(;n;) { while( !(n & 1)) n >>= 1; n >>= 1; if ( n == 0) return 0; n-= 1; } return 1; } 

    知道数字是否可被3整除的最简单方法是将其所有数字相加并将结果除以3.如果数字的总和可以被3整除,那么数字本身可以被3整除。例如,54467565687是可被3整除,因为5 + 4 + 4 + 6 + 7 + 5 + 6 + 5 + 6 + 8 + 7 = 63,并且63可以被3整除。所以,无论数字有多大,你都可以找到它可以被3整除,只是加上它的所有数字,并从这个和的值减去3,直到你得到一个小于3的结果。如果这个结果为0,则和的值可以被3整除(原来的数字也是如此) ),否则总和不能被3整除(并且原始数字也不能被整除)。 它比原始数字(当然,特别是如果它是一个大数字)连续减去3并且没有任何分割要快得多。 嗯abraço一个待办事项。

    阿图尔

    如果二进制交替数字和为零,则数字可被3整除:

     bool by3(int n) { int s=0; for (int q=1; n; s+=q*(n&1), n>>=1, q*=-1); return !s; } 

    您可以使用用户反馈:

     int isDivisibleBy3(int n) { int areDivisibleBy3[] = {}; for(int i = 0; i < 0; i++) { if(n == areDivisibleBy3[i]) { return 1; } } return 0; } 

    当用户报告错误,指出可被3除数的数字未给出正确的结果时,您只需将该数字添加到数组中,并增加i与for循环条件中的数字进行比较。

    这很棒,因为你永远不必担心用户从不使用的数字。

    不要忘记在用户报告错误时添加unit testing!

      以上就是c/c++开发分享检查数字的逻辑可以被3整除吗?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注(计算机技术网)。

      本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

      如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/550202.html

      (0)
      上一篇 2021年1月14日
      下一篇 2021年1月14日

      精彩推荐