八進制小數精確轉換為十進制小數算法實現

問題描述

輸入格式為 0.d1d2...dk 的八進制小數 (0 < k < 15)，要求精確輸出等值的十進制小數，格式：0.d1d2...dk [8] = 0.D1D2...Dm [10]。輸出尾部不能有多餘的 0 (即 Dm != 0)。

數學原理

八進制小數 0.d1d2...dk 的值為：

V = d1/8 + d2/8^2 + ... + dk/8^k

由於 8 = 2^3，每一位八進制數對應 3 位二進制。十進制小數最多需要 3k 位精度 (題目保證)。

算法：高精度整數運算

避免浮點數誤差，將分數轉為大整數分子/分母運算，最後模擬手工除法輸出小數。

步驟

1. 讀取字符串 s (如 "0.75")。
2. 提取小數部分 digits = "75"，長度 k。
3. 分子 num = 0，分母 den = 1。
   • 對每位 d：num = num * 8 + d；den *= 8。
   • 最終分數 num/den 即精確值。
4. 模擬長除法輸出十進制小數：
   • 整數部分 num / den (此處必為 0)。
   • 餘數 rem = num % den。
   • 循環：rem *= 10; digit = rem / den; rem %= den; 輸出 digit。
   • 直到 rem == 0 (有限小數) 或達到足夠精度 (題目保證有限)。
   • 去除尾部 0。

C++ 參考實現 (使用 boost::multiprecision::cpp_int)

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    while (cin >> s) {
        // 解析 "0.xxx"
        string digits = s.substr(2); // 跳過 "0."
        int k = digits.length();
        
        cpp_int num = 0, den = 1;
        for (char ch : digits) {
            int d = ch - '0';
            num = num * 8 + d;
            den *= 8;
        }
        
        // 模擬除法輸出十進制
        string result = "0.";
        cpp_int rem = num % den;
        // 最多 3k 位，題目保證有限小數
        for (int i = 0; i < 3 * k + 5 && rem != 0; ++i) {
            rem *= 10;
            int digit = (rem / den).convert_to<int>();
            result.push_back('0' + digit);
            rem %= den;
        }
        // 去除尾部 0
        while (result.back() == '0') result.pop_back();
        if (result.back() == '.') result += '0'; // 處理 0.0 情況
        
        cout << s << " [8] = " << result << " [10]\n";
    }
    return 0;
}

Java 參考實現 (BigInteger)

import java.math.BigInteger;
import java.util.Scanner;

public class OctalToDecimal {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            String digits = s.substring(2);
            int k = digits.length();
            
            BigInteger num = BigInteger.ZERO;
            BigInteger den = BigInteger.ONE;
            for (char ch : digits.toCharArray()) {
                int d = ch - '0';
                num = num.multiply(BigInteger.valueOf(8)).add(BigInteger.valueOf(d));
                den = den.multiply(BigInteger.valueOf(8));
            }
            
            StringBuilder sb = new StringBuilder("0.");
            BigInteger rem = num.mod(den);
            for (int i = 0; i < 3 * k + 5 && rem.signum() != 0; i++) {
                rem = rem.multiply(BigInteger.TEN);
                BigInteger[] divRem = rem.divideAndRemainder(den);
                sb.append(divRem[0].intValue());
                rem = divRem[1];
            }
            // 去尾部 0
            while (sb.length() > 2 && sb.charAt(sb.length()-1) == '0') sb.deleteCharAt(sb.length()-1);
            if (sb.charAt(sb.length()-1) == '.') sb.append('0');
            
            System.out.println(s + " [8] = " + sb + " [10]");
        }
    }
}

樣例驗證

輸入:
0.75
0.0001
0.01234567

輸出:
0.75 [8] = 0.953125 [10]
0.0001 [8] = 0.000244140625 [10]
0.01234567 [8] = 0.020408093929290771484375 [10]

驗證 0.75：7/8 + 5/64 = 56/64 + 5/64 = 61/64 = 0.953125 ✓

關鍵點

• 使用大整數 (cpp_int/BigInteger) 避免精度丟失。
• 分母為 8^k，保證十進制展開有限 (因分母質因子只有 2，十進制分母質因子 2,5)。
• 輸出格式嚴格：去尾部 0，保留 [8] [10] 標記。