4个高精度的关键位置是t的表示，t均是上一位留下来的值，遵从大的在前，小的在后
- 加法：上一位留下来的整除后的进位数，中途的
t存当前位的总值 - 减法：上一位留下来的整除后的借位数，中途的
t存当前位的总值，可能是负数，因此保存时需要(t + 10) % 10，注意，需要有cmp判断，判断A >= B是否成立 - 乘法：上一位留下来的整除后的多余的数，中途的
t存当前位的总值 - 除法：从高位开始枚举，上一位留下来的取模后的余数，转换为当前位时，需要先提前乘上
10，即t = t * 10，中途的t存当前位的总值
1、高精度加法(高精度 + 高精度)
题目描述
算法分析
- 1、若
t1表示第一个数当前位数的大小，t2表示第二个数当前位数的大小，next表示进位数
- 2、从个位数开始进行相加，使用
t记录(t1 + t2 + next)得出的结果，t % 10为该位数确定好的元素，进行下一个位数操作时，需要t /= 10
时间复杂度 )
Java 代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static List<Integer> add(List<Integer> A,List<Integer> B )
{
if (A.size()<B.size()) return add(B,A);
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A.get(i);
if (i < B.size()) t += B.get(i);
A.set(i, t % 10);
t /= 10;
}
if (t!=0) A.add(t);
return A;
}
public static void main(String[] args) {
//传进两个字符串
Scanner scan = new Scanner(System.in);
String a = scan.next();
String b = scan.next();
List<Integer> A = new ArrayList<Integer>();
List<Integer> B = new ArrayList<Integer>();
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)));
}
}
2、高精度减法(高精度 - 高精度)
算法分析
- 1、模拟减法规则，从个位到高位进行相减，若个位不够减则向上一个高位借1
- 2、
sub(A,B)函数中，C = A - B, 若A >= B则求A - B，否则A < B则求(B - A),最后再把'-'号添上 - 3、若遍历完整个
A，需要将最靠左的且为 0 的高位全部去除掉
时间复杂度
Java 代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
//判断A与B的大小关系 A >= B 返回true
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);
//若A = B 返回true
return true;
}
// C = A - B, 若A >= B 则求A - B，否则A < B 则求(B - A),最后再把'-'号添上
public static List<Integer> sub(List<Integer> A,List<Integer> B)
{
if(!cmp(A,B)) return sub(B,A);
int t = 0;
for(int i = 0;i < A.size();i++)
{
t = A.get(i) - t;
if(i < B.size()) t -= B.get(i);
A.set(i, (t + 10) % 10);
if(t < 0) t = 1;
else t = 0;
}
//若该数的头为0，则去掉（注意：该数的数学顺序是倒序）
while(A.size() > 1 && A.get(A.size() - 1) == 0) A.remove(A.size() - 1);
return A;
}
public static void main(String[] args) {
//传进两个字符串
Scanner scan = new Scanner(System.in);
String a = scan.next();
String b = scan.next();
List<Integer> A = new ArrayList<Integer>();
List<Integer> B = new ArrayList<Integer>();
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');
//若该数为负数,添上负号
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)));
}
}
3、高精度乘法(高精度 * 低精度)
算法分析
此处 A 是高精度的字符串， B 是整数
- 1、模拟乘法规则，从A的个位到高位与
B相乘，乘得的结果放入t中，则此位的数为t % 10.把t / 10剩余给下一个高位
- 2、若遍历完整个
A，t > 0,则表示还有剩余的数，则需要将剩余的数继续补到下一个高位
时间复杂度
Java 代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static List<Integer> mul(List<Integer> A, int B)
{
int t = 0;
for(int i = 0;i < A.size();i++)
{
t += A.get(i) * B;
A.set(i, t % 10);
t /= 10;
}
while(t != 0)
{
A.add(t % 10);
t /= 10;
}
return A;
}
public static void main(String[] args) {
//传进一个字符串，一个数字
Scanner scan = new Scanner(System.in);
String a = scan.next();
int B = scan.nextInt();
List<Integer> A = new ArrayList<Integer>();
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)));
}
}
4、高精度除法(高精度 / 低精度)，以及高精度取模
算法分析
- 1、模拟除法规则，从高位到底位与除数进行相除，除得的余数放入
t中，则此位的数为t / 10.把剩余的t % 10给下一个底位
- 2、若遍历完整个
A，需要将最靠左的且为0的高位全部去除掉
image.png
时间复杂度
Java 代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int t = 0;
//从高位往低位除
public static List<Integer> div(List<Integer> A,int B)
{
for(int i = A.size() - 1;i >= 0 ;i--)
{
t = t * 10 + A.get(i);
A.set(i, t / B);
t %= B;
}
while(A.size() > 1 && A.get(A.size() - 1) == 0) A.remove(A.size() - 1);
return A;
}
public static void main(String[] args) {
//传进一个字符串，一个数字
Scanner scan = new Scanner(System.in);
String a = scan.next();
int B = scan.nextInt();
List<Integer> A = new ArrayList<Integer>();
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(t);
}
}
网友评论