[数据结构与算法]高精度--java

大整数运算：

• 1.大整数存储：

应为栈式存储，因为如果按照
123456789式存储，如果加一位则所有的位数都需要移动，时间消耗大
按照987654321存储，则进位比较少，节省时间

• 大整数相加–模拟人类的方式
  c++是需要进行自己写

/ C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];//如果B的位数比A的长则，说明B在第i位上也有位数，所以需要相加。
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

java

import java.math.BigInteger;
import java.util.Scanner;
/*BigInteger(byte[] val)
将包含BigInteger的二进制补码二进制表达式的字节数组转换为BigInteger
BigInteger(int numBits, Random rnd)
构造一个随机生成的BigInteger，均匀分布在0到（2 numBits - 1）的范围内。
BigInteger(String val)
将BigInteger的十进制字符串表示形式转换为BigInteger。*/
public class Main {
    /*Java中有两个类可以来处理高精度的计算 分别是处理整数的BigInteger和处理小数的BigDecimal*/
    public static void main(String[] args) {
        Scanner sc =new Scanner(System.in);
        //也可以使用BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        BigInteger a = new BigInteger(sc.nextLine());
        BigInteger b= new BigInteger(sc.nextLine());
        System.out.println(a.add(b));

    }
}

• 因为此时数组第一位存的是个位，第二位存的是十位。。
• 所以算下一位的时候只需要三个变量
  A B 以及进位t，
  A+B+ t
  t>0. 说明大于10 进位
  t=0 不进位
  大整数相加–模拟人类的方式
  先看谁大的当A
  A，B，t
  t>0
  t<0
  
  大整数剑法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];//说明B的位数比A的大，说明在这一位上需要进行相减
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

java

package 大学菜;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Scanner;
/*BigInteger(byte[] val)
将包含BigInteger的二进制补码二进制表达式的字节数组转换为BigInteger
BigInteger(int numBits, Random rnd)
构造一个随机生成的BigInteger，均匀分布在0到（2 numBits - 1）的范围内。
BigInteger(String val)
将BigInteger的十进制字符串表示形式转换为BigInteger。*/
public class 高精度 {
    /*Java中有两个类可以来处理高精度的计算 分别是处理整数的BigInteger和处理小数的BigDecimal*/
    public static void main(String[] args) throws IOException {
//        Scanner sc =new Scanner(System.in);
//        BigInteger a = new BigInteger(sc.nextLine());
//        BigInteger b= new BigInteger(sc.nextLine());
//        System.out.println(a.add(b));
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        BigInteger c =new BigInteger(buf.readLine());
        BigInteger d = new BigInteger(buf.readLine());
        //System.out.println(c.add(d));
        System.out.println(c.subtract(d));
        buf.close();
    }
}

//java中加减乘除的方式

package 大学菜;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Scanner;
/*BigInteger(byte[] val)
将包含BigInteger的二进制补码二进制表达式的字节数组转换为BigInteger
BigInteger(int numBits, Random rnd)
构造一个随机生成的BigInteger，均匀分布在0到（2 numBits - 1）的范围内。
BigInteger(String val)
将BigInteger的十进制字符串表示形式转换为BigInteger。*/
public class 高精度 {
    /*Java中有两个类可以来处理高精度的计算 分别是处理整数的BigInteger和处理小数的BigDecimal*/
    public static void main(String[] args) throws IOException {
//        Scanner sc =new Scanner(System.in);
//        BigInteger a = new BigInteger(sc.nextLine());
//        BigInteger b= new BigInteger(sc.nextLine());
//        System.out.println(a.add(b));

        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        BigInteger c =new BigInteger(buf.readLine());
        BigInteger d = new BigInteger(buf.readLine());
        //加
        System.out.println(c.add(d));
        //减
        System.out.println(c.subtract(d));
        //乘
        System.out.println(c.multiply(d));
        //除法需要注意需要有两个存储的地方
        BigInteger[] cd ;
        cd= c.divideAndRemainder(d) ;
        System.out.println(cd[0]+" "+cd[1]);
        //只取模
        System.out.println(c.mod(d));
        buf.close();
       /*答案
        6
        5
        11
        1
        30
        1 1
        1
        */
    }
}