【算法基础】(一)基础算法 ---高精度

✨个人主页：bit me
✨当前专栏：算法基础
🔥专栏简介：该专栏主要更新一些基础算法题，有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下，互相监督打卡学习 🌹 🌹 🌹

🎄 一.高精度加法

给定两个正整数（不含前导 0 ），计算它们的和。

输入格式：

共两行，每行包含一个整数。

输出格式：

共一行，包含所求的和。

数据范围：

1 ≤ 整数长度 ≤ 100000

输入样例：

12
23

输出样例：

35

思路：

1. 首先我们们要考虑的是怎样储存数据。结合我们所学应该使用数组储存数据，但是数组下标开头是放个位数还是末尾数呢，在这里我们需要注意一下，在加法当中有进位，如果我们把最高位放在下标为0开头，想要进位就要把所有的数字都挪动一步，而最高位数字如果放在数组末尾就直接添加进位就可以，由此我们第一步就是处理整数的储存。

2. 处理好整数之后，我们还要实现他们加减法如何进行。创建一个临时结果C来接收A+B的每一个对应位相加的结果，在这里C的取值是俩位数相加取模，还要考虑是不是有进位，所以在这里我们还需创建一个t来进行判断进位。

题解：

1. 把a，b用字符串的形式储存赋给数组，因为String表示长度length可以使用size方法

Scanner scanner = new Scanner(System.in);
String a = scanner.next();
String b = scanner.next();
List<Integer> A = new ArrayList<>(a.length());
List<Integer> B = new ArrayList<>(b.length());

2. 按照第一步思路，最高位放在数组最后很容易添加进位，直接用add就可以实现

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');

charAt返回指定下标下面的char值，后面减去0是为了把字符变成数字

3. 实现我们的加法函数

List<Integer> C = add(A,B);

1.用新的数组C来一个一个接收A和B的每一个对应位相加的结果，注意取值是模
2.使用临时变量t来判断是否进位，然后实现进位，如果加法循环结束，t不是为0就要最高位进1

public static List<Integer> add(List<Integer> A ,List<Integer> B){List<Integer> C = new ArrayList<>();int t = 0;for(int i = 0;i < A.size() || i < B.size();i++){if(i < A.size()) t += A.get(i);if(i < B.size()) t += B.get(i);C.add(t % 10);t = t/10;}if(t != 0) C.add(1);return C;}

 
附上总的代码

public static void main(String[] args){Scanner scanner = new Scanner(System.in);String a = scanner.next();String b = scanner.next();List<Integer> A = new ArrayList<>(a.length());List<Integer> B = new ArrayList<>(b.length());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) + "");}}
public static List<Integer> add(List<Integer> A ,List<Integer> B){List<Integer> C = new ArrayList<>();int t = 0;for(int i = 0;i < A.size() || i < B.size();i++){if(i < A.size()) t += A.get(i);if(i < B.size()) t += B.get(i);C.add(t % 10);t = t/10;}if(t != 0) C.add(1);return C;}

 

🌲二.高精度减法

给定两个正整数（不含前导 0），计算它们的差，计算结果可能为负数。

输入格式：

共两行，每行包含一个整数。

输出格式：

共一行，包含所求的差。

数据范围：

1 ≤ 整数长度 ≤ 105

输入样例：

32
11

输出样例：

21

思路：

1. 计算依旧是数组储存，然后倒序，和加法一样

2. 我们在A-B中考虑到A可能比B小，得数为负数，那我们要先判断A和B的大小。两种判别方式，第一，首先判断A和B长度大小，也就是数位多少；第二，如果数位相同，那么则需要从最高位依次往最低位挪动对应比较。

3. 创建临时变量C来接收计算的结果，创建减法函数，在减法函数中依次让A的每一位减去B中对应的每一位数字，其中还需判断一下B的存在性，还要注意把t带上，因为不知道有没有借位，最后就是要注意非0前面还有0的情况，就需要删去，只有一个0的情况要保留。

题解：

1. 把a，b用字符串的形式储存赋给数组

Scanner scanner = new Scanner(System.in);
String s1 = scanner.next();
String s2 = scanner.next();
List<Integer> A = new ArrayList<>();
List<Integer> B = new ArrayList<>();
for(int i = s1.length() - 1;i >= 0;i --) A.add(s1.charAt(i) - '0');
for(int i = s2.length() - 1;i  >= 0; i --) B.add(s2.charAt(i) - '0');

2. 判断A-B的正负，并完善函数

if(!cmp(A,B)){System.out.print("-");
}

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);}
}
return true;
}

函数里第一步的操作相当于

if(A.size() >= B.size()){return true;
}else{return false;
}

3. 创建C来接收A-B的结果，并完善函数

List<Integer> C = sub(A,B);

在对应位A-B中应该是A.get(i) - B.get(i) - t ，因为可能B为零，所以需要判断一下是不是存在
 
还需考虑C的取值是取模，然后借位t是否被借位
 
最后还需考虑非0前面还有0的情况，就需要删去，只有一个0的情况要保留。

public static List<Integer> sub(List<Integer> A,List<Integer> B){
if(!cmp(A,B)){return sub(B,A);
}List<Integer> C = new ArrayList<>();
int t = 0;
for(int i = 0;i < A.size();i ++){t = A.get(i) - t;if(i < B.size()) t -= B.get(i);C.add((t + 10) % 10);if(t < 0) t = 1;else t = 0;
}
while(C.size() > 1 && C.get(C.size() - 1) == 0)  C.remove(C.size() - 1);return C;
}

 
附上总的代码

public static void main(String[] args){Scanner scanner = new Scanner(System.in);String s1 = scanner.next();String s2 = scanner.next();List<Integer> A = new ArrayList<>();List<Integer> B = new ArrayList<>();for(int i = s1.length() - 1;i >= 0;i --) A.add(s1.charAt(i) - '0');for(int i = s2.length() - 1;i  >= 0; i --) B.add(s2.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));}}public static List<Integer> sub(List<Integer> A,List<Integer> B){if(!cmp(A,B)){return sub(B,A);}List<Integer> C = new ArrayList<>();int t = 0;for(int i = 0;i < A.size();i ++){t = A.get(i) - t;if(i < B.size()) t -= B.get(i);C.add((t + 10) % 10);if(t < 0) t = 1;else t = 0;}while(C.size() > 1 && C.get(C.size() - 1) == 0)  C.remove(C.size() - 1);return C;}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);}}return true;}
}

 

🌳三.高精度乘法

给定两个非负整数（不含前导 0） A 和 B，请你计算 A×B 的值。
输入格式：

共两行，第一行包含整数 A，第二行包含整数 B。

输出格式：

共一行，包含 A×B的值。

数据范围：

1 ≤ A的长度 ≤ 100000
,
0≤B≤10000

输入样例：

2
3

输出样例：

6

思路：

1. 在我们乘法计算当中，例如123×45，我们在平时的计算方式和计算机不一样，我们是一个一个数字相乘得到得结果再相加，在计算机里这里我们可以把第一串数字看作是字符串，第二串数字不变，用第二个数字乘第一串字符串的每一个字符，按照这样的计算方式我们可以得到一个规律，比如用临时变量C来接收每一个结果，C中除了第一个和最后一个数，中间的每一个得数都是 = （字符 n × 第二串数字 + 进数t）% 10

2. 非0前面还有0的情况，就需要删去，只有一个0的情况要保留。

题解：

1. 对A中的数倒序遍历到数组中

Scanner scanner = new Scanner(System.in);
String a = scanner.next();
int b = scanner.nextInt();
List<Integer> A = new ArrayList<>(a.length());
for(int i = a.length() - 1; i >= 0;i --) A.add(a.charAt(i) - '0');

2. 创建变量C来接收结果以及完成计算过程

public static List<Integer> mul(List<Integer> A ,int b){List<Integer> C = new ArrayList<>();int t = 0;for(int i = 0;i < A.size() || t != 0;i ++ ){if(i < A.size()) t += A.get(i) * b;C.add(t % 10);t /= 10;}while(C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);return C;
}

t ！= 0表示只要进制不为空就一直循环，直到乘法算完
最后一步处理非0前面还有0的情况，就需要删去，只有一个0的情况要保留。

 
附上总的代码

public static void main(String[] args){Scanner scanner = new Scanner(System.in);String a = scanner.next();int b = scanner.nextInt();List<Integer> A = new ArrayList<>(a.length());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));}
}
public static List<Integer> mul(List<Integer> A ,int b){List<Integer> C = new ArrayList<>();int t = 0;for(int i = 0;i < A.size() || t != 0;i ++ ){if(i < A.size()) t += A.get(i) * b;C.add(t % 10);t /= 10;}while(C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);return C;
}

 

🌴四.高精度除法

给定两个非负整数（不含前导 0） A，B，请你计算 A/B 的商和余数。

输入格式：

共两行，第一行包含整数 A，第二行包含整数 B。

输出格式：

共两行，第一行输出所求的商，第二行输出所求余数。

数据范围：

1≤A的长度≤100000
1≤B≤10000
B一定不为 0

输入样例：

7
2

输出样例：

3
1

思路：

1. 除法里我们从高位往低位除，剩下的余数作为低一位的数的十位数来除，所以每一个余数剩下后给下一位都要乘以10，每一位的得数都是相除得来的，余数就是取模得来的。

2. 非0前面还有0的情况，就需要删去，只有一个0的情况要保留。

题解：

1. 对A中的数倒序遍历到数组中

Scanner scanner = new Scanner(System.in);
String a = scanner.next();
int b = scanner.nextInt();
List<Integer> A = new ArrayList<>(a.length());
for(int i = a.length() - 1;i >= 0;i --) A.add(a.charAt(i) - '0');

2. 用临时变量接收结果并且完善函数

List<Integer> C = div(A,b);

public static List<Integer> div(List<Integer> A,int b){List<Integer> C = new ArrayList<>();int r = 0;for(int i = A.size() - 1 ;i >= 0; i --){r = r * 10 + A.get(i);C.add(r / b);r %= b;}Collections.reverse(C);while(C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);C.add(r);return C;
}

这一段函数包括了计算过程以及结果中0得处理结果，上面详细讲解这里不做过多解释

 
附上总的代码

public static void main(String[] arg){Scanner scanner = new Scanner(System.in);String a = scanner.next();int b = scanner.nextInt();List<Integer> A = new ArrayList<>(a.length());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() - 2;i >= 0;i --) System.out.print(C.get(i));System.out.println();System.out.print(C.get(C.size() - 1));
}
public static List<Integer> div(List<Integer> A,int b){List<Integer> C = new ArrayList<>();int r = 0;for(int i = A.size() - 1 ;i >= 0; i --){r = r * 10 + A.get(i);C.add(r / b);r %= b;}Collections.reverse(C);while(C.size() > 1 && C.get(C.size() - 1) == 0) C.remove(C.size() - 1);C.add(r);return C;
}