题目描述:
给定一个长二进制串,求其除以3的余数
思路分析:
这里涉及到状态机,由于除以三的余数只可能是0,1,2。所以状态机就有三个状态。现在逐个遍历二进制串,初始余数为0,当遇到1时,状态转到1,遇到0时状态仍为0。对于状态1,判断分别遇到0和1的状态变换:遇到0,即余数为2转到状态2;遇到1,即余数为0转到状态0。可以发现,对于每个数在其后添加0相当于乘2,加1相当于乘2加1。
代码:
1 int numRest(string s)
2 {
3 int n = s.length();
4 int res=0;
5 for(int i=0; i<n; i++)
6 {
7 if(res==0)
8 {
9 if(s[i]=='0')
10 res=0;
11 else
12 res=1;
13 }
14 else if(res==1)
15 {
16 if(s[i]=='0')
17 res = 2;
18 else
19 res=0;
20 }
21 else
22 {
23 if(s[i]=='0')
24 res=1;
25 else
26 res=2;
27 }
28 }
29 return res;
30 }