Java 数据结构

大数乘积

看天大的数字是怎么在代码里面进行玩耍的……

Posted by Jruei Chen on 2020-10-11
Estimated Reading Time 8 Minutes
Words 1,919 In Total
Viewed Times

前言

数组练习：在计算大数的乘法时，由于数据类型表达范围的原因，计算结果会出现异常。为了实现超大整数的乘法（如两个100位整数的乘法），我们可以将超大整数转化若干的小操作。

例如：
abcde x pqrstz
=abcde x p x 10000+abcde x q x 1000+abcde x r x 100+abcde x s x 10+abcde x t
这样可以把超大整数的乘法转化为一个超大整数乘以一位数再乘以10的幂。

方法

（1）数据的存储

在实际操作中，为了避免超大整数超过了整数的取值范围，往往采用数组的形式按位存储超大整数。如，将整数abcde存储为数组

0 1 2 3 4
a b c d e

为了计算时的方便，我们可以将abcde进行倒序存储，即：

0 1 2 3 4
e d c b a

（2）计算

  1. 幂与乘法移位
    在计算时，“x 10000”，“x 1000”……可以直接转化为数组中数字先右移数位，再向空出的位置中填入零。如：abcde x 100后的结果为：
0 1 2 3 4 5 6
0 0 e d c b a
  1. 乘法运算
    在做乘法运算时，需要有一个代表进位的存储单元，该单元的初始值为0。为了保证最高位的进位，需要再最右位留出一个备用冗余位。
0 1 2 3 4 5 6
6 5 4 3 2 1 0
进位
0

如：123456 x 8，进位单元为0。先是6 x 8=48，积的个位为8+0=8，进位单元的值为4，即：
6乘以8以后，第0位为：8+0=8，进位单元为4，
5乘以8以后，第1位为：0+4=4，进位单元为4；
4乘以8以后，第2位为：2+4=6，进位单元为3，
3乘以8以后，第3位为：4+3=7，进位单元为2，
2乘以8以后，第4位为：6+2=8，进位单元为1，
1乘以8以后，第5为为：8+1=9，进位单元为0.
即得到：

0 1 2 3 4 5 6
8 4 6 7 8 9 0

当每一位都乘过之后，需要进行加法运算。

  1. 加法运算
    加法运算也需要有进位单元保存进位情况，进位单元初始值为0。例如计算123456 x 78。
    123456 x 7 x 10得到：
0 1 2 3 4 5 6
0 2 9 1 4 6 8

123456 x 8得到：

0 1 2 3 4 5 6
8 4 6 7 8 9 0

另外，进位单元为

进位
0

两个数组都从第0位向有开始计算，结果如下：
第0位：0+8+0=8，进位单元为：0
第1位：2+4+0=6，进位单元为：0
第2位：9+6+0=5，进位单元为：1
第3位：1+7+1=9，进位单元为：0
第4位：4+8+0=2，进位单元为：1
第5位：6+9+1=6，进位单元为：1
第6位：8+0+1=9，进位单元为：0
所以：123456 x 78=9629568

例子

下面用Java实现大数乘积作为一个例子

导包

导入必要的包

1
2
3
package BigNumberOperation;
import java.time.temporal.Temporal;
import java.util.Scanner;

一、新建顺序表

该顺序表里面包含一些必要的方法处理输入的数字
将数字转换为用数组存储

1
2
3
4
//用来存放大数的顺序表，因为所有的方法都在该顺序表内，所以右括号}在后面
class ArrayNumber {
  int[] number;
  int curLen = 0;

构造器

1
2
3
4
5
6
7
8
//初始化顺序表
  ArrayNumber(String number) {
     number2arr(number);
  }

//空参构造器
  ArrayNumber() {
  }

最初的想法（可不看）

一开始采用的是long类型数字，发现并不能满足数字无限大的情况
后来采用字符串转字符数组再装数字数组，所以对应的方法都改了
一下出现整段都注释掉的就是这个原因，不再赘述。（注释的代码可以不看）

1
2
3
4
5
/*  
  ArrayNumber(long number) {
    this.curLen = howManyNumber(number);
    number2arr(number);
  }*/

数字入表

将输入数字装换为顺序表（为了方便计算，采用倒序，比如12345在数组里是[5 4 3 2 1]）

1
2
3
4
5
6
7
public void number2arr(String num) {
  char[] a = num.toCharArray();
  number = new int[a.length];
  curLen = a.length;
  for (int i = 0; i < a.length; i++) {
    number[i] = a[i] - '0';
  }

数字入表（可不看）

将数字装换为顺序表（为了方便计算，采用倒序，比如12345在数组里是54321）

1
2
3
4
5
6
7
8
/*
  public void number2arr(long num) {
    number = new int[(int) (curLen * 1.5)];
    for (int i = 0; i < curLen; i++) {
      number[i] = (int) num % 10;
      num /= 10;
    }
  }*/

判断位数

判断数字是几位数构成的

1
2
3
4
5
6
7
8
/*
  public int howManyNumber(long number) {
    int i;
    for (i = 0; number > 0; i++) {
      number /= 10;
    }
    return i;
  }*/

扩大容量

扩大顺序表容量的方法

1
2
3
4
5
6
7
public void enlargeArr() {
  int[] temp = number;
  number = new int[curLen * 2];
  for (int n = 0; n < curLen; n++) {
    number[n] = temp[n];
  }
}

缩小容量

缩小顺序表容量

1
2
3
4
5
6
7
public void reduceArr() {
  int[] temp = number;
  number = new int[curLen * 2];
  for (int n = 0; n < curLen; n++) {
    number[n] = temp[n];
  }
}

是否改变容量

判断是否需要改变顺序表容量

1
2
3
4
5
6
7
public void judgeArr() {
  if (number.length <= curLen + 3) {
    enlargeArr();
  } else if (number.length >= curLen * 3) {
    reduceArr();
  }
}

重写toString方法

重写母类object类中的toString方法，让其按照我们想要的格式输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public String toString() {
  if (judge0()) {
    return "0一共有0个有效数字。";
  } else {
    reverseArr();
    StringBuilder stringArr = new StringBuilder();
    for (int i = 0; i < curLen; i++) {
      stringArr.append(number[i]);
    }

    String cur = "\n一共有" + curLen + "个有效数字。";
    return stringArr.toString() + cur;
  }
}

原数字是否为0

判断数组的最后一个数字为0，即可判断数组是否全为0

1
2
3
public boolean judge0() {
  return number[curLen - 1] == 0;
}

数组内容翻转

将数组里面的内容头尾调位

1
2
3
4
5
6
7
8
public void reverseArr() {
  int temp;
  for (int i = 0; i < curLen/2; i++) {
    temp = number[i];
    number[i] = number[curLen-1-i];
    number[curLen-1-i] = temp;
  }
}

别忘了将该顺序表的右括号}括回来

1
}

二、计算方法类

1
2
3
//  用来存放顺序表的计算方法，右括号}放在后面
//  该类以参数传进的方法输入变量，不用写构造器，用默认的空参构造器
class ComputeMethod {

乘法运算

这里只实现乘法运算，关于加减还有除法读者可以自行尝试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
  public static ArrayNumber multiply(ArrayNumber arr1, ArrayNumber arr2) {
  //  新建一个用来储存结果的数组
    ArrayNumber arr = new ArrayNumber();
    if (arr1.curLen > arr2.curLen) {
      arr.number = new int[arr1.number.length * 2];
    } else {
      arr.number = new int[arr2.number.length * 2];
      }

  //  乘积主要运算算法
    int i, h, k, carry = 0, transNum;
    for (i = 0; i < arr1.curLen; i++) {
      for (h = 0, k = i; h < arr2.curLen; k++, h++) {
        transNum = arr.number[k] + arr2.number[h] * arr1.number[i] + carry;
        arr.number[k] = transNum % 10;
        carry = transNum / 10;
        arr.curLen = k + 1;
      }
      if (carry != 0) {
        arr.number[k] = carry;
        arr.curLen = k + 1;
        carry = 0;
      }
      arr.judgeArr();
    }
    return arr;
  }
}

三、主方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ArrayListCompute {

  public static void main(String[] args) {
    System.out.println("欢迎使用超级大数乘积系统！");
    String s1="1234567",s2="89";
    
//    这里直接使用上文所给的两个数字进行计算，
//    若需要任意数字，可以将下面的注释符号删除，在运行过程输入需要计算的数字就行
//    无论多大都可以，但前提只能是正整数。
//    System.out.println("请在下方输入你想进行乘积运算的两个超级大数（只能是整数）：");
//    Scanner sc =new Scanner(System.in);
//    s1=sc.nextLine();
//    s2=sc.nextLine();

     ArrayNumber arr = ComputeMethod.multiply(new ArrayNumber(s1), new ArrayNumber(s2));
     System.out.println(s1+"和"+s2+"的乘积为：\n"+arr.toString());
  }
}

 

今日的分享就到这里啦，大家有什么想法都可以在评论区讨论~~

每一条我都会很认真看的，谢谢大家~~

（本文为原创作品，未经许可禁止转载！）

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
Java 数据结构
FRIENDS
ESC