51nod1491 黄金系统

Description

现在给出两个黄金系统下面的数字，请比较他们的大小。

Input

单组测试数据。
第一行有一个字符串A。
第二行有一个字符串B。
按照a0到an的顺序输入。
他们都是非空串，可能有前导0，并且只有0和1组成，长度不超过100000。

Output

如果A>B，输出>；
如果A=B，输出=；
如果A<B，输出<；

Input示例

00100
11

Output示例

解题思路

q2= 1 + q;遇到011时进位成100，从低位往高位进位，进位到不能进位为止，然后去掉前导零，判断大小即可。

Code

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define MAXN 100010
 7 using namespace std;
 8 char A[MAXN],B[MAXN];
 9 void solve(char * str)
10 {
11     int len = strlen(str);
12 
13     for(int i = len; i>0; i--)
14         str[i] = str[i-1];
15     str[0] = '0';
16     len++;
17     for(int i = len - 3; i >=0 ; i--)
18     {
19         if(str[i] == '0' && str[i + 1] == '1' && str[i+2] == '1')
20         {
21             str[i] = '1', str[i+1] = '0', str[i+2] = '0';
22         }
23     }
24     int s;
25     for(int i = 0; i < len;)
26         if(str[i] == '0') i++;
27         else
28         {
29             s = i;
30             break;
31         }
32     int i,j;
33     for(i = 0, j = s; j < len; i++,j++)
34         str[i] = str[j];
35         str[i] = '';
36 
37 }
38 
39 int main()
40 {
41     scanf("%s%s",A,B);
42     solve(A);
43     solve(B);
44     int lenA = strlen(A),lenB = strlen(B);
45     if(lenA ==lenB)
46     {
47         int i;
48         for(i = 0; i < lenA; i++)
49         {
50             if(A[i] == '1' && B[i] == '0')
51                {
52                   puts(">");
53                   break;
54                }
55             else if(A[i] == '0' && B[i] == '1')
56                {
57                    puts("<");
58                    break;
59                }
60         }
61         if(i == lenA)
62             puts("=");
63     }
64     else
65     {
66         lenA < lenB ? puts("<") : puts(">");
67     }
68     return 0;
69 }