高精度除以低精度(A/b)
java模板
// A / b = C ... r, A >= 0, b > 0 r=余数
private static List<Integer> div(List<Integer> A, int b){
for(int i = A.size()-1 ; i >= 0 ; i--){ //除法是从最高位开始计算的
r = r * 10 + A.get(i);
A.set(i,r / b );
r %= b;
}
while(A.size() > 1 && A.get(A.size() -1) == 0) A.remove(A.size() - 1); //去除前导0
return A;
}
解析
1:(r*10+Ai)/b
代表的是每一位的除法操作;每进行一次操作就会得出商的一位数;最终得出的余数r%b
就是我们想要的余数
如图
r代表的就是红色圆圈画的1,1,2,也就是每次计算剩下的余数
r*10+Ai
代表的是12,13,24
b就是0,11,11,22
最终的商就是每次除法操作得出的数字的组合:0112
最终余数就是r%b = 2;
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main{
static int r = 0;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String a = in.next();
int b = in.nextInt();
List<Integer> A = new ArrayList<>();
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(r);
}
private static List<Integer> div(List<Integer> A, int b){
for(int i = A.size()-1 ; i >= 0 ; i--){
r = r * 10 + A.get(i);
A.set(i,r / b );
r %= b;
}
while(A.size() > 1 && A.get(A.size() -1) == 0) A.remove(A.size() - 1); //去除前导0
return A;
}
}
解析:
1:如果你是在原本的集合上设置值,那么是不用反转的;如果是开辟了一个新的数组,那么一定要记得反转Collection.reverse()
;
2:因为在这里把r声明成了成员变量,所以在div方法中没有传递r参数;是为了记忆模板的时候和加减乘保持一致性比较好记;所以可能和y总给的模板有些不一样;按照自己的习惯记就好了;
3:上面的第一部分psvm方法处理输入输出操作没啥可说的,多写几遍就熟悉了;