题目描述
给定两个正整数A，B，请你计算 A / B的商和余数。
输入格式
共两行，第一行包含整数A，第二行包含整数B。
输出格式
共两行，第一行输出所求的商，第二行输出所求余数。
数据范围
1≤A的长度≤100000,
1≤B≤10000
样例
输入样例：
7
2
输出样例：
3
1
算法1
(暴力枚举) O(n2)
blablabla
时间复杂度分析：blablabla
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//int r=0;
vector<int> div(vector<int> &A,int B,int &r){//r传入r的地址，便于直接对余数r进行修改
vector<int> C;
for(int i=0;i<A.size();i++){//对A从最高位开始处理
r=r*10+A[i];//将上次的余数*10在加上当前位的数字，便是该位需要除的被除数
C.push_back(r/B);//所得即为商在这一位的数字
r=r%B;
}
//由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，vector只有删除最后一个数字pop_back是常数复杂度，而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移，
//因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0
reverse(C.begin(),C.end());
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main(){
string a;
int B,r=0; //代表余数
cin>>a>>B;
vector<int> A;
for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位，由于在除法的手算过程中，发现从高位进行处理
//for(int i=0;i<A.size();i++) cout<<A[i];
//cout<<B;
auto C = div(A,B,r);
for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位
cout<<endl<<r;//输出余数
cout<<endl;
return 0;
}
vector[HTML_REMOVED] div(vector[HTML_REMOVED] &A,int B,int &r){//r传入r的地址，便于直接对余数r进行修改
vector[HTML_REMOVED] C;
bool f = false;
for(int i=0;i<A.size();i++){//对A从最高位开始处理
r=r10+A[i];//将上次的余数10在加上当前位的数字，便是该位需要除的被除数
if(r/B!=0) {C.push_back(r/B); f = true;}
else if(f == true) C.push_back(r/B);
r=r%B;
}
if(C.size() == 0) C.push_back(0);
return C;
}
这样写就不用先反转再去掉前导零了
我想问一下为什么不学高精度除以高精度
因为一般来讲不会用到。而且复杂度应该会很高。
你好，可以帮我解答一个困惑吗？翻转如果是为了删除前导零的话，那删除以后return的时候不用再翻转回去吗？
是因为后面在输出的时候是反着输出的C是吗？
对滴，你也可以模拟一下
为什么不学高精除高精呀
我觉得把你这高精度减法和高精度乘法堆一块应该就是除法，小学的竖式
y总的错冷吗？？
没有呀
为什么不能定义一个全局变量r
请问这个算法 n^2 是怎么推出来的？
应该是n，由A的长度决定，他应该是没有修改题解模板
algorithm头文件中的reverse()算法时间复杂度是O(n^2)的
逆置时间复杂度为O(n)把，从两头开始对调，到中间停止，执行n/2次，复杂度为O(n)
感觉这个复杂度一个是n
为什么我的样例点有一个过不了 #include<bits/stdc++.h> using namespace std; const int N=100010; vector<int>a,c; string n1; int b; void put(string s,vector<int>&d) { for(int i=s.size()-1;i>=0;i--) { d.push_back(s[i]-'0'); } } void div() { int t=0; int pos=a.size()-1; // for(int i=0;i<a.size();i++)cout<<a[i]; // cout<<endl; while(pos>=0) { t=(t*10+a[pos--]); if(t%b==t){c.push_back(0),t=(t*10+a[pos--]);} c.push_back(t/b); t=(t%b); } int flag=0; for(int i=0;i<c.size();i++) { if(c[i])flag=1; if(!flag&&!c[i])continue; cout<<c[i]; } cout<<endl; cout<<t; } int main() { //freopen("in.txt","r",stdin); ios::sync_with_stdio(false); cin>>n1>>b; put(n1,a); div(); }高精度拿java的BigDecimal写可不可以啊
java和python不用学高精度吧
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
//去除前导0
int delPreZero(int x[], int xLen){
int i=xLen;
while(x[i-1]==0 && i>1){ i--; } return i;}
//逆序输出数组值
void printArr(int x[], int xLen){
for(int i=xLen-1; i>=0; i–){
cout << x[i];
}
cout << endl;
}
//若x>=y返回true，否则返回false
bool compare(int x[], int y[], int xLen, int yLen){
if(xLen < yLen){
return false;
}
if(xLen == yLen){ for(int i=xLen-1; i>=0; i--){ if(x[i] > y[i]){ return true; } if(x[i] < y[i]){ return false; } } return true; } return true;}
//若x>=y,则x的高位减去y（只减一次）,返回值为x的新长度
int sub(int x[], int y[], int z[], int xLen, int yLen){
int zLoc = xLen - yLen ; //商的位置
//若不够减，则商的位置后移一位 for(int i=1; i<=yLen; i++){ if(x[xLen-i] > y[yLen-i]) break; if(x[xLen-i] < y[yLen-i]){ zLoc--; break; } } if(zLoc<0) return xLen; //当前被除数x的高位与除数y做一次减法运算 for(int i=zLoc,j=0; i<xLen && j<yLen; i++,j++){ while(x[i] < y[j]){ x[i+1]--; x[i] += 10; } x[i] -= y[j]; } //商的相应位置加一 z[zLoc]++; //计算当前被除数x的真实长度 while(x[xLen-1]==0) xLen--; if(xLen <= 0) xLen = 1; return xLen;}
int main(){
char as[301], bs[301];
int a[301]={0}, b[301]={0}, c[301]={0}; int aLen = 0, bLen = 0, cLen = 1, maxLen = 0; int i; //输入 cin >> as >> bs; aLen = strlen(as); bLen = strlen(bs); //被除数和除数分别逆序存放 for(i=0; i<aLen; i++){ a[i] = as[aLen-1-i] - '0'; } for(i=0; i<bLen; i++){ b[i] = bs[bLen-1-i] - '0'; } //去除前导0 aLen = delPreZero(a, aLen); bLen = delPreZero(b, bLen); //通过从高位开始连续减去除数，计算商和余数 cLen = aLen - bLen + 1; while(compare(a, b, aLen, bLen)){ aLen = sub(a, b, c, aLen, bLen); } //解决商的位数是0或负数的情况 if(cLen < 1){ cLen = 1; } //去除商的前导0 cLen = delPreZero(c, cLen); //输出商c printArr(c, cLen); //输出余数a printArr(a, aLen); return 0;}
解析特别详细，好评！
详细
可以可以正在记录模板
reverse(C.begin(),C.end()); 这个是什么意思呢
对数组C进行反转
写得太细致了👍👍
当时y总为什么说不学 那个 高精度除以高精度来着？
注释对新手太友好了
棒棒棒
写的不错！