高精度算法(C/C++)

手撕二分查找及其变种,就是干!

高精度算法 (C/C++)

做ACM题的时候,经常遇到大数的加减乘除,乘幂,阶乘的计算,这时给定的数据类型往往不够表示最后结果,这时就需要用到高精度算法。高精度算法的本质是把大数拆成若干固定长度的块,然后对每一块进行相应的运算。这里以考虑4位数字为一块为例,且输入的大数均为正整数(也可以考虑其他位,但要注意在每一块进行相应运算时不能超出数据类型的数值范围;有负整数的话读入时判断一下正负号在决定运算)。

1. 高精度加法

以3479957928375817 + 897259321544245为例:

3479 9579 2837 5817
+897 +2593 +2154 +4245
= = = =
4376 12172 4991 10062
进位0 进位1 进位0 进位1
4377 2172 4992 0062

C语言实现代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
    int i = 0, result = 1;
    for(i = 0; i < b; ++i)
    {
        result *= a;
    }
    return result;
}


//High Precision Of Addition
int main()
{
    char stra[N], strb[N];      //字符串数组,以字符形式储存两个大数;
    int i = 0, step = 4, carry = 0; //step表示块长,carry为进位位;
    int lengtha, lengthb, maxlength, resultsize;    //maxlength表示stra和strb二者长度较大的那个;
    int numa[N], numb[N],numc[N];   //依次储存被加数,加数,和;
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    memset(numc, 0, sizeof(numc));         //初始化为零;
    scanf("%s%s", stra, strb);
    lengtha = strlen(stra);
    lengthb = strlen(strb);     //计算两个大数的长度
    //字符数字转为四位一块的整数数字
    for(i = lengtha-1; i >= 0; --i)
    {
        numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
    }
    for(i = lengthb-1; i >= 0; --i)
    {
        numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
    }
    maxlength = lengtha > lengthb ? lengtha : lengthb;

    //逐块相加,并进位
    for(i = 0; i <= maxlength/step; ++i)
    {
        numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry;    //计算和
        carry = (numa[i] + numb[i])/Pow(10, step);  //计算进位
    }

    //计算最后和的块的总数
    resultsize = numc[maxlength/step] > 0 ? maxlength/step : maxlength/step - 1;
    printf("%d", numc[resultsize]);
    for(i = resultsize-1; i >= 0; --i)
    {
        printf("%04d", numc[i]);    //右对齐,补零输出;
    }
    printf("\n");
    return 0;
}

2. 高精度减法

与加法类似,不同的是要注意正负号和显示位数的变化。以99999037289799 – 100004642015000为例:
先判断被减数和减数哪个大,显然这里减数大,故输出结果为负数。在用大数减去小数,(若某一块相减为负数,则要向高位块借位)如下表

100 0046 4201 5000
-99 -9990 -3728 -9799
1 56 473 5201
借位0 借位1 借位0 借位1
0 56 472 5201

C语言实现代码如下:

用Kolla在阿里云部署10节点高可用OpenStack

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
    int i = 0, result = 1;
    for(i = 0; i < b; ++i)
    {
        result *= a;
    }
    return result;
}

//High Precision Of Subtraction
int main()
{
    char stra[N], strb[N];     //字符串数组,以字符形式储存两个大数;
    int i = 0, step = 4, borrow = 0, mark = 0; //step表示块长,borrow为借位位, mark为结果符号位;
    int lengtha, lengthb, maxlength, resultsize;    //maxlength表示stra和strb二者长度较大的那个;
    int numa[N], numb[N],numc[N],  *maxnum, *minnum;   //依次储存被减数,减数,和;
    memset(stra, 0, sizeof(stra));
    memset(strb, 0, sizeof(strb));
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    memset(numc, 0, sizeof(numc));         //初始化为零;
    scanf("%s%s", stra, strb);
    lengtha = strlen(stra);
    lengthb = strlen(strb);     //计算两个大数的长度
    maxlength = lengtha >= lengthb ? lengtha : lengthb;

    //字符数字转为四位一块的整数数字
    for(i = lengtha-1; i >= 0; --i)
    {
        numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
    }
    for(i = lengthb-1; i >= 0; --i)
    {
        numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
    }

    //找出较大的数
    maxnum = numa;
    minnum = numb;
    mark = 1;
    for(i = (maxlength-1)/step; i >= 0; --i)
    {
        if(numa[i] > numb[i])
        {
            maxnum = numa;
            minnum = numb;
            mark = 1;
            break;
        }
        else if(numa[i] < numb[i])
        {
            maxnum = numb;
            minnum = numa;
            mark = -1;
            break;
        }
    }

    //逐块相减,并借位
    for(i = 0; i <= maxlength/step; ++i)
    {
        numc[i] = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)%Pow(10,step);    //计算差
        borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1;  //计算借位
    }

    //计算最后和的块的总数
    resultsize = maxlength/step;
    while(!numc[resultsize])    --resultsize;
    printf("%d", mark*numc[resultsize]);
    for(i = resultsize-1; i >= 0; --i)
    {
        printf("%04d", numc[i]);    //右对齐,补零输出;
    }
    printf("\n");
    return 0;
}

3. 高精度乘法

乘法可以看作是乘数每一位与被乘数相乘后再相加,以4296556241 x 56241为例:

被乘数 42 9655 6241
乘数 5 6 2 4 1
被乘数x乘数 42 9655 6241
1 42 9655 6241
4 168*10 38620*10 24964*10
2 84*100 19310*100 12482*100
6 252*1000 57930*1000 37446*1000
5 210*10000 48275*10000 31205*10000
累加和 2362122 543006855 351000081
进位(从低位向高位) 241 54304 35100
241 6426 1955 0081

C语言实现代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
    int i = 0, result = 1;
    for(i = 0; i < b; ++i)
    {
        result *= a;
    }
    return result;
}


//High Precision Of Multiplication
int main()
{
    char stra[N], strb[N];      //字符串数组,以字符形式储存两个大数;
    int i = 0, j = 0, k = 0, step = 4, carry = 0; //step表示块长,carry为进位位;
    int lengtha, lengthb, resultsize, tmpsize, eachnum;  //resultsize储存块的总数,eachnum用来储存乘数的每一位
    int numa[N], numb[N], numc[N], tmp[N];   //依次储存被乘数数&积,乘数;
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    memset(numc, 0, sizeof(numc));  //初始化为零;
    scanf("%s%s", stra, strb);
    lengtha = strlen(stra);
    lengthb = strlen(strb);     //计算两个大数的长度
    //将被乘数字符数字转为四位一块的整数数字
    for(i = lengtha-1; i >= 0; --i)
    {
        numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
    }
    //将乘数数字字符数字转为一位一块的整数数字
    for(i = lengthb-1; i >= 0; --i)
    {
        numb[lengthb-1-i] = strb[i]-'0';
    }

    resultsize = tmpsize = (lengtha-1)/step;
    //取乘数的每一位与被乘数的逐块相乘,并进位;
    for(i = 0; i < lengthb; ++i)
    {
        memcpy(tmp, numa, sizeof(numa));    //将numa数组赋值给tmp数组;

        k = i/step;     //k储存每一块需要向高位块移动的次数;
        if(k)
        {
            for(j = tmpsize; j >= 0; --j)
            {
                tmp[j+k] = tmp[j];
                tmp[j] = 0;
            }
            tmpsize += k;
        }

        //乘以乘数每一位扩展成的块;
        eachnum = numb[i]*Pow(10, i%step);
        for(j = 0; j <= tmpsize; ++j)
        {
            tmp[j] *= eachnum;
        }

        //大数相加
        carry = 0;  //进位置零;
        for(j = 0; j <= resultsize; ++j)
        {
            numc[j] += tmp[j] + carry;
            carry = numc[j]/Pow(10,step);
            numc[j] %= Pow(10, step);
        }
        if(carry)
        {
            ++resultsize;
            numc[j] += carry;
        }
    }

    //输出
    printf("%d", numc[resultsize]);
    for(i = resultsize-1; i >= 0; --i)
    {
        printf("%04d", numc[i]);    //右对齐,补零输出;
    }
    printf("\n");
    return 0;
}

4. 高精度除法

高精度除法有两种,一种是高精度除以低精度,另一种是高精度除以高精度。前者只需将每一块除以低精度除数即可;后者则考虑用高精度减法来实现,即每次减去高精度除数,直到减到小于除数,则减的次数即为商,剩余的即为余数。

  • 高精度除以低精度
    以9876342876 / 343为例:
被除数 98 7634 2876
除数 343
向低位块进位 98 137 190
0 2879 4002
余数 190

C语言代码实现如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
    int i = 0, result = 1;
    for(i = 0; i < b; ++i)
    {
        result *= a;
    }
    return result;
}

//High Precision Of division
//(1)高精度除以低精度
int main()
{
    char stra[N];      //字符串数组,以字符形式储存高精度被除数;
    int i = 0, step = 4, carry = 0; //step表示块长,carry为高位向低位进位位;
    int lengtha, resultsize;
    int numa[N], numb, numc[N], numd;   //依次储存被除数,除数,商, 余数;
    memset(numa, 0, sizeof(numa));
    memset(numc, 0, sizeof(numc));         //初始化为零;
    scanf("%s%d", stra, &numb);
    lengtha = strlen(stra);   //计算被除数的长度

    //字符数字转为四位一块的整数数字
    for(i = lengtha-1; i >= 0; --i)
    {
        numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
    }

    carry = 0;  //高位向低位进位位置零
    resultsize = (lengtha-1)/step;
    //逐块相除,高位向低位进位
    for(i = resultsize; i >= 0; --i)
    {
        numc[i] = (numa[i] + carry*Pow(10,step))/numb;    //计算商
        carry = (numa[i] + carry*Pow(10,step))%numb;  //计算进位
    }
    numd = carry;   //最低位块的余数即为整个除法的余数

    //计算最后和的块的总数
    while(!numc[resultsize])    --resultsize;
    //输出商
    printf("%d", numc[resultsize]);
    for(i = resultsize-1; i >= 0; --i)
    {
        printf("%04d", numc[i]);    //右对齐,补零输出;
    }
    //输出余数
    printf("\n%d\n", numd);
    return 0;
}
  • 高精度除以高精度
    以176342876 / 3453452为例:
被除数 176342876
– (51 x 除数) 51 x 3453452
余数 216824
51

C语言代码实现如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//整数乘幂运算函数
int Pow(int a, int b)
{
    int i = 0, result = 1;
    for(i = 0; i < b; ++i)
    {
        result *= a;
    }
    return result;
}

//High Precision Of division
//(2)高精度除以高精度
int main()
{
    char stra[N], strb[N];     //字符串数组,以字符形式储存两个大数;
    int i = 0, step = 4, borrow = 0; //step表示块长,borrow为进位位;
    int lengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark;    //maxlength表示stra和strb二者长度较大的那个;
    int numa[N], numb[N], numc[N], numd[N];   //依次储存被除数数,除数数,商,余数;
    memset(stra, 0, sizeof(stra));
    memset(strb, 0, sizeof(strb));
    memset(numa, 0, sizeof(numa));
    memset(numb, 0, sizeof(numb));
    memset(numc, 0, sizeof(numc));
    memset(numd, 0, sizeof(numd));      //初始化为零;
    scanf("%s%s", stra, strb);
    lengtha = strlen(stra);
    lengthb = strlen(strb);     //计算两个大数的长度

    //字符数字转为四位一块的整数数字
    for(i = lengtha-1; i >= 0; --i)
    {
        numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
    }
    for(i = lengthb-1; i >= 0; --i)
    {
        numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
    }
    memcpy(numd, numa, sizeof(numa));
    numbsize = (lengthb-1)/step;
    numcsize = 0;
    numdsize = (lengtha-1)/step;

    do
    {
        maxsize = numdsize > numbsize ? numdsize : numbsize;
        //计算剩余数是否小于除数
        mark = 1;
        for(i = maxsize; i >= 0; --i)
        {
            if(numd[i] > numb[i])
            {
                mark = 1;
                break;
            }
            else if(numd[i] < numb[i])
            {
                mark = -1;
                break;
            }
        }

        //判断是否余数已经小于除数
        if(!(mark+1))   break;

        borrow = 0; //借位置零;
        //逐块相减,并借位
        for(i = 0; i <= maxsize; ++i)
        {
            tmpnum = (numd[i] - numb[i] + Pow(10, step) + borrow)%Pow(10,step);    //计算差
            borrow = (numd[i] - numb[i] + Pow(10, step) + borrow)/Pow(10,step) - 1;  //计算借位
            numd[i] = tmpnum;
        }
        while(!numd[numdsize])  --numdsize;

        //每减一个除数,商加一;
        borrow = 1;
        for(i = 0; i <= numcsize; ++i)
        {
            numc[i] += borrow;
            borrow = numc[i]/Pow(10,step);
            numc[i] %= Pow(10,step);
        }
        if(borrow)
        {
            ++numcsize;
            numc[i] += borrow;
        }
    }while(1);

    printf("%d", numc[numcsize]);
    for(i = numcsize-1; i >= 0; --i)
    {
        printf("%04d", numc[i]);    //右对齐,补零输出;
    }
    printf("\n");
    printf("%d", numd[numdsize]);
    for(i = numdsize-1; i >= 0; --i)
    {
        printf("%04d", numd[i]);    //右对齐,补零输出;
    }
    printf("\n");
    return 0;
}

【WPF学习】第十七章 键盘输入

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享