面试题：C语言高精度多进制转换及优化

数据结构选择：
- 为了处理超过常规数据类型范围的大数字，我们可以使用数组来存储每一位数字。例如，使用int数组，每个元素存储一位数字。
实现思路：
- 十进制转其他进制：
  - 采用除基取余法。例如，要将十进制数转换为base进制，不断用该十进制数除以base，将余数按顺序记录下来，直到商为0。
- 其他进制转十进制：
  - 采用位权展开法。例如，对于一个base进制数，从最低位开始，每一位乘以base的相应幂次，然后累加起来。
代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 将十进制数转换为其他进制
void decToBase(int *dec, int decLen, int base, char *result) {
    int index = 0;
    int temp[10000]; // 临时数组存储余数
    int tempIndex = 0;
    // 先进行除基取余
    while (decLen > 0 || dec[0] > 0) {
        int remainder = 0;
        for (int i = decLen - 1; i >= 0; i--) {
            int t = dec[i] + remainder * 10;
            dec[i] = t / base;
            remainder = t % base;
        }
        if (decLen > 0 && dec[decLen - 1] == 0) {
            decLen--;
        }
        temp[tempIndex++] = remainder;
    }
    // 将余数转换为字符
    for (int i = tempIndex - 1; i >= 0; i--) {
        if (temp[i] < 10) {
            result[index++] = temp[i] + '0';
        } else {
            result[index++] = temp[i] - 10 + 'A';
        }
    }
    result[index] = '\0';
}

// 将其他进制数转换为十进制
void baseToDec(char *baseNum, int base, int *dec, int *decLen) {
    *decLen = 0;
    int len = strlen(baseNum);
    for (int i = 0; i < len; i++) {
        int num = 0;
        if (baseNum[i] >= '0' && baseNum[i] <= '9') {
            num = baseNum[i] - '0';
        } else if (baseNum[i] >= 'A' && baseNum[i] <= 'F') {
            num = baseNum[i] - 'A' + 10;
        }
        int carry = 0;
        for (int j = 0; j < *decLen || carry > 0; j++) {
            int t = (j < *decLen? dec[j] : 0) * base + carry;
            dec[j] = t % 10;
            carry = t / 10;
            if (j == *decLen - 1 && carry > 0) {
                *decLen = *decLen + 1;
            }
        }
        for (int j = 0; j < *decLen || carry > 0; j++) {
            int t = (j < *decLen? dec[j] : 0) + num;
            dec[j] = t % 10;
            num = t / 10;
            if (j == *decLen - 1 && num > 0) {
                *decLen = *decLen + 1;
            }
        }
    }
}

优化策略：
- 减少内存占用：
  - 在存储大数字时，使用数组存储每一位数字，没有使用更复杂的数据结构，避免额外的指针等内存开销。
- 降低时间复杂度：
  - 在除基取余和位权展开过程中，通过优化循环操作，每次循环处理数组中的所有位，避免不必要的重复计算。例如，在十进制转其他进制时，在一次循环中完成对整个大数字的除法操作并计算余数。
算法复杂度分析：
- 十进制转其他进制：
  - 时间复杂度：主要操作是除基取余，每次循环处理数组中的所有位，假设大数字的长度为n，则时间复杂度为$O(n)$。
  - 空间复杂度：需要一个临时数组存储余数，其大小取决于大数字转换后的长度，最多为n，所以空间复杂度为$O(n)$。
- 其他进制转十进制：
  - 时间复杂度：主要操作是位权展开，每次循环处理输入字符串中的一位和当前的十进制数组，假设输入字符串长度为m，十进制数组长度为n，则时间复杂度为$O(m \times n)$。但实际中，随着计算进行，n逐渐增大，总体时间复杂度仍接近$O(m \times n)$。
  - 空间复杂度：需要一个数组存储十进制结果，其大小取决于转换后的十进制数长度，最多为m，所以空间复杂度为$O(m)$。

你可以使用以下方式调用上述函数：

int main() {
    int dec[10000];
    int decLen = 0;
    char baseNum[10000];
    int base;

    // 输入要转换的其他进制数和进制
    printf("请输入要转换的数: ");
    scanf("%s", baseNum);
    printf("请输入该数的进制: ");
    scanf("%d", &base);
    baseToDec(baseNum, base, dec, &decLen);

    // 输入目标进制
    int targetBase;
    printf("请输入目标进制: ");
    scanf("%d", &targetBase);
    char result[10000];
    decToBase(dec, decLen, targetBase, result);
    printf("转换后的结果是: %s\n", result);

    return 0;
}

上述代码实现了高精度多进制转换，包括十进制转其他进制和其他进制转十进制，并对优化策略和算法复杂度进行了分析。

星途面试题库

面试题：C语言高精度多进制转换及优化

知识考点

面试题答案