高精度算法詳解+例題（大數的加，減，乘，除，取餘運算（附相關JAVA代碼））

目錄

 高精度加法：

 高精度減法：

 高精度乘法：高精度最簡單的運算了吧。

 高精度除法：高精度算法中最難了解的算法。

 高精度取餘：高精度中代碼最短的算法。

 高精度算法例題：

HDU 1002 A - A + B Problem II

HDU1047 Integer Inquiry

         HDU 1250 Hat's Fibonacci 

         HDU - 1865 1sting  

高精度算法，說白了其實就是用程式手動模拟我們在草稿本上的運算。

高精度加法：

1.概念

高精度使用數組來存儲整數，模拟手算進行四則運算

2.高精度運算涉及到的問題

（1） 資料的輸入：因為數字很大，不能用整數來輸入，是以隻能用字元數組輸入，然後轉化。

scanf("%s %s",str,str1)； 
    
           

（2） 資料的存儲：因為後面的運算是從前向後進行，是以我們在轉化的時候需要反向來轉化；

int l1=strlen(str),l2=strlen(str1);
        for(int i=0;i<l1;i++)
            a[l1-i]=str[i]-'0';
        for(int i=0;i<l2;i++)
            b[l2-i]=str1[i]-'0';        
           

（3）資料的運算：進位和借位，這裡就是代碼的核心了，就是手動模拟人算的。

int l=1,x=0;//x是處理進位 
            while(l<=l1||l<=l2)
            {
                c[l]=a[l]+b[l]+x;
                x=c[l]/10;//超過10要進位 
                c[l]%=10;//進位後留下來的數 
                l++;
            }
            c[l]=x;//最後一位可能會進位。 
           

 （4）結果的輸出：小數點的位置和處于多餘的0：最後一步很簡單，看代碼就能懂

while(c[l]==0&&l>=0)//處理前置0 
                l--;
            if(l==-1)//結果為0 
                printf("0");
            else
                for(;l>0;l--)
                    printf("%d",c[l]);
            printf("\n");
           

 整體代碼：

#include<stdio.h>
#include<cstring>
#include<algorithm>
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
using namespace std;
int main()
{
    char str[maxn],str1[maxn];
    int a[maxn],b[maxn],c[maxn];
    me(a,0),me(b,0),me(c,0);
    scanf("%s%s",str,str1);
    int l1=strlen(str),l2=strlen(str1);
    for(int i=0; i<l1; i++)
        a[l1-i]=str[i]-'0';
    for(int i=0; i<l2; i++)
        b[l2-i]=str1[i]-'0';
    int l=1,x=0;//x是處理進位
    while(l<=l1||l<=l2)
    {
        c[l]=a[l]+b[l]+x;
        x=c[l]/10;//超過10要進位
        c[l]%=10;//進位後留下來的數
        l++;
    }
    c[l]=x;//最後一位可能會進位。
    while(c[l]==0&&l>=0)//處理前置0
        l--;
    if(l==-1)//結果為0
        printf("0");
    else
        for(; l>0; l--)
            printf("%d",c[l]);
    printf("\n");
    return 0;
}
           

Java代碼：

import java.math.BigInteger;
import java.util.Scanner;
 
public class mian {
 
    private static Scanner cin;
    public static void main(String[] args) {
        cin=new Scanner(System.in);
        while(cin.hasNext()) {
        BigInteger a,b,sum;
        a=cin.nextBigInteger();
        b=cin.nextBigInteger();
        sum=a.add(b);
        System.out.println(sum);
        }
         
    }
}
           

高精度減法：

和高精度加法相比，減法在差為負數時處理的細節更多一點：當被減數小于減數時，差為負數，差的絕對值是減數減去被減數；在程式實作上用一個變量來存儲符号位，用另一個數組存差的絕對值。

  算法流程：

（1）讀入被減數S1，S2（字元串）：和高精度加法一樣，可以參考上面的那個

（2）置符号位：判斷被減數是否大于減數：大則将符号位置為空；小則将符号位置為“-”，交換減數與被減數；

int l1=strlen(str1),l2=strlen(str2);
        if(l1==l2&&strcmp(str1,str2)<0)//減數比被減數大
            jianfa(str2,str1,1);
        else if(l1<l2)//減數比被減數大
            jianfa(str2,str1,1);
        else
            jianfa(str1,str2,0);
           

（3）被減數與減數處理成數值，放在數組中； 

int len1=strlen(str1),len2=strlen(str2);
    for(int i=0,j=len1-1; i<len1; i++,j--)
        a[i]=str1[j]-'0';
    for(int i=0,j=len2-1; i<len2; i++,j--)
        b[i]=str2[j]-'0';
           

（4）運算：

    A、取數；

    B、判斷是否需要借位；

   C、減，将運算結果放到差數組相應位中；

   D、判斷是否運算完成：是，轉5；不是，轉A；

while(l<=len1)
    {
        c[l]=a[l]-b[l];
        if(c[l]<0)
        {
            c[l]+=10;
            a[l+1]--;
        }
        l++;
    }
           

（5）列印結果：符号位，第1位，循環處理第2到最後一位；

while(c[l]==0&&l>=0)//除去前置0
        l--;
    if(l==-1)
        printf("0");
    else
    {
        if(flog)///減數比被減數大，答案為負數
            printf("-");
        for(int i=l; i>=0; i--)
            printf("%d",c[i]);
    }
    printf("\n");
           

 整體代碼：

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e5+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;

void jianfa(char *str1,char *str2,int flog)
{
    int a[maxn],b[maxn],c[maxn];
    me(a,0),me(b,0),me(c,0);
    int len1=strlen(str1),len2=strlen(str2);
    for(int i=0,j=len1-1; i<len1; i++,j--)
        a[i]=str1[j]-'0';
    for(int i=0,j=len2-1; i<len2; i++,j--)
        b[i]=str2[j]-'0';
    int l=0;
    while(l<=len1)
    {
        c[l]=a[l]-b[l];
        if(c[l]<0)
        {
            c[l]+=10;
            a[l+1]--;
        }
        l++;
    }
    while(c[l]==0&&l>=0)//除去前置0
        l--;
    if(l==-1)
        printf("0");
    else
    {
        if(flog)///減數比被減數大，答案為負數
            printf("-");
        for(int i=l; i>=0; i--)
            printf("%d",c[i]);
    }
    printf("\n");
}
int main()
{
    char str1[maxn],str2[maxn];
    while(scanf("%s%s",str1,str2)!=EOF)
    {
        int l1=strlen(str1),l2=strlen(str2);
        if(l1==l2&&strcmp(str1,str2)<0)//減數比被減數大
            jianfa(str2,str1,1);
        else if(l1<l2)//減數比被減數大
            jianfa(str2,str1,1);
        else
            jianfa(str1,str2,0);
    }
    return 0;
}
           

Java代碼：

import java.math.BigInteger;
import java.util.Scanner;
 
public class mian {
 
    private static Scanner cin;
    public static void main(String[] args) {
        cin=new Scanner(System.in);
        while(cin.hasNext()) {
        BigInteger a,b,sum;
        a=cin.nextBigInteger();
        b=cin.nextBigInteger();
        sum=a.subtract(b);
        System.out.println(sum);
        }
    }
}
           

 高精度乘法：高精度最簡單的運算了吧。

既然是一個很大的整數，我們便不能夠再用簡單的資料類型直接儲存這些整數。我們可以自然得想到要通過數組或字元串來儲存數字。字元串的特點友善我們對于高位整數的輸入，而整形數組的簡便性更有利于每個位數的計算，因而我們結合兩者的優點，不難得出高精度乘法的大緻流程：

a、通過兩個字元串輸入兩個整數； 

char str1[maxn], str2[maxn];
    scanf("%s%s", str1, str2);
           

b、引人兩個數組，将兩個整數通過一定的運算，分别将每一位的數字儲存進數組中；

int n = strlen(str1), m = strlen(str2);
    int a[maxn], b[maxn],c[maxn];
    for (int i = 0, j = n - 1; i < n; i++, j--)
        a[i] = str1[j] - '0';
    for (int i = 0, j = m - 1; i < m; i++, j--)
        b[i] = str2[j] - '0';
           

c、進行每一位的運算；

我們再聲明一個數組c來儲存答案。大家通過一個簡單的乘法運算進行模拟就可以看出，以同樣的儲存規則，a[0] * b[0] = c[0]; a[0] * b[1] + a[1] * b[0] = c[1];逐漸我們可以發現規律： "c[i + j] += a[i] * b[j]"同過一個循環去實作，就可以把c[i + j]計算出來，需要指出的是，這裡的計算我們還沒有進行進位處理。

          1   2   3

  *       5   6   7

  *--------------------------

          7   14  21

      6   12  18

 5   10   15   

*--------------------------

 5   16   34  32  21

for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            c[i + j] += a[i] * b[j];
           

d、處理進位；

for (int i = 0; i < n + m; i++)
        if (c[i] >= 10)
        {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
           

e、輸出結果；

int l=maxn-1;
    while(!c[l])
        l--;
    for (int i = l; i >= 0; i--)
        printf("%d", c[i]);
    printf("\n");
           

 整體代碼：

#include <iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<stack>
#include<string>
const int maxn=1e4+10;
const int mod=1e9+7;
const int inf=1e8;
#define me(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;
int main()
{
    char str1[maxn], str2[maxn];
    scanf("%s%s", str1, str2);
    int n = strlen(str1), m = strlen(str2);
    int a[maxn], b[maxn],c[maxn];
    for (int i = 0, j = n - 1; i < n; i++, j--)
        a[i] = str1[j] - '0';
    for (int i = 0, j = m - 1; i < m; i++, j--)
        b[i] = str2[j] - '0';
    memset(c,0,sizeof(c));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            c[i + j] += a[i] * b[j];
    for (int i = 0; i < n + m; i++)
        if (c[i] >= 10)
        {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }
    int l=maxn-1;
    while(!c[l])
        l--;
    for (int i = l; i >= 0; i--)
        printf("%d", c[i]);
    printf("\n");
    return 0;
}
           

Java代碼：

import java.math.BigInteger;
import java.util.Scanner;
 
public class mian {
 
    private static Scanner cin;
    public static void main(String[] args) {
        cin=new Scanner(System.in);
        while(cin.hasNext()) {
        BigInteger a,b,sum;
        a=cin.nextBigInteger();
        b=cin.nextBigInteger();
        sum=a.multiply(b);
        System.out.println(sum);
        }
    }
}
           

 高精度除法：高精度算法中最難了解的算法。

大數除法，應該算是四則運算裡面最難的一種了。不同于一般的模拟，除法操作步數模仿手工除法，而是利用減法操作實作的。

其基本思想是反複做除法，看從被除數裡面最多能減去多少個除數，商就是多少。

逐個減顯然太慢，要判斷一次最多能減少多少個整的10的n次方。

以7546除23為例。

先減去23的100倍，就是2300，可以減3次，餘下646。   此時商就是300；

然後646減去23的10倍，就是230，可以減2次，餘下186。此時商就是320；

然後186減去23，可以減8次，此時商就是328.

a、通過兩個字元串輸入兩個整數；

scanf("%s %s", str1, str2);
    int l1 = strlen(str1), l2 = strlen(str2);///獲得大數的位數
           

b、進行每一位的運算；

void SubStract(int len) {
    int i = 0;
    while (str1[i] == '0')///查找現在減到哪一位了
        i++;
    int j = i;
    for (; i < len; i++)
        str1[i] = str1[i] - str2[i] + '0';///分别将每一位的數字儲存進數組中
    for (i = len - 1; i > j; i--) {
        if (str1[i] < '0')///若該位<0，則需要借位
            str1[i] += 10, str1[i - 1]--;
    }
}
           

f、輸出結果；

int l=maxn-1;
        while(!num_c[l])
            l--;
        for(int i=l; i>=0; i-- )
            printf("%d", num_c[i]);
        printf("\n");
           

 整體代碼：

#include<stdio.h>
#include<string.h>
#include <algorithm>

using namespace std;
const int maxn = 1e3 + 5;
char str1[maxn], str2[maxn];
int a[maxn];

void SubStract(int len) {
    int i = 0;
    while (str1[i] == '0')///查找現在減到哪一位了
        i++;
    int j = i;
    for (; i < len; i++)
        str1[i] = str1[i] - str2[i] + '0';///分别将每一位的數字儲存進數組中
    for (i = len - 1; i > j; i--) {
        if (str1[i] < '0')///若該位<0，則需要借位
            str1[i] += 10, str1[i - 1]--;
    }
}

int main() {
    while (scanf("%s %s", str1, str2) != EOF) {
        int l1 = strlen(str1), l2 = strlen(str2);///獲得大數的位數
        if (l1 < l2 || (l1 == l2 && strcmp(str1, str2) < 0)) {///如果被除數小于除數，結果為0
            printf("0\n");
            continue;
        }
        int k = 0;
        while (true) {
            a[k] = 0;
            while (strcmp(str1, str2) >= 0) {
                SubStract(l2), a[k]++;///每成功減一次，将商的相應位加1
            }
            k++;
            if (l1 == l2)///減完了 直接跳出
                break;
            for (int i = l2 - 1; i >= 0; i--)
                str2[i + 1] = str2[i];
            str2[0] = '0', l2++, str2[l2] = '\0';
        }
        int i = 0;
        while (a[i] == 0)
            i++;
        for (; i < k; i++)
            printf("%d", a[i]);
        printf("\n");
    }
    return 0;
}
           

Java代碼：

import java.math.BigInteger;
import java.util.Scanner;
 
public class mian {
 
    private static Scanner cin;
    public static void main(String[] args) {
        cin=new Scanner(System.in);
        while(cin.hasNext()) {
        BigInteger a,b,sum;
        a=cin.nextBigInteger();
        b=cin.nextBigInteger();
        sum=a.divide(b);
        System.out.println(sum);
        }
    }
}
           

 高精度取餘：高精度中代碼最短的算法。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e4;
int main()
{
    char str[maxn];
    int mod;
    scanf("%s%d",str,&mod);
    int ans=0;
    for(int i=0;i<strlen(str);i++)
        ans=(ans*10+str[i]-'0')%mod;
    printf("%d\n",ans);
    return 0;
}
           

Java代碼：

import java.math.BigInteger;
import java.util.Scanner;
 
public class mian {
 
    private static Scanner cin;
    public static void main(String[] args) {
        cin=new Scanner(System.in);
        while(cin.hasNext()) {
        BigInteger a,b,sum;
        a=cin.nextBigInteger();
        b=cin.nextBigInteger();
        sum=a.remainder(b);
        System.out.println(sum);
        }
    }
}
           

高精度算法例題：

HDU 1002 A - A + B Problem II

題解：模闆高精度加法。

#include<stdio.h>
#include<cstring>

int main() {
    char str1[10000], str2[10000];
    int a[10000], b[10000], c[10000];
    int  t, k = 0;
    scanf("%d", &t);
    for (int s = 1; s <= t; s++) {
        scanf("%s %s", str1, str2);
        if (k++)
            printf("\n");
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));
        int l1 = strlen(str1), l2 = strlen(str2);
        for (int i = 0; i < l1; i++)
            a[l1 - i] = str1[i] - '0';
        for (int i = 0; i < l2; i++)
            b[l2 - i] = str2[i] - '0';
        int l = 1, x = 0;
        while (l <= l1 || l <= l2) {
            c[l] = a[l] + b[l] + x;
            x = c[l] / 10;
            c[l] %= 10;
            l++;
        }
        c[l] = x;
        printf("Case %d:\n", s);
        printf("%s + %s = ", str1, str2);
        while (c[l] == 0 && l > 0)
            l--;
        if (l == 0)
            printf("0");
        else
            for (; l > 0; l--)
                printf("%d", c[l]);
        printf("\n");
    }
    return 0;
}
           

HDU1047 Integer Inquiry

題意：讓你加n個大數，直到輸入0為止，主要運用高精度加法。

#include<iostream>
#include<cstring>

using namespace std;
char str[100][1000];
int a[100][1000], b[1000];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n = 0;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        while (scanf("%s", str[++n]) && str[n][0] != '0');
        int len, max = 0;
        for (int i = 1; i <= n; i++) {
            len = strlen(str[i]);
            for (int j = 0; j < len; j++)
                a[i][len - j] = str[i][j] - '0';
            if (len > max)
                max = len;
        }
        int l = 1;
        while (l <= max) {
            for (int i = 0; i < n; i++)
                b[l] += a[i][l];
            b[l + 1] += b[l] / 10;
            b[l] %= 10;
            l++;
        }
        while (b[l] == 0 && l > 0)
            l--;
        if (l == 0)
            printf("0");
        else
            for (; l > 0; l--)
                printf("%d", b[l]);
        printf("\n");
        if (t)
            printf("\n");
    }
    return 0;
}
           

HDU 1250 Hat's Fibonacci 

題解：大數加法，但是數組每個位存一個數可能會逾時間或超記憶體，是以使用較大的進制。

#include<stdio.h>

int a[8000][300] = {0};

int main() {
    for (int i = 1; i < 5; i++)
        a[i][1] = 1;
    for (int i = 5; i < 8000; i++) {
        for (int j = 1; j < 255; j++) {
            a[i][j] += a[i - 1][j] + a[i - 2][j] + a[i - 3][j] + a[i - 4][j];
            a[i][j + 1] += a[i][j] / 100000000;
            a[i][j] %= 100000000;
        }
    }
    int n;
    while (scanf("%d", &n) != EOF) {
        int l = 255;
        while (a[n][l] == 0)
            l--;
        printf("%d", a[n][l]);//最前面的數不夠8位直接輸出
        for (--l; l > 0; l--)
            printf("%08d", a[n][l]); //這裡的%08d估計大家都不陌生了吧?就是不夠8位的時候左側使用0補夠 。
        printf("\n");
    }
}
           

HDU - 1865 1sting  

題解：本題總共分兩種情況：

    （1）當第n個不與n-1個相加，就以1結尾，有f（n-1）種情況。

    （2）：第n個1加上第n-1個1，就有發（n-2）種情況以2結尾。

#include<stdio.h>
#include<cstring>

int a[205][255] = {0};

int main() {
    a[1][1] = 1, a[2][1] = 2;
    for (int i = 3; i < 205; i++) {
        for (int j = 1; j < 255; j++) {
            a[i][j] += a[i - 1][j] + a[i - 2][j];
            a[i][j + 1] += a[i][j] / 100000000;
            a[i][j] %= 100000000;
        }
    }
    int n;
    scanf("%d", &n);
    while (n--) {
        char str[300];
        scanf("%s", str);
        int s = strlen(str);
        int l = 251;
        while (a[s][l] == 0)
            l--;
        printf("%d", a[s][l]);
        for (--l; l > 0; l--)
            printf("%08d", a[s][l]);
        printf("\n");
    }
}