检查二进制流中的可除性-yiteyi-C++库

二进制数流即将到来，任务是告诉到目前为止形成的数字可以被给定的数字n整除。在任何给定的时间，你都会得到0或1，并判断由这些位组成的数字是否可以被n整除。

null

一般来说，电子商务公司会问这类问题。这是在微软的采访中问我的。实际上这个问题有点简单，面试官把n改为3。

方法1（简单但会导致溢出）：

                     /* Simple implementation of the logic,                   
                                         without error handling compiled with                   
                                         Microsoft visual studio 2015 */                   
                     void                               CheckDivisibility2(                               int                               n)                   
                     {                   
                                         int                               num = 0;                   
                                         std::cout <<                               "press any key other than"                   
                                         " 0 and 1 to terminate "                               ;                   
                                         while                               (                               true                               )                   
                                         {                   
                                         int                               incomingBit;                   
                             
                                         // read next incoming bit via standard                   
                                         // input. 0, 00, 000.. are same as int 0                   
                                         // ans 1, 01, 001, 00..001 is same as 1.                   
                                         std::cin >> incomingBit;                   
                             
                                         // Update value of num formed so far                   
                                         if                               (incomingBit == 1)                   
                                         num = (num * 2 + 1);                   
                                         else                               if                               (incomingBit == 0)                   
                                         num = (num * 2);                   
                             
                                         else                   
                                         break                               ;                   
                                         if                               (num % n == 0)                   
                                         std::cout <<                               "yes "                               ;                   
                                         else                   
                                         std::cout <<                               "no "                               ;                   
                                         }                   
                     }                   

这个解决方案的问题是：溢出怎么办。因为0和1将继续出现，形成的数字将超出整数的范围。

方法2（不会导致溢出）： 在自动机中使用的技术

为了实现这项技术，我们需要观察一个二进制数的值在被0或1追加时是如何变化的。

让我们举个例子。假设你有二进制数1。如果加上0，它将变为10（十进制为2），表示前一个值的2倍。如果加上1，它将变成11（十进制为3），是前一个值+1的2倍。

它如何帮助获得剩余部分？ 任何数字（n）都可以写成m=an+r的形式，其中a、n和r是整数，r是余数。所以当m乘以任意数时，余数就是。假设m乘以x，那么m将是mx=xan+xr。所以（mx）%n=（xan）%n+（xr）%n=0+（xr）%n=（xr）%n；

我们只需要对余数进行上面的计算（当数字加上0或1时计算数值）。

When a binary number is appended by 0 (means 
multiplied by 2), the new remainder can be 
calculated based on current remainder only.
r = 2*r % n;

And when a binary number is appended by 1.
r = (2*r + 1) % n;

                     // C++ program to check divisibility in a stream                   
                     #include <iostream>                   
                     using                               namespace                               std;                   
                             
                     /*  A very simple implementation of the logic,                   
                                         without error handling. just to demonstrate                   
                                         the above theory. This simple version not                   
                                         restricting user from typing 000, 00 , 000.. ,                   
                                         because this all will be same as 0 for integer                   
                                         same is true for 1, 01, 001, 000...001 is same                   
                                         as 1, so ignore this type of error handling                   
                                         while reading just see the main logic is correct. */                   
                     void                               CheckDivisibility(                               int                               n)                   
                     {                   
                                         int                               remainder = 0;                   
                                         std::cout <<                               "press any key other than 0"                   
                                         " and 1 to terminate "                               ;                   
                                         while                               (                               true                               )                   
                                         {                   
                                         // Read next incoming bit via standard                   
                                         // input. 0, 00, 000.. are same as int 0                   
                                         // ans 1, 01, 001, 00..001 is same as 1.                   
                                         int                               incomingBit;                   
                                         cin >> incomingBit;                   
                             
                                         // Update remainder                   
                                         if                               (incomingBit == 1)                   
                                         remainder = (remainder * 2 + 1) % n;                   
                                         else                               if                               (incomingBit == 0)                   
                                         remainder = (remainder * 2) % n;                   
                                         else                   
                                         break                               ;                   
                             
                                         // If remainder is 0.                   
                                         if                               (remainder % n == 0)                   
                                         cout <<                               "yes "                               ;                   
                                         else                   
                                         cout <<                               "no "                               ;                   
                                         }                   
                     }                   
                             
                     // Driver code                   
                     int                               main()                   
                     {                   
                                         CheckDivisibility(3);                   
                                         return                               0;                   
                     }                   

输入：

输出：

Press any key other than 0 and 1 to terminate 
no 
no 
no 
no 
yes

相关文章： 基于DFA的部门检查流是否是3的倍数

本文由 普尼特 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章