4個高精度的關鍵位置是t的表示，t均是上一位留下來的值，遵從大的在前，小的在后

• 加法：上一位留下來的整除后的進位數(shù)，中途的t存當前位的總值
• 減法：上一位留下來的整除后的借位數(shù)，中途的t存當前位的總值，可能是負數(shù)，因此保存時需要(t + 10) % 10，注意，需要有cmp判斷，判斷A >= B是否成立
• 乘法：上一位留下來的整除后的多余的數(shù)，中途的t存當前位的總值
• 除法：從高位開始枚舉，上一位留下來的取模后的余數(shù)，轉換為當前位時，需要先提前乘上10，即t = t * 10，中途的t存當前位的總值

1、高精度加法(高精度 + 高精度)

題目描述

算法分析

• 1、若t1表示第一個數(shù)當前位數(shù)的大小，t2表示第二個數(shù)當前位數(shù)的大小，next表示進位數(shù)

• 2、從個位數(shù)開始進行相加，使用t記錄(t1 + t2 + next)得出的結果，t % 10為該位數(shù)確定好的元素，進行下一個位數(shù)操作時，需要t /= 10

時間復雜度

Java 代碼

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static List<Integer> add(List<Integer> A,List<Integer> B )
    {
        if (A.size()<B.size()) return add(B,A);
        int t = 0;
        for (int i = 0; i < A.size(); i ++ )
        {
            t += A.get(i);
            if (i < B.size()) t += B.get(i);
            A.set(i, t % 10);
            t /= 10;
        }
        if (t!=0) A.add(t);
        return A;
    }
    public static void main(String[] args) {
        //傳進兩個字符串
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        String b = scan.next();
        
        List<Integer> A = new ArrayList<Integer>();
        List<Integer> B = new ArrayList<Integer>();
        for (int i = a.length() - 1; i >= 0; i -- ) A.add(a.charAt(i) - '0');
        for (int i = b.length() - 1; i >= 0; i -- ) B.add(b.charAt(i) - '0');

        List<Integer> C = add(A, B);
        for (int i = C.size() - 1; i >= 0; i -- ) System.out.print((C.get(i)));
    }
}

2、高精度減法(高精度 - 高精度)

算法分析

• 1、模擬減法規(guī)則，從個位到高位進行相減，若個位不夠減則向上一個高位借1

• 2、sub(A,B)函數(shù)中，C = A - B, 若A >= B 則求A - B，否則A < B 則求(B - A),最后再把'-'號添上
• 3、若遍歷完整個A，需要將最靠左的且為 0 的高位全部去除掉

時間復雜度

Java 代碼

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    //判斷A與B的大小關系 A >= B 返回true
    public static boolean cmp(List<Integer> A ,List<Integer> B)
    {
        if (A.size()!=B.size()) return A.size()>B.size();
        for(int i = A.size() - 1;i >= 0;i--)
            if (A.get(i) != B.get(i))
                return A.get(i) > B.get(i);
        //若A = B 返回true
        return true;
            
    }
    // C = A - B, 若A >= B 則求A - B，否則A < B 則求(B - A),最后再把'-'號添上
    public static List<Integer> sub(List<Integer> A,List<Integer> B)
    {
        if(!cmp(A,B)) return sub(B,A);
        int t = 0;
        for(int i = 0;i < A.size();i++)
        {
            t = A.get(i) - t;
            if(i < B.size()) t -= B.get(i);
            A.set(i, (t + 10) % 10);
            if(t < 0) t = 1;
            else t = 0;
        }
        //若該數(shù)的頭為0，則去掉（注意：該數(shù)的數(shù)學順序是倒序）
        while(A.size() > 1 && A.get(A.size() - 1) == 0) A.remove(A.size() - 1);
        return A;
    }
    public static void main(String[] args) {
        //傳進兩個字符串
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        String b = scan.next();
                
        List<Integer> A = new ArrayList<Integer>();
        List<Integer> B = new ArrayList<Integer>();
        for (int i = a.length() - 1; i >= 0; i -- ) A.add(a.charAt(i) - '0');
        for (int i = b.length() - 1; i >= 0; i -- ) B.add(b.charAt(i) - '0');
        //若該數(shù)為負數(shù),添上負號
        if(!cmp(A,B)) System.out.print("-");
        List<Integer> C = sub(A, B);
        for (int i = C.size() - 1; i >= 0; i -- ) System.out.print((C.get(i)));
    }
    
}

3、高精度乘法(高精度 * 低精度)

算法分析

此處 A 是高精度的字符串， B 是整數(shù)

• 1、模擬乘法規(guī)則，從A的個位到高位與B相乘，乘得的結果放入t中，則此位的數(shù)為t % 10.把t / 10剩余給下一個高位

• 2、若遍歷完整個A，t > 0,則表示還有剩余的數(shù)，則需要將剩余的數(shù)繼續(xù)補到下一個高位

時間復雜度

Java 代碼

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static List<Integer> mul(List<Integer> A, int B)
    {
        int t = 0;
        for(int i = 0;i < A.size();i++)
        {
            t += A.get(i) * B;
            A.set(i, t % 10);
            t /= 10;
        }
        while(t != 0)
        {
            A.add(t % 10);
            t /= 10;
        }
        return A;
    }
    public static void main(String[] args) {
        //傳進一個字符串，一個數(shù)字
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        int B = scan.nextInt();
                
        List<Integer> A = new ArrayList<Integer>();
        for (int i = a.length() - 1; i >= 0; i -- ) A.add(a.charAt(i) - '0');
        List<Integer> C = mul(A, B);

        for (int i = C.size() - 1; i >= 0; i -- ) System.out.print((C.get(i)));
    }
}

4、高精度除法(高精度 / 低精度)，以及高精度取模

算法分析

• 1、模擬除法規(guī)則，從高位到底位與除數(shù)進行相除，除得的余數(shù)放入t中，則此位的數(shù)為t / 10.把剩余的t % 10給下一個底位

• 2、若遍歷完整個A，需要將最靠左的且為0的高位全部去除掉
  
  image.png

時間復雜度

Java 代碼

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int t = 0;
    //從高位往低位除
    public static List<Integer> div(List<Integer> A,int B)
    {
        for(int i = A.size() - 1;i >= 0 ;i--)
        {
            t = t * 10 + A.get(i);
            A.set(i, t / B);
            t %= B;
        }
        while(A.size() > 1 && A.get(A.size() - 1) == 0) A.remove(A.size() - 1);
        return A;
    }
    public static void main(String[] args) {
        //傳進一個字符串，一個數(shù)字
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        int B = scan.nextInt();
                
        List<Integer> A = new ArrayList<Integer>();
        for (int i = a.length() - 1; i >= 0; i -- ) A.add(a.charAt(i) - '0');
        List<Integer> C = div(A, B);

        for (int i = C.size() - 1; i >= 0; i -- ) System.out.print((C.get(i)));
        System.out.println();
        System.out.println(t);
    }
}