HJ95 人民币转换 题解

by 限时烟花

抽丝剥茧

这道题本身是一个偏向应用的题目，整体的要求是能够顾全阿拉伯数字表达和中文大写表达之间的转换关系。

格式比较重要：

1. 输出固定需要以“人民币”开头；
2. 小数点大致可以等价于“元”，但是并不是简单的取代关系；
3. 连续的零并不是需要每个都翻译的，需要按照情况进行处理。

总体来说就是中文的规则比较零碎，需要仔细整理一下小学学习时的规则。

化繁为简

虽然中文的规则看上去比较零碎，并且条条框框比较多，但是我们也可以一层层地分析问题，从而能够构建一些简化问题的方法。本质上并没有想象中那么复杂。 首先我们知道阿拉伯数字和中文大写语法之间最大的差异就是逻辑上的顺序。阿拉伯数字的表达式本身是没有“千百万”的含义的，只是一串数字的连结，表达中只需要从前往后书写就可以。但是中文表述中，给每一位数字含义，并且每一位数字的含义是基于它相对低位的位置来确定的。所以这里就存在一个逻辑上的倒置，这也是我们处理这个问题的难点。

接下来我们可以提出一些insight来简化这个问题。

首先，由于小数点之后只有两位数字，故我们可以优先处理小数点之后的两位；

其次，中文大写中是“四个一段”的语法逻辑，即：“千百十个”为一个循环，更进一步来说，所谓的“亿”、“万”都是可以当作“个”处理。

码上行动

dic = ['零', '壹', '贰', '叁', '肆', '伍', '陆', '柒', '捌', '玖']

while True:
    try:
        inte, frac = input().split('.')
        head, body, tail = '人民币', '', ''
        if frac == '00':
            tail = '元整'
        else:
            if inte == '0':
                tail = ''
            else:
                tail = '元'
            if frac[0] != '0':
                tail += dic[int(frac[0])] + '角'
            if frac[1] != '0':
                tail += dic[int(frac[1])] + '分'
        l, i = [], len(inte)
        while i - 4 >= 0:
            l.insert(0, inte[i-4: i])
            i -= 4
        if i > 0:
            l.insert(0, inte[:i])
            
        for i, num in enumerate(l):
            flag = True
            for j, c in enumerate(num):
                if c == '0':
                    if num == '0000':
                        if l[-1] != '0000' and flag:
                            body += '零'
                            flag = False
                            continue
                    else:
                        if j != len(num)-1 and num[j+1] != '0' and flag:
                            body += '零'
                            flag = False
                            continue
                else:
                    if len(num[j:]) == 4:
                        body += dic[int(c)] + '仟'
                    elif len(num[j:]) == 3:
                        body += dic[int(c)] + '佰'
                    elif len(num[j:]) == 2:
                        if c != '1':
                            body += dic[int(c)] + '拾'
                        else:
                            body += '拾'
                    else:
                        body += dic[int(c)]
            if len(l[i:]) == 3:
                body += '亿'
            elif len(l[i:]) == 2 and num != '0000':
                body += '万'
        print(head + body + tail)
    except:
        break                       

心有成算

时间复杂度：虽然算法比较长，但是只是对每一位数字进行一次处理，故时间复杂度为$O(n)O(n)$

空间复杂度：使用n长来存储输入，已经中间的变量，故空间复杂度为$O(n)O(n)$

例题图解

另辟蹊径

感觉这道题也没有其他特别优秀的思路了，所以要想提高速度。。不如。。换个语言吧。

#include <iostream>
#include <string>
using namespace std;

string integer[] = {"零", "壹", "贰", "叁", "肆", "伍", "陆", "柒", "捌", "玖"};
string scaleTable1[] = {"拾", "佰", "仟"};
string scaleTable2[] = {"", "万", "亿"};

string processAfterDot(string str) {
    string result;
    if(str == "00")
        return "";
    if(str[0] > '0')
        result += integer[str[0] - '0'] + "角";
    if(str[1] > '0')
        result += integer[str[1] - '0'] + "分";
    
    return result;
}

string processBeforeDot(string str) {
    string result;
    int scale = 10000;
    int number = stoi(str);
    bool carryThousand = false;
    
    if(number == 0) {
        return "";
    }
    
    for(int i=0; i<2; ++i) {
        int segNum = number % scale;
        string segStr;
        number /= scale;
        
        if(segNum == 0) {
            continue;
        }
        
        int thousand = segNum / 1000;
        int hundred = segNum / 100 - thousand * 10;
        int ten = segNum / 10 - thousand * 100 - hundred * 10;
        int one = segNum % 10;
        
        if(thousand == 0) {
            if(number%10 != 0)
                segStr = segStr + integer[0];
        }
        else
            segStr = segStr + integer[thousand] + scaleTable1[2];
        
        if(hundred == 0) {
            if(thousand != 0)
                segStr = segStr + integer[0];
        } else 
            segStr = segStr + integer[hundred] + scaleTable1[1];
        
        if(ten == 0) {
            if(hundred != 0) 
                segStr = segStr + integer[0];
        } else if(ten == 1) {
            segStr = segStr + scaleTable1[0];
        } else {
            segStr = segStr + integer[ten] + scaleTable1[0];
        }
        
        if(one == 0) {
            if(ten != 0)
                segStr = segStr + integer[0];
        } else {
            segStr = segStr +  integer[one];
        }
        
        if(i == 0) {
            if(one == 0)
              //汉字一个占三bytes
                segStr = segStr.substr(0, segStr.size()-3);
        } else {
            if(one == 0) {
                segStr = segStr.substr(0, segStr.size()-3);
                segStr = segStr + scaleTable2[i];
                
                if((segNum/10 > 0 || number > 0)) {
                    if(!carryThousand) {
                        segStr = segStr + integer[0];
                    }
                } else {
                    segStr = segStr + integer[0];
                }
                
            } else {
                segStr = segStr + scaleTable2[i];
            }
        }
        
        if(i == 0 && thousand != 0)
            carryThousand = true;
        else
            carryThousand = false;
        
        result = segStr + result;
    }
    
    return result;
}

int main() {
    string input;
    while(cin >> input) {
        int idx = input.find('.');
        string str1 = input.substr(0, idx);
        string str2 = input.substr(idx+1);
        
        string result = "人民币";
        string beforeDot = processBeforeDot(str1);
        string afterDot= processAfterDot(str2);
        
        if(beforeDot.size() == 0) {
            if(afterDot.size() != 0) {
                result += afterDot;
            }
        } else {
            if(afterDot.size() == 0) {
                result += beforeDot + "元" + "整";
            } else {
                result += beforeDot + "元" + afterDot;
            }
        }
        
        cout << result << endl;
    }
}

时间复杂度：不变，为$O(n)O(n)$

空间复杂度：不变，为$O(n)O(n)$