Problem Solving►UVa

UVa 763 - Fibinary Numbers

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

直接用 fib base 來進行相加，每一項皆為 1 或 0 ($1,2,3,5,8,\ldots$)，且不能讓連續兩個 1 存在。(連續兩個 1 可用下一位一個 1 表示)

處理進位時可以這樣:

(注意以下例子除了 dec 外，左邊皆為 LSB)

特例一，十進位的 2:

1 + 1 = 2 (要進位)
(LSB)2 => (LSB)01

特例二，十進位的 4:

010 + 010 = 020 (要進位)
(LSB)020 => (LSB)101

1 2 3
0 2 0 => 4(dec)

可換成

1 2 3
1 0 1 => 4(dec)

正常情況:

0001 + 0001 = 0002 (要進位)

1 2 3 5
0 0 0 2 => 10(dec)

換成

1 2 3 5 8
0 1 1 1 0 => 10(dec)

再換

1 2 3 5 8
0 1 0 0 1 => 10(dec)

(LSB)0002 => (LSB)01001

幾個要注意的點:

  • 如果進位有增加位數的情況。
  • 每次進位完，因為有可能影響前面已檢查過的位數，所以要再回去檢查一次。
  • 輸入輸出的LSB,MSB

Code

UVa 763
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<cstring>
#include<algorithm>

int ans[105];
inline int carry(int idx)
{
    int ret;
    if (!idx)//(LSB)2 => 01
    {
        ans[1]++;
        ret = 1;
    }
    else if (idx == 1)//(LSB)020 => 101
    {
        ans[2]++, ans[0]++;
        ret = 0;
    }
    else//(LSB)0020 => 1001
    {
        ans[idx + 1]++, ans[idx - 2]++;
        ret = idx - 3;
    }

    ans[idx] -= 2;

    return ret;
}
int main()
{
    char str1[105], str2[105];
    int i;
    bool first = true;
    while (scanf("%s%s", str1, str2) != EOF)
    {
        std::fill(ans, ans + 105, 0);

        int len1 = strlen(str1), len2 = strlen(str2);
        for (i = 0; i < len1; i++)
            ans[i] = str1[len1 - i - 1] - '0';

        for (i = 0; i < len2; i++)
            ans[i] += str2[len2 - i - 1] - '0';

        int cont = 0, len3 = std::max(len1, len2);
        for (i = 0; i < len3; i++)//ans[0] 為 LSB
        {
            if (ans[i] >= 2)
            {
                if (i == len3 - 1)//多一位數
                    len3++;

                i = carry(i) - 1;//i 要從有變動的在開始檢查
                cont = 0;
                continue;
            }
            
            if (ans[i])
                cont++;
            else
                cont = 0;

            if (cont == 2)//處理連續兩個 1 ，進位到下一格
            {
                if (i == len3 - 1)//多一位數
                    len3++;

                cont = 0;
                ans[i + 1]++;
                ans[i - 1] = ans[i] = 0;
            }
        }

        if (first)
            first = false;
        else
            putchar('\n');

        for (i = len3 - 1; i >= 0; i--)//從MSB開始輸出
            putchar(ans[i] + '0');
        putchar('\n');
    }

    return 0;
}