Fork me on GitHub

高精度整数的具体应用


高精度整数

对于广大使用C/C++的读者,我们首先明确高精度整数的保存形式,我们常用如下结构体来保存一个高精度整数

1
2
3
4
struct bigInteger{
int digit[1000];
int size;
};

其中,digit数组用来保存大整数中若干位的数字,这里我们暂且使用每4位为一个单位保存,size为digit数组中第一个我们还没有使用过的数组单元(即下一个我们可以使用的数组单元)。以整数123456789为例,当我们使用该结构体来保存该值时,其结果是这样的:digit[0] = 6789; digit[1] = 2345; digit[2] = 1; size = 3;

现在我们已经能够利用该结构体来保存大整数了,接下来即将完成对其运算的实现。

  1. a+b

    题目描述:

    实现一个加法器,使其能够输出a+b的值。

    输入:

    输入包括两个数a和b,其中a和b的位数不超过1000位。

    输出:

    可能有多组测试数据,对于每组数据,输出a+b的值。

    样例输入:

    1
    2
    2 6
    10000000000000000000 10000000000000000000000000000000

    样例输出:

    1
    2
    8
    10000000000010000000000000000000

    代码如下:

    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
    #include <iostream>
    #include <cstdio>
    #include <cstring>

    using namespace std;

    struct bigInteger{
    int digit[1000]; // 按四位数一个单位保存数值
    int size; // 下一个我们未使用的数组单元
    void init(){
    for(int i = 0 ; i < 1000 ; i++){
    digit[i] = 0;
    }
    size = 0;
    }
    void set(char str[]){
    init(); // 对结构体初始化
    int L = strlen(str);
    for(int i = L-1 , j = 0 ,t = 0 , c = 1 ; i >= 0 ; i--){
    // 从最后一个字符开始倒序遍历字符串,j控制每4个字符转换为一个数字存入数组,t临时保存字符转换为数字的中间值,c表示当前位的权重,按1,10,100,1000顺序变化
    t += (str[i] - '0')*c;
    j++;
    c*=10;
    if(j == 4 || i == 0){
    digit[size++] = t;
    j = 0;
    t = 0;
    c = 1;
    }
    }
    }
    void output(){
    for(int i = size - 1 ; i >= 0 ; i--){
    if(i != size-1) printf("%04d",digit[i]);
    else printf("%d",digit[i]);
    }
    printf("\n");
    }
    bigInteger operator + (const bigInteger &A)const{
    bigInteger ret; // 返回值,即两数相加的结果
    ret.init(); // 对其初始化
    int carry = 0; // 进位,初始值为0
    for(int i = 0 ; i < A.size || i < size; i++){
    int tmp = A.digit[i]+digit[i]+carry;
    // 计算两个整数当前位以及来自低位的进位和
    carry = tmp/10000; // 计算该位的进位
    tmp %= 10000; // 去除进位部分,取后四位
    ret.digit[ret.size++] = tmp; // 保存该位结果
    }
    if(carry != 0){
    ret.digit[ret.size++] = carry; // 保存该进位
    }
    return ret;
    }
    }a,b,c;

    char str1[1002],str2[1002];
    int main(){
    while(scanf("%s%s",str1,str2)!=EOF){
    a.set(str1);
    b.set(str2); // 用两个字符串分别设置两个高精度整数
    c=a+b;
    c.output();
    }

    return 0;
    }

    运行结果:

  2. N的阶乘

    题目描述:

    输入一个正整数N,输出N的阶乘。

    输入:

    正整数N(0<=N<=1000)

    输出:

    输入可能包括多组数据,对于每一组输入数据,输出N的阶乘

    样例输入:

    1
    2
    3
    4
    5
    15

    样例输出:

    1
    2
    3
    24
    120
    1307674368000

    代码如下:

    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
    #include <iostream>
    #include <cstdio>
    #include <cstring>

    using namespace std;

    struct bigInteger{
    int digit[1000];
    int size;
    void init(){
    for(int i = 0 ; i < 1000 ; i++) digit[i] = 0;
    size = 0;
    }
    void set(char x){// 用一个小整数设置高精度整数
    init();
    do{
    digit[size++] = x%10000;
    x/=10000;
    }while(x!=0)
    }
    void output(){
    for(int i = size-1 ; i >= 0 ; i--){
    if(i != size-1) printf("%04d",digit[i]);
    else printf("%d",digit[i]);
    }
    printf("\n");
    }
    bigInteger operator*(int x)const {
    bigInteger ret; // 将要返回的高精度整数
    ret.init();
    int carry = 0;
    for(int i = 0 ; i < size; i++){
    int tmp = x*digit[i] + carry;
    carry = tmp/10000;
    tmp %= 10000;
    ret.digit[ret.size++] = tmp;
    }
    if(carry != 0){
    ret.digit[ret.size++] = carry;
    }
    return ret;
    }
    }a;

    int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
    a.init();
    a.set(1); // a初始值为1
    for(int i = 1 ; i <= n; i++){
    a = a*i;
    }
    a.output();
    }

    return 0;
    }

    运行结果:

  3. 进制转换

    题目描述:

    将M进制的数X转换为N进制的数输出

    输入:

    输入的第一行包括两个整数:M和N(2<=M,N<=36)。

    下面的一行输入一个数X,X是M进制的数,现在要求将M进制的数X转换成N进制的数输出

    输出:

    输出X的N进制表示的数

    样例输入:

    1
    2
    16 10
    F

    样例输出:

    1
    15

    代码如下:

    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
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    #include <iostream>
    #include <cstdio>
    #include <cstring>

    using namespace std;

    #define maxDigits 100

    struct bigInteger{
    int digit[maxDigits];
    int size;
    void init(){
    for(int i = 0 ; i < maxDigits ; i++) digit[i] = 0;
    size = 0;
    }
    void set(int x){
    init();
    do{
    digit[size++] = x%10000;
    x /= 10000;
    }while(x != 0);
    }
    void output(){
    for(int i = size-1 ; i >= 0 ; i--){
    if(i != size-1) printf("%04d",digit[i]);
    else printf("%d",digit[i]);
    }
    printf("\n");
    }
    bigInteger operator *(int x)const{
    bigInteger ret;
    ret.init();
    int carry = 0;
    for(int i = 0 ; i < size ; i++){
    int tmp = x*digit[i] + carry;
    carry = tmp/10000;
    tmp %= 10000;
    ret.digit[ret.size++] = tmp;
    }
    if(carry != 0){
    ret.digit[ret.size++] = carry;
    }
    return ret;
    }
    bigInteger operator +(const bigInteger &A)const{
    bigInteger ret;
    ret.init();
    int carry = 0;
    for(int i = 0 ; i < A.size || i < size ; i++){
    int tmp = A.digit[i] + digit[i] + carry;
    carry = tmp/10000;
    tmp %= 10000;
    ret.digit[ret.size++] = tmp;
    }
    if(carry != 0){
    ret.digit[ret.size++] = carry;
    }
    return ret;
    }
    bigInteger operator /(int x)const{
    bigInteger ret;
    ret.init();
    int remainder = 0; // 余数
    for(int i = size - 1 ; i >= 0 ; i--){ // 从最高位至最低位依次完成计算
    int t = (remainder*10000+digit[i])/x;
    // 计算当前位置值加上高位剩余的余数的和对x求得的商
    int r = (remainder*10000+digit[i])%x;
    ret.digit[i] = t;
    remainder = r;
    }
    ret.size = 0;
    // 返回高精度整数的size初始值为0,即当所有位数字都为0时,
    // digit[0]代表数字0,作为最高有效位,高精度整数即数字0
    for(int i = 0 ; i < maxDigits ; i++){
    if(digit[i] != 0) ret.size = i;
    // 若存在非0位,确定最高的非0位,作为最高有效位
    }
    ret.size++;
    return ret;
    }
    int operator %(int x)const{
    int remainder = 0; // 余数
    for(int i = size -1 ; i >= 0 ; i--){
    int t = (remainder*10000+digit[i])/x;
    int r = (remainder*10000+digit[i])%x;
    remainder = r;
    }
    return remainder;
    }
    }a,b,c;
    char str[10000];
    char ans[10000];
    int main(){
    freopen("25in.txt","r",stdin);
    int n,m;
    while(scanf("%d%d",&m,&n)!=EOF){
    scanf("%s",str); // 输入m进制数
    int L = strlen(str);
    a.set(0); // a初始值为0,用来保存转换成十进制的m进制数
    b.set(1); // b初始值为1,在m进制向十进制转换的过程中,依次代表每一位的权重
    for(int i = L-1 ; i >= 0 ; i--){
    // 由低位至高位转换m进制数至相应的十进制数
    int t;
    if(str[i]>='0' && str[i] <= '9'){
    t = str[i] - '0';
    }else t = str[i]-'A'+10;
    a = a+b*t; // 累加当前数字乘当前位权重的积
    b = b*m;
    }
    int size = 0; // 代表转换为n进制后的字符个数
    do{
    int t = a%n; // 求余数
    if(t >= 10) ans[size++] = t-10+'a';
    else ans[size++] = t+'0';
    a = a/n;
    }while(a.digit[0]!=0 || a.size != 1);
    for(int i = size-1 ; i>=0 ; i--) printf("%c",ans[i]);
    printf("\n");
    }

    return 0;
    }

    运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%