您现在的位置是：首页 > 其他

当前栏目

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

算法基础

2023-04-18 16:26:24 时间

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

高精度

🎄 一.高精度加法
🌲二.高精度减法
🌳三.高精度乘法
🌴四.高精度除法

🎄 一.高精度加法

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

输入格式：

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

输出格式：

共一行，包含所求的和。

数据范围：

1 ≤ 整数长度 ≤ 100000

输入样例：

12
23

输出样例：

35

思路：

首先我们们要考虑的是怎样储存数据。结合我们所学应该使用数组储存数据，但是数组下标开头是放个位数还是末尾数呢，在这里我们需要注意一下，在加法当中有进位，如果我们把最高位放在下标为0开头，想要进位就要把所有的数字都挪动一步，而最高位数字如果放在数组末尾就直接添加进位就可以，由此我们第一步就是处理整数的储存。
处理好整数之后，我们还要实现他们加减法如何进行。创建一个临时结果C来接收A+B的每一个对应位相加的结果，在这里C的取值是俩位数相加取模，还要考虑是不是有进位，所以在这里我们还需创建一个t来进行判断进位。

题解：

把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());

按照第一步思路，最高位放在数组最后很容易添加进位，直接用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是为了把字符变成数字

实现我们的加法函数

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

思路：

计算依旧是数组储存，然后倒序，和加法一样
我们在A-B中考虑到A可能比B小，得数为负数，那我们要先判断A和B的大小。两种判别方式，第一，首先判断A和B长度大小，也就是数位多少；第二，如果数位相同，那么则需要从最高位依次往最低位挪动对应比较。
创建临时变量C来接收计算的结果，创建减法函数，在减法函数中依次让A的每一位减去B中对应的每一位数字，其中还需判断一下B的存在性，还要注意把t带上，因为不知道有没有借位，最后就是要注意非0前面还有0的情况，就需要删去，只有一个0的情况要保留。

题解：

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

判断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;
}

创建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

思路：

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

题解：

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

创建变量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

思路：

除法里我们从高位往低位除，剩下的余数作为低一位的数的十位数来除，所以每一个余数剩下后给下一位都要乘以10，每一位的得数都是相除得来的，余数就是取模得来的。
非0前面还有0的情况，就需要删去，只有一个0的情况要保留。

题解：

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

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

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;
}

猜你喜欢

Jease 2.6发布 Java开源内容框架
EasyCVR对接华为iVS订阅摄像机和用户变更请求接口介绍
JVM调优总结：反思
【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
JVM调优总结：调优方法
前端面试【JavaScript】— typeof 是否能正确判断类型？
JVM调优总结：新一代的垃圾回收算法
前端面试【JavaScript】— instanceof 能否判断基本数据类型？
JVM调优总结：典型配置举例
前端面试【JavaScript】— 能不能手动实现一下 instanceof 的功能？
前端面试【JavaScript】— Object.is和=== 有什么区别？
JVM调优总结：分代垃圾回收详述
前端面试【JavaScript】— JS中类型转换有哪几种？
WPF开发入门尝试
前端面试【JavaScript】— == 和 ===有什么区别？
一个Java程序员对2011年的回顾
前端面试【JavaScript】— 对象转原始类型是根据什么流程运行的？
JVM调优总结：垃圾回收面临的问题
直接在代码里面对list集合进行分页
JVM调优总结：基本垃圾回收算法

zl程序教程

当前栏目

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

高精度

🎄 一.高精度加法

🌲二.高精度减法

🌳三.高精度乘法

🌴四.高精度除法

相关文章

当前栏目

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

高 精 度

🎄 一.高精度加法

🌲二.高精度减法

🌳三.高精度乘法

🌴四.高精度除法

相关文章

高精度