模版:高精度加减乘除

4个高精度的关键位置是t的表示，t均是上一位留下来的值，遵从大的在前，小的在后

• 加法：上一位留下来的整除后的进位数，中途的t存当前位的总值
• 减法：上一位留下来的整除后的借位数，中途的t存当前位的总值，可能是负数，因此保存时需要(t + 10) % 10，注意，需要有cmp判断，判断A >= B是否成立
• 乘法：上一位留下来的整除后的多余的数，中途的t存当前位的总值
• 除法：从高位开始枚举，上一位留下来的取模后的余数，转换为当前位时，需要先提前乘上10，即t = t * 10，中途的t存当前位的总值

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

题目描述

算法分析

• 1、若t1表示第一个数当前位数的大小，t2表示第二个数当前位数的大小，next表示进位数

• 2、从个位数开始进行相加，使用t记录(t1 + t2 + next)得出的结果，t % 10为该位数确定好的元素，进行下一个位数操作时，需要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、模拟减法规则，从个位到高位进行相减，若个位不够减则向上一个高位借1

• 2、sub(A,B)函数中，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;
        }
        //若该数的头为0，则去掉（注意：该数的数学顺序是倒序）
        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');
        //若该数为负数,添上负号
        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 是整数

• 1、模拟乘法规则，从A的个位到高位与B相乘，乘得的结果放入t中，则此位的数为t % 10.把t / 10剩余给下一个高位

• 2、若遍历完整个A，t > 0,则表示还有剩余的数，则需要将剩余的数继续补到下一个高位

时间复杂度

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) {
        //传进一个字符串，一个数字
        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、模拟除法规则，从高位到底位与除数进行相除，除得的余数放入t中，则此位的数为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) {
        //传进一个字符串，一个数字
        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);
    }
}