蓝桥杯|大数问题的处理

本文最后更新于:几秒前

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

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

BASIC-10 十进制转十六进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
资源限制
时间限制: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 位
1
2
3
4
5
6
7
8
9
10
11
12
#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];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
资源限制
时间限制: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)
  • 边乘边进位的逻辑过于繁琐,可以分两次,先乘再加,(见优化)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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 和 打印 分开处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#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。
*/

三、启示

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

本博客所有文章均个人原创,除特别声明外均采用 CC BY-SA 4.0协议,转载请注明出处!