​

本文记录在 蓝桥杯 刷题中发现的一个同类型问题，大数的处理。以下是「BASIC-10 十进制转十六进制」和「BASIC-30 阶乘计算」的解题分享。

如果觉得我代码太烂，欢迎留言拍砖。🎉

BASIC-10 十进制转十六进制

资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
　　给定n个十六进制正整数，输出它们对应的八进制数。
输入格式
　　输入的第一行为一个正整数n （1<=n<=10）。
　　接下来n行，每行一个由0~9、大写字母A~F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
输出格式
　　输出n行，每行为输入对应的八进制正整数。
【注意】
　　输入的十六进制数不会有前导0，比如012A。输出的八进制数也不能有前导0。
样例输入
　　2
　　39
　　123ABC
样例输出
　　71
　　4435274
【提示】
　　先将十六进制数转换成某进制数，再由某进制数转换成八进制。

一、思路

• 用自带的进制输出，真是太方便啦！📎 C++好用的进制转换
• 但是这数据规模忒🐔大了，每个十六进制数长度不超过 100000 * 4/3 = 长度足足有 133333 位 。

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        long long s;
        cin >> hex >> s;
        cout << oct << s << endl;
    }
    return 0;
}

二、改进

1.用什么存

• 用字符串读入，输出。（便于挨个字符转换 + 便于字符拼接）

2.如何转换

• 十六进制数 挨个转换为 二进制数，并拼接。【利用数组 s2 += a[s16[j] - 'A' + 10];】
• 二进制数，每三位，转换成八进制。【利用键值对 s8 += m[tmp];】

#include <iostream>
#include <map>
using namespace std;
int main() {
    string a[16] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", 
        "1010", "1011", "1100", "1101", "1110", "1111"};
    map<string, string> m;
    m["000"] = "0";
    m["001"] = "1";
    m["010"] = "2";
    m["011"] = "3";
    m["100"] = "4";
    m["101"] = "5";
    m["110"] = "6";
    m["111"] = "7";
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s16 = "", s2 = "", s8 = "";
        cin >> s16;
        for (int j = 0; j < s16.size(); j++) {
            if (s16[j] > '9') {
                s2 += a[s16[j] - 'A' + 10];
            } else {
                s2 += a[s16[j] - '0'];
            }
        }
        if (s2.size() % 3 == 1) {
            s2 = "00" + s2;
        } else if (s2.size() % 3 == 2) {
            s2 = "0" + s2;
        }
        int flag = 0;
        for (int j = 0; j < s2.size(); j += 3) {
            string tmp = s2.substr(j, 3);
            s8 += m[tmp];    
            if (j == 0 && m[tmp] == "0") {
                flag = 1;
            }
        }
        if (flag) {
            s8 = s8.substr(1);
        }
        cout << s8;
        cout << endl;
    }
    return 0;
}

/*
易错：
1. 第5行，初始化数组，逗号别少写。
2. 第22行，s16[j] > '9'，9的单引号，别少写
3. 第29行，不能写成 s2 += “00”，因为 “00” 应该在前面
4. 第45行，注意换行，保持题目输出的格式一致
*/

BASIC-30 阶乘计算

资源限制
时间限制：1.0s   内存限制：512.0MB
问题描述
　　输入一个正整数n，输出n!的值。
　　其中n!=1*2*3*…*n。
算法描述
　　n!可能很大，而计算机能表示的整数范围有限，需要使用高精度计算的方法。使用一个数组A来表示一个大整数a，A[0]表示a的个位，A[1]表示a的十位，依次类推。将a乘以一个整数k变为将数组A的每一个元素都乘以k，请注意处理相应的进位。首先将a设为1，然后乘2，乘3，当乘到n时，即得到了n!的值。
输入格式
　　输入包含一个正整数n，n<=1000。
输出格式
　　输出n!的准确值。
样例输入
10
样例输出
3628800

一、思路：

1.用什么存：

• 用数组 ans 来存结果，因为不知道数组多长，使用 vector ，并倒序储存结果，个位在 a[0]。
• 用数组 flag 来存进位值，同样使用 vector 。

2.如何进位

• flag 长度保持比 ans 长度多一位，当 flag 长度 = ans 长度时，flag 长度增加，存 ans 的进位值 或 0。

• 一轮结束，当 falg 最后一位，不为零时，ans 长度增加，存 falg 最后一位值。

3.缺点

• vector 长度增加时 的判断过于麻烦。（判断是否处于最后一位 & 判断增加长度处的值为进位值 or 0）
• 边乘边进位的逻辑过于繁琐，可以分两次，先乘再加，（见优化）

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> ans, flag;
    ans.push_back(1);
    flag.push_back(0);
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < ans.size(); j++) {
            ans[j] = i * ans[j] + flag[j];
            flag[j] = 0;
            if (ans[j] >= 10) {
                if (flag.size() - 1 == j) {
                    flag.push_back(ans[j] / 10);
                } else {
                    flag[j + 1] = ans[j] / 10;
                }
                ans[j] %= 10;
            } else {
                if (flag.size() - 1 == j) {
                    flag.push_back(0);
                } else {
                    flag[j + 1] = 0;
                }
            }
        }
        while (flag[flag.size() - 1]) {
            ans.push_back(flag[flag.size() - 1]);
            if (ans[ans.size() - 1] >= 10) {
                flag.push_back(ans[ans.size() - 1] / 10);
                ans[ans.size() - 1] %= 10;
            } else {
                flag.push_back(0);
            }
        }
    }
    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i];
    }
    return 0;
}
/*
易错：
29-36行，对ans的最高位进位的操作必不可少，否则下一轮，最高位的乘法的结果会爆
i-- 别写成 i++
*/

二、优化

• 初始化一个大数组 a[10000]，可省去 push_back() 步骤。

• 多次循环，将 乘法 和 进位（加法） 用两个循环分开处理。

• 多次循环，将 去除前置0 和 打印 分开处理。

#include <iostream>
using namespace std;
int main() {
    int a[10000] = {1};
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10000; j++) {
            a[j] *= i;
        }
        for (int j = 0; j < 10000; j++) {
            if (a[j] >= 10) {
                a[j + 1] += (a[j] / 10);
                a[j] %= 10; 
            }
        }
    }
    int flag = 0;
    for (int i = 9999; i >= 0; i--) {
        if (a[i] == 0) {
            continue;
        }
        flag = i;
        break;
    }
    for(int i = flag; i >= 0; i--) {
        cout << a[i];
    }
    return 0;
}
/*
易错：a[10000] 的数组长度，1000不够大，需要10000。
*/

三、启示

• 有大大大大数乘法，可以用数组存。