Problem Solving►UVa

UVa 619 - Numerically Speaking

Contents

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

Problem

中文網址

Solution

非常非常麻煩的一題，在大數處理方面還好，但格式很麻煩。
先把字串轉為數字，這裡我用 deque 去存數字。
如果一開始是英文 則用 26 進位去算每一位數字 $x_1\times 26^0 + x_2\times 26^1 + …$ ，但進位時用 10 進位。一開始是數字則相反。(迭代法去計算次方比較快)

而在輸出方面如果一開始是英文，轉成數字後直接一位一位輸出即可。

一開始是數字則較為麻煩，因為轉成字母時，它沒有 0 ，而是 26 的 z。
這邊我把每一個存進去的數字 只要是等於零的代表它有進位 [26] -> [1][0] ，此時就要將它前一位減去 1 ，前一位也是零則借位直到可以減。
如此一來在輸出時 只要遇到 0 就輸出 'z'，其餘則輸出各對應的。putchar(num[i] ? ('a' + num[i] - 1) : 'z') 。

或許有更直接的方法…

Code

UVa 619
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<cstdio>
#include<cctype>
#include<deque>
#include<cstring>
using namespace std;

char str[100];
deque<int> num;
void solve();
int main()
{
    while (fgets(str, 100, stdin) && str[0] != '*')
    {
        str[strlen(str) - 1] = NULL;
        solve();
        num.clear();
    }

    return 0;
}
void solve()
{
    int len = strlen(str), i, k;
    int base, tar, tran, size = 1;
    if (isdigit(str[0]))
        base = 10, tar = 26, tran = '0';
    else
        base = 26, tar = 10, tran = 'a' - 1;

    //把字串轉成數字
    for (i = 0; i < len; i++)
    {
        if (i)
        {
            size = num.size();

            //迭代計算次方
            for (k = 0; k < size; k++)
                num[k] *= base;
            num[size - 1] += (str[i] - tran);
        }
        else//還沒有數字時
            num.push_back(str[i] - tran);

        //處理進位
        for (k = size - 1; k; k--)
            if (num[k] >= tar)
            {
            num[k - 1] += (num[k] / tar);
            num[k] %= tar;
            }

        //最高位
        while (num[0] >= tar)
        {
            num.push_front(num[0] / tar);
            num[1] %= tar;
        }
    }

    size = num.size();
    if (base == 10)//轉成英文字母
    {
        /*
        處理沒有 0 的問題:

        將每個 num[] 只要是 0 ，就將其前一位減一，如果前一位也是 0 就借位直到不為 0 的。
        */
        for (i = size - 1; i; i--)
        {
            if (!num[i])
            {
                for (int j = i - 1; j >= 0; j--)
                    if (!num[j])
                        num[j] = 25;
                    else
                    {
                        num[j]--;
                        break;
                    }
            }
        }

        int temp = 0;
        //如果第一位是 0 則代表借位借掉了(非 z)
        for (i = num[0] ? 0 : 1; i < size; i++)
        {
            putchar(num[i] ? ('a' + num[i] - 1) : 'z');//0 為 z，其餘要減 1 才是代表的字母
            temp++;
        }

        //格式處理
        for (; temp < 22; temp++)
            putchar(' ');
        i = 0;
        int count = len % 3;
        if (count)//多出來的
        {
            for (i = 0; i < count; i++)
                putchar(str[i]);
            if (len > 3)
                putchar(',');
        }

        count = 0;
        for (; i < len; i++, count++)
        {
            if (count == 3)
            {
                putchar(',');
                count = 0;
            }
            putchar(str[i]);
        }

        putchar('\n');
    }
    else//轉成數字(decimal)
    {
        printf("%-22s", str);

        int  count;

        count = size % 3;
        i = 0;
        if (count)//多出來的
        {
            while (count--)
                putchar('0' + num[i++]);

            if (size > 3)
                putchar(',');
        }

        count = 0;
        for (; i < size; i++, count++)
        {
            if (count == 3)
            {
                putchar(',');
                count = 0;
            }

            putchar('0' + num[i]);
        }
        putchar('\n');
    }
}