【马蹄集】第二十四周——高精度计算专题

数论专题：高精度计算

---

MT2191 整数大小比较

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

给出两个正整数，判断它们的大小。

格式

输入格式：两个正整数。
输出格式：若前者大，输出 >；若后者大，输出 <；若一样大，输出 =。

样例 1

输入：1412894619244619891 23762842222

输出：>

备注

保证所有数在 $2^{100}$ 以内。

相关知识点：高精度计算

题解

虽然这道题是比较数字的大小，但实际上我们不用关心其数字的取值范围（可以从字符串对象的角度出发进行比较）。对于任意两个正整数，它们之间的大小关系可根据以下两步进行比较：

1. 数字长度。对于正整数而言，显然长度越长的数更大。
2. 若长度相等，则从数的最高位到最低位依次比较大小，在某位上具有更大数字的数更大。

若 1、2 之后未能找到更大的数，则说明这两个数的取值相同。

基于此，可直接写出求解该题的完整代码（已 AC）：

/*
    MT2191 整数大小比较 
*/
#include 
using namespace std;

// 比较两个大数的大小 
int compare(string stra, string strb)
{
    // 根据长度判断大小关系 
    int lenA = stra.length();
    int lenB = strb.length();
    if(lenA > lenB) return 1;
    if(lenA < lenB) return -1;
    // 长度相等需要进一步判断
    for(int i=0; i<lenA; i++){
        if(stra[i] - strb[i] > 0) return 1;
        if(stra[i] - strb[i] < 0) return -1;
    }
    // 或者直接比较字符串大小
    // if(stra > strb) return 1;
    // else if(stra < strb) return -1;
    // else return 
    return 0;
}

// 打印结果
void printResult(int result)
{
    if(result > 0) cout<<">"<<endl;
    else if(result < 0) cout<<"<"<<endl;
    else cout<<"="<<endl;
}

int main( )
{
    // 获取输入 
    string stra, strb;
    cin>>stra>>strb;
    // 比较两个大数的大小
    int result = compare(stra, strb);
    // 输出比较结果
    printResult(result);
    return 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

---

MT2192 A+B problem

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

计算 $A+B(1\le A,B\le {10}^{10000})$。

格式

输入格式：两行每行一个整数 $A,B$。
输出格式：一个整数 $A+B$。

样例 1

输入：

1
1

输出：

2

相关知识点： 高精度计算

题解

这道题考察的是大数运算（加法）。关于如何实现大数加法运算的分析请见博客 【算法与数据结构】——大数运算 。下面给出多位数加法的执行流程：

多位数加法的过程涉及到对各个位的加法运算，因此在处理大数的加法运算时，通常会用一个 int 型数组来存储大数在各个位上的值。例如，数：122333444455555666666，可通过一个足够长的数组 $ary[]$ ，使 $ary\left[0\right]=1,ary\left[1\right]=2,ary\left[3\right]=2,\dots ,ary\left[20\right]=6$ 进行存储。采取数位与索引大小相对应的存储方式（即数的低位对应较小的索引，高位对应较大的索引），是为了便于大数在执行加法运算时的进位可直接在数组中向后拓展。接下来，就能按照以上思路扫描数组并对各个位进行加法运算。最后，单独用一层循环处理进位即可。

下面直接给出求解本题的完整代码（已 AC）：

/*
    MT2192 A+B problem 
*/
#include 
using namespace std;

const int N = 1e4+5;
int numa[N], numb[N];

// 计算两个大数之和（输入为字符串） 
void getSum(string stra, string strb)
{
    // 赋初值
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    int tmp = 0;
    // 将两个字符串保存至 int 型数组中（注意逆序） 
    for(int i=stra.length()-1; i>=0; i--)
        numa[tmp++] = stra[i] - '0';
    tmp = 0;
    for(int i=strb.length()-1; i>=0; i--)
        numb[tmp++] = strb[i] - '0';
    // 将数组中的每个数按位进行加法运算
    for(int i=0;i<N;i++)
        numa[i] += numb[i];
    // 对存放加法结果的数组执行进位处理
    for(int i=0; i<N; i++){
        numa[i+1] += numa[i] / 10;
        numa[i] %= 10;
    }
}

// 输出大数加法后的结果 
void printBigData()
{
    // 从最高位向后扫描，直到第 1 个非 0 数字出现 
    int p = N-1;
    while(numa[p] == 0) p--;
    while(p >= 0) cout<<numa[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    string stra, strb;
    cin>>stra>>strb;
    // 对两个大数进行加法运算 
    getSum(stra, strb);
    // 输出和
    printBigData();
    return 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
49
50
51
52
53

---

MT2193 A-B problem

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

计算 $A-B(1\le B\le A\le {10}^{10000})$。

格式

输入格式：两行每行一个整数 $A,B$。
输出格式：一个整数 $A-B$。

样例 1

输入：

2
1

输出：

1

相关知识点： 高精度计算

题解

这道题考察的是大数运算（减法）。关于如何实现大数减法运算的分析请见博客 【算法与数据结构】——大数运算 。下面给出多位数减法的执行流程：

多位数减法需要用到 int 型数组来存储大数在各个位上的值，其存储规则和大数加法一致（即低位对应较小的索引，高位对应较大的索引）。接下来，只需要扫描数组，在每个位上按照以上思路进行减法运算即可得到大数减法的结果。

下面直接给出求解本题的完整代码（已 AC）：

/*
    MT2193 A-B problem 
*/
#include 
using namespace std;

const int N = 1e4+5;
int numa[N], numb[N];

// 计算两个大数之差（输入为字符串） 
void getSub(string stra, string strb)
{
    // 赋初值
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    int tmp = 0;
    // 将两个字符串保存至 int 型数组中（注意逆序） 
    for(int i=stra.length()-1; i>=0; i--)
        numa[tmp++] = stra[i] - '0';
    tmp = 0;
    for(int i=strb.length()-1; i>=0; i--)
        numb[tmp++] = strb[i] - '0';
    // 将数组中的每个数按位进行减法运算
    for(int i=0;i<N;i++){
        numa[i] -= numb[i];
        if(numa[i] < 0){
            // 借位 
            numa[i+1]--; 
            numa[i] += 10;
        }
    }
}

// 输出大数减法后的结果 
void printBigData()
{
    // 从最高位向后扫描，直到第 1 个非 0 数字出现 
    int p = N-1;
    while(numa[p] == 0) p--;
    while(p > -1) cout<<numa[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    string stra, strb;
    cin>>stra>>strb;
    // 对两个大数进行减法运算 
    getSub(stra, strb);
    // 输出和
    printBigData();
    return 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
49
50
51
52
53
54

---

MT2194 大斐列

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

计算斐波那契数列第 $n$ 项。
斐波那契数列定义为：$F[1]=1，F[2]=1$，递推关系为：$F[N]=F[N-1]+F[N-2]$。即：$1、1、2、3、5、8、13、21、34、\dots \dots$

格式

输入格式：一个整数 $n$。
输出格式：一个整数 $F[n]$。

样例 1

输入：6

输出：8

备注

对于 30% 的数据：$3\le n\le 20$。
对于 100% 的数据：$3\le n\le 5000$。

相关知识点：高精度计算

题解

这道题实际上就是求斐波那契数列：即通过迭代公式 $F[N]=F[N-1]+F[N-2]$，不断获取下一个值。但是斐波那契数列的增长速度非常快，通过编写 Python 代码可知（代码如下），斐波那契数列的第 5000 个数的长度达到了 1045。因此这道题是一道妥妥的大数加法问题。

# 求斐波那契的第 5000 项
ary = [1,1]
for i in range(2,5000):
    ary.append(ary[i-1]+ary[i-2])
print(ary[4999])
print(len(str(ary[4999])))
1
2
3
4
5
6

所以这里依然需要用到大数加法。具体的实现方式和前面类似，在此就不赘述。

下面给出基于以上思路写出的完整代码（已 AC）：

/*
    MT2194 大斐列 
    通过 python 算出最后数字（即第 5000 项）的长度为 1045
*/
#include 
using namespace std;

const int N = 1100;
int numa[N], numb[N], numc[N];

// 计算斐波那契数列
void getFibonacci(int n)
{
    // 赋初值
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    memset(numc, 0, sizeof(numc));
    numa[0] = numb[0] = 1;
    n -= 2;
    // 递推求解斐波那契数列并统计前缀和 
    while(n--){
        // 将数组中的每个数按位进行加法运算 
        for(int i=0;i<N;i++)
            numc[i] = numa[i] + numb[i];
        // 对存放加法结果的数组执行进位处理
        for(int i=0; i<N; i++){
            numc[i+1] += numc[i] / 10;
            numc[i] %= 10;
        }
        // 将数组进行前向赋值（从而实现递推）
        memcpy(numa, numb, sizeof(numb));
        memcpy(numb, numc, sizeof(numc));
    }
}

// 输出大数加法后的结果 
void printBigData()
{
    // 从最高位向后扫描，直到第 1 个非 0 数字出现 
    int p = N-1;
    while(numc[p] == 0) p--;
    while(p > -1) cout<<numc[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    int n;
    cin>>n;
    // 求出斐波那契数列 
    getFibonacci(n);
    // 输出指定项 
    printBigData();
    return 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
49
50
51
52
53
54
55
56

---

MT2195 升级版斐波那契数列

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

我们都知道斐波那契数列一项是前两项的和，现在我们规定一个升级版斐波那契数列，其一项为前三项的和，要求算其前 $n$ 项的和。即，定义：$F[1]=1，F[2]=1，F[3]=1$，递推关系为：$F[N]=F[N-1]+F[N-2]+F[N-3]$。

格式

输入格式：一个整数 $n$；
输出格式：前 $n$ 项的和。

样例 1

输入：4

输出：6

备注

其中：$4\le n\le 1000$。

相关知识点：高精度计算

题解

这道题依然考察了大数加法，和前面一题类似，下面直接给出求解本题的完整代码（已 AC）：

/*
    MT2195 升级版斐波那契数列 
    通过 python 算出最后数字（即第 1000 项）的长度为 265，整个数列的数字之和长度为 265
*/
#include 
using namespace std;

const int N = 300;
int numa[N], numb[N], numc[N], numd[N], preSum[N];

// 计算斐波那契数列
void getFibonacci(int n)
{
    // 赋初值
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    memset(numc, 0, sizeof(numc));
    memset(numd, 0, sizeof(numd));
    memset(preSum, 0, sizeof(preSum));
    numa[0] = numb[0] = numc[0] = 1;
    preSum[0]  = 3;
    n -= 3;
    // 递推求解斐波那契数列并统计前缀和 
    while(n--){
        // 将数组中的每个数按位进行加法运算 
        for(int i=0;i<N;i++)
            numd[i] = numa[i] + numb[i] + numc[i];
        // 对存放加法结果的数组执行进位处理
        for(int i=0; i<N; i++){
            numd[i+1] += numd[i] / 10;
            numd[i] %= 10;
        }
        // 将当前项累加至前缀和数组中
        for(int i=0;i<N;i++)
            preSum[i] += numd[i];
        for(int i=0; i<N; i++){
            preSum[i+1] += preSum[i] / 10;
            preSum[i] %= 10;
        }
        // 将数组进行前向赋值
        memcpy(numa, numb, sizeof(numb));
        memcpy(numb, numc, sizeof(numc));
        memcpy(numc, numd, sizeof(numd));
        
    }
}

// 输出大数加法后的结果 
void printBigData()
{
    // 从最高位向后扫描，直到第 1 个非 0 数字出现 
    int p = N-1;
    while(preSum[p] == 0) p--;
    while(p > -1) cout<<preSum[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    int n;
    cin>>n;
    // 求出斐波那契数列 
    getFibonacci(n);
    // 输出前缀和 
    printBigData();
    return 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

---

MT2196 2的N次幂

难度：黄金    时间限制：1秒    占用内存：128M

题目描述

任意给定一个正整数 $N(N\le 100)$ ，计算 2 的 $N$ 次方的值。

格式

输入格式：一个正整数 $N$；
输出格式：输出 $2^N$ 的值。

样例 1

输入：5

输出：32

相关知识点：高精度计算

题解

$2^n$ 在 $n$ 取 100 时，是一个长度为 31 的大数，因此也是一道高精度题。与前面不同的是，这道题要求的是乘幂运算。但实际上，数的乘幂运算就等于进行 “幂” 次乘法运算（叠乘），乘数为底数。所以求解该题的关键实际是基于乘法运算的高精度计算问题，关于如何实现大数乘法运算的分析请见博客 【算法与数据结构】——大数运算 。

这里选用的数据结构依然是 int 型数组，其存储规则和大数加法一致（即低位对应较小的索引，高位对应较大的索引）。不过在算法一开始，需要将该数组的最低位置为底数（即 2）。接下来，定义一重循环（循环次数为 $n-1$），每遍都执行以下两步：

• 将存放大数的数组中的每一位都乘以底数；
• 遍历整个数组执行进位。

算法结束时，即得到了大数乘幂运算的结果。下面给出基于以上思路得到的完整代码：

/*
    MT2196 2的N次幂  
*/
#include 
using namespace std;

// 题目给的数据范围保证了结果不超过 32 位 
const int N = 32;
int num[N];

// 高精度乘幂运算
void getHighPrecision(int base, int power)
{
    // 初始化存放运算结果的数组 
    memset(num, 0, sizeof(num));
    // 给数组赋初值 
    num[0] = base;
    // 执行乘幂运算 
    while(--power){
        // 将数组中的每个数进行乘法运算 
        for(int i=0; i<N; i++)
            num[i] *= base;
        // 对数组执行进位处理
        for(int i=0; i<N; i++){
            num[i+1] += num[i] / 10;
            num[i] %= 10;
        }
    }
}

// 输出高精度运算后的大数
void printBigData()
{
    // 从最高位向后扫描，直到第 1 个非 0 数字出现 
    int p = N-1;
    while(num[p] == 0) p--;
    while(p > -1) cout<<num[p--];
    cout<<"\n";
} 

int main( )
{
    // 获取输入 
    int n;
    cin>>n;
    // 执行乘幂的高精度运算
    getHighPrecision(2, n);
    // 输出 
    printBigData();
    return 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
49
50
51

END

---