算法分析
-
1、模拟除法规则,从高位到底位与除数进行相除,除得的余数放入
t
中,则此位的数为t / 10
.把剩余的t % 10
给下一个底位 -
2、若遍历完整个
A
,需要将最靠左的且为0的高位全部去除掉
时间复杂度 $O(n)$
参考文献
参考y总的模版归纳:https://www.acwing.com/blog/content/277/
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);
}
}
C++代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int t = 0;
vector<int> div(vector<int> &A, int B)
{
vector<int> C;
for(int i = A.size() - 1;i >= 0;i --)
{
t = t * 10 + A[i];
C.push_back(t / B);
t %= B;
}
reverse(C.begin(), C.end());
while(C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> A;
for(int i = a.size() - 1;i >= 0;i --) A.push_back(a[i] - '0');
vector<int> C = div(A, b);
for(int i = C.size() - 1;i >= 0;i --) cout << C[i];
cout << endl;
cout << t;
return 0;
}
当时y总为什么说不学 那个 高精度除以高精度来着?
我也忘记了