当前位置：首页 > 洛谷 > 标题：洛谷B3617题解析：八进制转十六进制算法实现与优化（附AC100代码）

标题：洛谷B3617题解析：八进制转十六进制算法实现与优化（附AC100代码）

9个月前 (06-21)

一、题目解读

洛谷B3617题要求将输入的八进制字符串转换为十六进制表示。题目需处理大数场景，且对输入合法性有明确限制（长度不超过1000，仅包含0-7字符）。由于八进制与十六进制无法直接转换，需借助十进制作为中间桥梁，因此解题思路需设计两步转换：八进制→十进制→十六进制。

二、解题思路

参考代码采用分模块设计，核心逻辑分为三部分：

1. 输入验证：自定义isValidOctal()函数通过字符遍历与长度检查，过滤非法输入。

2. 八进制转十进制：采用模拟乘法原理，每次将十进制结果乘以8并累加当前八进制位，通过字符串逆序处理实现大数乘法。

3. 十进制转十六进制：利用短除法思想，从低位到高位逐位计算余数并拼接十六进制字符，最终逆序输出结果。

三、解题步骤

1. 预处理：读取用户输入的八进制字符串，调用isValidOctal()验证合法性。

2. 阶段一转换：通过octalToDecimal()函数实现八进制→十进制转换，关键步骤为循环迭代每位数字，模拟“乘8+本位”的竖式乘法过程。

3. 阶段二转换：调用decimalToHex()，将十进制数逐位除以16取余数，反向构建十六进制字符串。

4. 输出优化：针对0值特判，避免空字符串输出。

四、代码与注释

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

// 验证八进制字符串合法性
bool isValidOctal(const string& s) {
    if(s.empty() || s.length() > 1000) return false;  // 长度检查
    for(char c : s) {                              // 遍历字符
        if(c < '0' || c > '7') return false;        // 仅允许0-7
    }
    return true;
}

// 八进制转十进制（大数处理）
string octalToDecimal(const string& octal) {
    string decimal = "0";
    for(char c : octal) {
        int digit = c - '0';                      // 提取当前八进制位
        // 十进制数乘以8
        string temp = decimal;
        int carry = 0;
        for(int i = temp.length()-1; i >= 0; i--) { // 逆序处理大数乘法
            int num = (temp[i] - '0') * 8 + carry;
            temp[i] = (num % 10) + '0';            // 取个位
            carry = num / 10;                      // 进位
        }
        if(carry > 0) {
            temp.insert(0, 1, carry + '0');       // 前置最高位进位
        }
        // 加上当前八进制位
        carry = digit;
        for(int i = temp.length()-1; i >= 0 && carry > 0; i--) {
            int num = (temp[i] - '0') + carry;
            temp[i] = (num % 10) + '0';
            carry = num / 10;
        }
        if(carry > 0) {
            temp.insert(0, 1, carry + '0');
        }
        decimal = temp;
    }
    return decimal;
}

// 十进制转十六进制（大数处理）
string decimalToHex(const string& decimal) {
    if(decimal == "0") return "0";                  // 特判0值
    
    string hex;
    string num = decimal;
    const string hexDigits = "0123456789abcdef";    // 十六进制字符表

    while(num!= "0") {
        int remainder = 0;
        string temp;
        // 模拟除法过程
        for(char c : num) {
            int digit = remainder * 10 + (c - '0');  // 当前位乘以10 + 余数
            remainder = digit % 16;                 // 取余数
            digit /= 16;                            // 商
            if(!temp.empty() || digit > 0) {         // 非空或高位存在时拼接
                temp.push_back(digit + '0');
            }
        }
        hex.push_back(hexDigits[remainder]);        // 添加十六进制字符
        num = temp.empty()? "0" : temp;            // 更新被除数
    }
    
    reverse(hex.begin(), hex.end());                // 逆序输出结果
    return hex;
}

int main() {
    string octal;
    cin >> octal;                                  // 输入八进制串
    if(isValidOctal(octal)) {                      // 验证合法性
        string decimal = octalToDecimal(octal);    // 转十进制
        string hex = decimalToHex(decimal);       // 转十六进制
        cout << hex << endl;                       // 输出结果
    } else {
        cout << "Invalid input" << endl;           // 报错
    }
    return 0;
}