题意分析

本题要求编写一个程序，将介于 0 和 1（包含 0 和 1）之间的八进制小数转换为等价的十进制小数。输入为一系列八进制小数，每行一个，格式为 0.d1d2d3...dk，其中 di 是八进制数位（取值范围 0 到 7），k 的值没有限制。输出为对应的十进制小数，格式为 0.d1d2d3 ... dk [8] = 0.D1D2D3 ... Dm [10]，且输出的十进制小数不能有尾随零，即 Dm 不等于 0。

解题思路

1. 数据读取：使用 scanf 函数逐行读取输入的八进制小数字符串 s1。
2. 初始化操作：
   • 使用 strlen 函数获取字符串 s1 的长度 l。
   • 将 s1 复制到 s3 中，用于后续输出原始八进制数。
   • 计算转换后的十进制小数的最大长度 len，根据题目条件，八进制数小数点后有 n 位时，转换为十进制后小数点后的位数最多为 3n 位，所以 len = 3 * (l - 2)（因为字符串 s1 包含 0. 这两位）。
3. 转换过程：
   • 初始化字符串 s2 为 0.，用于存储转换后的十进制小数。
   • 通过循环进行乘 10 对 8 取整的操作，从八进制小数的最低位开始，逐位计算并更新 s1 中的每一位，同时得到十进制小数的每一位，存储到 s2 中。
4. 去除尾随零：从 s2 的末尾开始，找到最后一个不为 0 的字符位置 j。
5. 输出结果：按照指定格式输出原始八进制数和转换后的十进制数，只输出到 j 位置。

复杂度分析

1. 时间复杂度：
   • 读取输入的时间复杂度为 $O(k)$，其中 $k$ 是输入八进制小数的位数。
   • 转换过程中，内层循环对八进制小数的每一位进行处理，循环次数为 l - 2，外层循环执行 len 次，所以转换过程的时间复杂度为 $O(3 * (l - 2) * (l - 2))$。
   • 去除尾随零的时间复杂度为 $O(len)$。
   • 总体时间复杂度主要取决于转换过程，为 $O(3 * (l - 2) * (l - 2))$，可以近似看作 $O(l^2)$。
2. 空间复杂度：
   • 主要使用了三个字符数组 s1、s2 和 s3，s1 和 s3 的长度固定为 20，s2 的长度固定为 50，所以空间复杂度为 $O(1)$。

代码解释

#include<iostream>
#include<string>
#include<cstdlib>
#include<algorithm>
#include<cstring>  // Added for strlen and strcpy
using namespace std;
char s1[20],s2[50],s3[20];
 
int main()
{
    int i,t,j,k,g,l,len;
    // 循环读取输入的八进制小数字符串
    while(scanf("%s",s1)!=EOF)
    {
        // 获取字符串 s1 的长度
        l=strlen(s1);
        // 将 s1 复制到 s3 中，用于后续输出原始八进制数
        strcpy(s3,s1);
        // 计算转换后的十进制小数的最大长度
        len=3*(l-2);
        t=0;
        // 初始化 s2 为 0.
        s2[0]='0';
        s2[1]='.';
        j=2;
        // 进行转换过程
        while(t<len)
        { 
            k=0;
            t++;
            // 从最低位开始，乘 10 对 8 取整
            for(i=l-1;i>1;i--)                      
            {
                g=(s1[i]-'0')*10+k;
                k=g/8;
                s1[i]=g%8+'0';
            }
            // 将得到的十进制小数的一位存入 s2 中
            s2[j]=k+'0';
            j++;
        }
        // 字符串结束符
        s2[j]='\0';
        // 输出原始八进制数
        printf("%s [8] = ",s3);
        j--;
        // 去除尾随零
        while(s2[j]=='0')                             
            j--;
        // 输出转换后的十进制数
        for(i=0;i<=j;i++)                             
            printf("%c",s2[i]);
        printf(" [10]\n");
    }
    // 暂停程序，方便查看结果（仅在某些环境下需要）
    system("pause");
    return 0;
}