您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

大數運算專題：八進制小數轉十進制 (Octal Fractions) 完整解析

編輯：C++ 入門

問題背景

任意八進制小數 0.d₁d₂...dₖ (dᵢ ∈ {0..7}) 都能精確用有限位十進制小數表示。題目要求讀入多行八進制小數（形式為 0.xxx），輸出對應的十進制精確值，格式為：

0.xxx [8] = 0.yyy [10]

且結果不得有尾隨零。

數學原理

八進制小數 0.d₁d₂...dₖ 的值為：

Σ (dᵢ × 8⁻ⁱ) = d₁/8 + d₂/8² + ... + dₖ/8ᵏ

通分分母為 8ᵏ，分子為整數 N = d₁×8ᵏ⁻¹ + d₂×8ᵏ⁻² + ... + dₖ。
因此值為 N / 8ᵏ。因 8ᵏ = 2³ᵏ，分母僅含質因子 2，故十進制展開必定有限（最長 3k 位）。

高精度除法模擬（逐位輸出）

直接用雙精度浮點會丟失精度，需模擬手工豎式除法：

將八進制小數部分視為整數 N（去掉前導 0.）
分母 D = 8ᵏ
模擬 N / D 的十進制除法，逐位產生商位，直到餘數為 0

核心代碼 (C++)

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

// 高精度除法：返回十進制小數字符串（不含 "0." 前綴）
string divide_octal_to_decimal(const string& octal_frac) {
    int k = octal_frac.length();
    // 1. 計算分子 N (八進制字符串轉十進制大整數)
    vector<int> N(1, 0); // 低位在前
    for (char ch : octal_frac) {
        int digit = ch - '0';
        // N = N * 8 + digit
        int carry = digit;
        for (size_t i = 0; i < N.size() || carry; ++i) {
            if (i == N.size()) N.push_back(0);
            carry += N[i] * 8;
            N[i] = carry % 10;
            carry /= 10;
        }
    }
    // 2. 計算分母 D = 8^k (十進制大整數)
    vector<int> D(1, 1);
    for (int i = 0; i < k; ++i) {
        int carry = 0;
        for (size_t j = 0; j < D.size(); ++j) {
            carry += D[j] * 8;
            D[j] = carry % 10;
            carry /= 10;
        }
        while (carry) { D.push_back(carry % 10); carry /= 10; }
    }

    // 3. 高精度除法 N / D，產生小數位
    string decimal_digits;
    vector<int> rem = N; // 餘數
    // 先補齊整數部分（這裡整數部分恆為 0）
    // 開始小數部分除法
    while (true) {
        // 判斷餘數是否為 0
        bool is_zero = true;
        for (int d : rem) if (d != 0) { is_zero = false; break; }
        if (is_zero) break;

        // rem = rem * 10
        int carry = 0;
        for (size_t i = 0; i < rem.size(); ++i) {
            carry += rem[i] * 10;
            rem[i] = carry % 10;
            carry /= 10;
        }
        while (carry) { rem.push_back(carry % 10); carry /= 10; }

        // 試商：rem / D
        int q = 0;
        // 簡單試商法：因 D 位數較多，這裡用減法模擬（數據規模小可接受）
        // 實際比賽中建議用二分查找商或 Knuth Algorithm D
        vector<int> temp_rem = rem;
        while (true) {
            // temp_rem >= D ?
            bool ge = false;
            if (temp_rem.size() > D.size()) ge = true;
            else if (temp_rem.size() == D.size()) {
                for (int i = temp_rem.size()-1; i >= 0; --i) {
                    if (temp_rem[i] > D[i]) { ge = true; break; }
                    if (temp_rem[i] < D[i]) break;
                }
                if (!ge) { // 相等也算 >=
                    bool eq = true;
                    for (int i = 0; i < (int)temp_rem.size(); ++i)
                        if (temp_rem[i] != D[i]) { eq = false; break; }
                    ge = eq;
                }
            }
            if (!ge) break;
            // temp_rem -= D
            int borrow = 0;
            for (size_t i = 0; i < D.size(); ++i) {
                int sub = temp_rem[i] - D[i] - borrow;
                if (sub < 0) { sub += 10; borrow = 1; } else borrow = 0;
                temp_rem[i] = sub;
            }
            for (size_t i = D.size(); borrow && i < temp_rem.size(); ++i) {
                if (temp_rem[i] == 0) { temp_rem[i] = 9; borrow = 1; }
                else { temp_rem[i]--; borrow = 0; }
            }
            while (temp_rem.size() > 1 && temp_rem.back() == 0) temp_rem.pop_back();
            ++q;
        }
        decimal_digits.push_back('0' + q);
        rem = temp_rem;
    }
    // 去尾隨零
    while (!decimal_digits.empty() && decimal_digits.back() == '0')
        decimal_digits.pop_back();
    return decimal_digits.empty() ? "0" : decimal_digits;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    while (cin >> line) {
        // line 格式: "0.xxx"
        string octal_frac = line.substr(2); // 跳過 "0."
        string dec_frac = divide_octal_to_decimal(octal_frac);
        cout << line << " [8] = 0." << dec_frac << " [10]\n";
    }
    return 0;
}