C++面试题集

任意进制大数转换

2017-08-25  本文已影响129人  saviochen

问题描述:将用字符串表示的M进制大数,转化为用字符串表示的N进制大数。1<M,N<=62;字符串的取值为[0-9a-zA-Z],例如B表示数字37。

1、受位数限制的方案

关于此问题,最简单的实现方式是先将M进制的大数转化为long long类型的10进制整数,然后再辗转相除求出,N进制的大数字符串。

void reverse(string& srcNum){
    size_t i = 0, j = srcNum.size() - 1;
    char temp = 0;
    while (i < j){
        temp = srcNum[i];
        srcNum[i++] = srcNum[j];
        srcNum[j--] = temp;
    }
}

string m2n_constrait(int srcBase, int desBase, string srcNum){
    if (srcBase > 62 || srcBase < 2 || desBase > 62 || desBase < 2)
        return "";
    char flag[63] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string desNum;
    long long midNum = 0, temp = 0;
    for (size_t i = 0; i < srcNum.size(); ++i){
        if (srcNum[i] >= '0' && srcNum[i] <= '9')
            temp = srcNum[i] - '0';
        else if (srcNum[i] >= 'a' && srcNum[i] <= 'z')
            temp = srcNum[i] - 'a' + 10;
        else if (srcNum[i] >= 'A' && srcNum[i] <= 'Z')
            temp = srcNum[i] - 'A' + 36;
        else return "";
        midNum = midNum * srcBase + temp;
    }   
    while (midNum){
        desNum.push_back(flag[midNum % desBase]);
        midNum /= desBase;
    }
    reverse(desNum);
    return desNum;
}

2、通用方案

此方案直接对原数据,用目标进制n直接进行辗转相除,取商和取余,逐步求解每一位最终结果。实现起来较为复杂,下面以一个简单的例子来说明其详细过程:要求将32进制的45转化为9进制的数字

void reverse(string& srcNum){
    size_t i = 0, j = srcNum.size() - 1;
    char temp = 0;
    while (i < j){
        temp = srcNum[i];
        srcNum[i++] = srcNum[j];
        srcNum[j--] = temp;
    }
}
bool isZero(string& srcNum){
    for (size_t i = 0; i<srcNum.size(); ++i){
        if (srcNum[i] != '0')
            return false;
    }
    return true;
}
string m2n(int srcBase, int desBase, string srcNum){
    if (srcBase > 62 || srcBase < 2 || desBase > 62 || desBase < 2)
        return "";
    char flag[63] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string desNum, midNum;
    long long temp = 0, carry = 0;
    while (!srcNum.empty() && !isZero(srcNum) ){
        for (size_t i = 0; i < srcNum.size(); ++i){
            if (srcNum[i] >= '0' && srcNum[i] <= '9')
                temp = srcNum[i] - '0';
            else if (srcNum[i] >= 'a' && srcNum[i] <= 'z')
                temp = srcNum[i] - 'a' + 10;
            else if (srcNum[i] >= 'A' && srcNum[i] <= 'Z')
                temp = srcNum[i] - 'A' + 36;
            else return "";
            carry = carry * srcBase + temp;
            if (carry / desBase != 0 || i == srcNum.size() - 1){
                midNum.push_back(flag[carry / desBase]);
                carry %= desBase;
            }
        }
        desNum.push_back(flag[carry]);
        srcNum = midNum;
        carry = 0;
        midNum.clear();
    }
    reverse(desNum);
    return desNum;
}
上一篇 下一篇

猜你喜欢

热点阅读